[蓝桥杯][算法提高VIP]3000米排名预测

算法提高VIP]3000米排名预测"/>

[蓝桥杯][算法提高VIP]3000米排名预测

题目

题目链接

题解

全排列。

对运动员进行全排列。

对于每种全排列，我们遍历每一个进行预测的同学，从全排列中获取到预测的运动员所在名次。
对于说真话的同学，顺序遍历他预测的全部运动员，要求他预测的每一个运动员的排名都要比后一个运动员的排名小；只要存在一个不满足要求的，就说明这个全排列是错的；只有全都满足（除这个同学预测的最后一位运动员外）要求，才能说明这个全排列对于这个同学的预测是合适的；
对于说假话的同学，顺序遍历他预测的全部运动员，只要存在当前运动员的排名比后一个运动员的排名大就说明这个全排列对于这个同学的预测是合适的。

考虑到全排列了，但是觉得内部是两重循环会超时就没写，一直在想dfs能不能行。主要还是没想好一种合适的方案实现判断每个同学的预测对每一种全排列是否合适，导致最后舍弃全排列的思路。

代码

#include<bits/stdc++.h>
using namespace std;int n, m, flag, a[20][20], c[20], t[20], cnt[20], ccnt;
int b[20] = {0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int ans[20010][20];int main()
{cin>>n>>m;for(int i = 1;i <= m;i ++) {cin>>cnt[i];for(int j = 1;j <= cnt[i];j ++) cin>>a[i][j];cin>>t[i];} do { // b[i]：排名为i的运动员的编号for(int i = 1;i <= n;i ++) c[b[i]] = i; // c[i]：编号为i的运动员的排名for(int i = 1;i <= m;i ++) {flag = !t[i];for(int j = 1;j < cnt[i];j ++) if(c[a[i][j]] >= c[a[i][j+1]]) {flag = !flag; break;}if(flag) break;	
//			下面这部分与上面部分的判断是相同的，上面是进行了简化，可能不容易理解 
//			if(t[i]) {
//				flag = 0;
//				for(int j = 1;j < cnt[i];j ++) 
//				if(c[a[i][j]] >= c[a[i][j+1]]) {flag = 1; break;}
//			} else {
//				flag = 1;
//				for(int j = 1;j < cnt[i];j ++) 
//				if(c[a[i][j]] >= c[a[i][j+1]]) {flag = 0; break;}
//			}
//			if(flag) break;}if(flag) continue;++ccnt;for(int i = 1;i <= n;i ++) ans[ccnt][i] = b[i];} while(next_permutation(b+1, b+n+1));cout<<ccnt<<endl;for(int i = 1;i <= ccnt;i ++, cout<<endl)for(int j = 1;j <= n;j ++) cout << ans[i][j] <<' ';return 0;
}