内容简介:问题描述求一个0~N-1的排列(即每个数只能出现一次),给出限制条件(一张N*N的表,第i行第j列的1或0,表示为j-1这个数不能出现在i-1这个数后面,并保证第i行第i列为0),将这个排列看成一个自然数,求从小到大排序第K个排列。数据规模和约定
问题描述
求一个0~N-1的排列(即每个数只能出现一次),给出限制条件(一张N*N的表,第i行第j列的1或0,表示为j-1这个数不能出现在i-1这个数后面,并保证第i行第i列为0),将这个排列看成一个自然数,求从小到大 排序 第K个排列。
数据规模和约定
N<=10,K<=500000
输入格式
第一行为N和K,接下来的N行,每行N个数,0表示不能,1表示能
输出格式
所求的排列
样例输入
#include <iostream> #include <cmath> #include <vector> #include <algorithm> using namespace std; int main() { int n, k, t, a[10], index[10], cnt = 1; vector<pair<int, int> > v; cin >> n >> k; for (int i = 0; i < n; i++) a[i] = i; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> t; if (t == 0 && i != j) { v.push_back({i, j}); } } } do { int flag = 0; for (int i = 0; i < n; i++) index[a[i]] = i; for (int i = 0; i < v.size(); i++) { if (index[v[i].second] - index[v[i].first] == 1) { flag = 1; break; } } if (flag == 0) { if (cnt == k) { for (int i = 0; i < n; i++) cout << a[i] << ' '; break; } else { cnt++; } } } while (next_permutation(a, a + n)); return 0; }❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 蓝桥杯 ADV-126 算法提高 扫雷
- 蓝桥杯 ADV-133 算法提高 彩票
- 蓝桥杯 ALGO-112 算法训练 暗恋
- 蓝桥杯 算法训练 审美课 java
- 蓝桥杯 ADV-233 算法提高 队列操作
- 蓝桥杯 ADV-189 算法提高 连接乘积
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Defensive Design for the Web
37signals、Matthew Linderman、Jason Fried / New Riders / 2004-3-2 / GBP 18.99
Let's admit it: Things will go wrong online. No matter how carefully you design a site, no matter how much testing you do, customers still encounter problems. So how do you handle these inevitable bre......一起来看看 《Defensive Design for the Web》 这本书的介绍吧!