题目 1478: 蓝桥杯算法提高VIP

算法提高VIP"/>

题目 1478: 蓝桥杯算法提高VIP

题目 1478: 蓝桥杯算法提高VIP-3000米排名预测

好难。

需要的知识点

1. 全排列的库函数next_permutation(a,a+n)
2. 检查一个串有无在另一个串中出现过。不是KMP那样的字串，可以是不连续的字串。

东西倒是不多，就是很难写。2022 1 14 16：55写了两个小时最起码
不过好歹顺利写出来了

AC那一刻，感觉多巴胺飙升

//正确的序列要全部出现过，错误的序列一个也不能出现
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 14;
int temp[N];
int righ[N][N];
int wrong[N][N];
int res[400000][N]; // 9！ = 362880 
int n,m;
int r=0,w=0;bool check(int a[])
{bool correct[20];memset(correct,0,sizeof(correct));//a的长度是n//检查是否出现所有的正确的序列bool flag1 = true;for(int i=1;i<=r;i++){int l=righ[i][0];int k=1;for(int j=0;j<n && k<=l ;j++){if(a[j] == righ[i][k])	k++;}if(k>l) //说明在正确的序列中出现过{correct[i] = true;}}//必须满足全部正确的序列都出现过for(int i=1;i<=r;i++) if(!correct[i]) {flag1 = false;break;}//检查有没有出现过错误的序列bool flag2 = false;for(int i=1;i<=w;i++){int l=wrong[i][0];int k=1;for(int j=0;j<n && k<=l; j++){if(a[j] ==wrong[i][k]) k++;}if(k > l) //在错误的预测中出现{flag2 =true;break;}}if(flag1 && !flag2) {return true;}return false;
}
int main()
{cin>>n>>m;int s=0;for(int i=1;i<=m;i++){int l;cin>>l;for(int j=1;j<=l;j++){cin>>temp[j];}int mod;cin>>mod;if(mod==1){++r;for(int j=1;j<=l;j++)righ[r][j] = temp[j];righ[r][0] = l; //第一个数表示预测的长度}else{++w;for(int j=1;j<=l;j++)wrong[w][j] = temp[j];wrong[w][0] = l;}} int a[14];for(int j=0;j<=10;j++) a[j] = j;while(next_permutation(a,a+n)){if(check(a)){++s;for(int i=0;i<n;i++)res[s][i] = a[i];}}cout<<s<<endl;for(int i=1;i<=s;i++){for(int j=0;j<n;j++)cout<<res[i][j]<<" ";puts("");}
}