算法提高VIP"/>
题目 1478: 蓝桥杯算法提高VIP
题目 1478: 蓝桥杯算法提高VIP-3000米排名预测
好难。
需要的知识点
- 全排列的库函数
next_permutation(a,a+n)
- 检查一个串有无在另一个串中出现过。不是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("");}
}
更多推荐
题目 1478: 蓝桥杯算法提高VIP
发布评论