蓝桥杯 ALGO-52 算法训练排列问题

问题描述
求一个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表示能
输出格式
所求的排列
样例输入
3 2
0 1 1
1 0 0
0 1 0
样例输出
1 0 2
解释：
对于N=3的没有任何限制的情况
第一：0 1 2
第二：0 2 1
第三：1 0 2
第四：1 2 0
第五：2 0 1
第六：2 1 0
根据题目所给的限制条件由于2不能出现在1后面，0不能出现在2后面
第一：0 2 1
第二：1 0 2
第三：2 1 0

#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;
}

#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 | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版