Kickstart-2018-RoundH-ProblemA——Big Buttons

本文主要是介绍Kickstart-2018-RoundH-ProblemA——Big Buttons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：长度为N的字符串由R B两个字符组成，但是不能有给定的字符串前缀，问除去给定前缀的字符串之后组成的字符串种类有多少。
题目链接（科学上网）

Note：注意处理重复前缀，即：前缀是否有包含和被包含的关系

#include <string>
#include <iostream>using namespace std;#define LL long longLL pow(LL x, LL y){ ///幂LL ans=1;while(y>0){if(y&1){ans*=x;}x*=x;y>>=1;}return ans;
}int findWin(LL N, LL P, int NO){LL len,numbers=pow(2,N);string forbid,forbidStrs[105];int allForbidLen=0;for(int i=0;i<P;i++){cin>>forbid;bool flag=false;int l1,l2,l,j=0,t;for(j=0;j<allForbidLen;j++){ ///和所有已经在数组中的字符串比较前缀是否有包含关系l1=forbid.length(),l2=forbidStrs[j].length();l=l1>l2 ? l2:l1;for(t=0;t<l;t++){ ///比较前缀if(forbid[t]!=forbidStrs[j][t]){  break; } ///前缀不一样直接跳出}if(t==l){/// 有前缀相同,保留前缀较短的if(flag){ forbidStrs[j]=""; continue; } ///如果已经保存过了则把重复的前缀字符串置为空else {if(l1<l2){ forbidStrs[j]=forbid; }flag=true;}}}if(!flag){ ///没有相同前缀的字符串则加入数组forbidStrs[allForbidLen++]=forbid;}}for(int t=0;t<allForbidLen;t++){ ///正确的个数为 2^N-2^(N-len)-...len=forbidStrs[t].length();if(numbers>0&&len>0){numbers=numbers-pow(2,(N-len));}if(numbers<0){numbers=0;break;}}cout<<"Case #"<<NO<<": "<<numbers<<endl;return 0;
}int main()
{freopen("A.in","r",stdin);freopen("A.out","w",stdout);int T;LL N,P;cin>>T;for(int i=1;i<=T;i++){cin>>N>>P;findWin(N,P,i);}return 0;
}

这篇关于Kickstart-2018-RoundH-ProblemA——Big Buttons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---