AKAAKAKAKKAAKK…如果我们在键盘上打出一个AK串(只由字符A和K组成的固定位数的字符串),就可以AK全场么?
不可以,有些AK串不允许出现!
现在给定整数n和m,n表示AK串的位数,m表示所有n位AK串中不允许出现的前缀,请输出合法的n位AK串的个数。
题目大意分析:找出所有k位不包含指定AK子串的AK串个数我们可以把AK串看成一个二进制串,比如:AKAKAAKK=10101100
这里就是把A看成1,把K看成0(下面的代码也是这样定义的)
n位二进制串的个数是 2ⁿ
现在,我们就把问题拆成了几个小问题:
2.如何判断这个二进制串(也就是被处理后的AK串)是否包含不允许出现的AK串
第一个问题可以用一个函数解决int tran(string s){int len=s.size();
int num=0;
for(int i=0;inum<<=1;
if(s[i]=='A') {//A为1,K为0
num+=1;
}
}
num<<=(n-len);//除了1以外的字符都是K也就是0
return num;//返回构造好的二进制串
}
第二个问题也是用一个函数解决(int check(int x){//判断这个串里是否包含被禁止的子串
for(int i=1;i<=m;i++){int k=len[i];
int y=x&(((1<
然后就可以拼凑出整个程序了#includeusing namespace std;
int n,m;
int ft[20],len[20];
int tran(string s){int len=s.size();
int num=0;
for(int i=0;inum<<=1;
if(s[i]=='A') {//A为1,K为0
num+=1;
}
}
num<<=(n-len);//除了1以外的字符都是K也就是0
return num;//返回构造好的二进制
}
int check(int x){//判断这个串里是否包含被禁止的子串
for(int i=1;i<=m;i++){int k=len[i];
int y=x&(((1<string s;
cin>>n>>m;
for(int i=1;i<=m;i++){cin>>s;
ft[i]=tran(s);//将AK串s转成对应前缀的二进制
len[i]=s.size();
}
int ans=0;
int u=1<if(check(i)){//判断i的前缀会不会被禁止
ans++;
}
}
cout<
完结撒花✿✿ヽ(°▽°)ノ✿✿
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻标题:AK串II题解(爱思创平台)-创新互联
分享URL:https://www.cdcxhl.com/article8/dcsgop.html
成都网站建设公司_创新互联,为您提供App开发、网站排名、关键词优化、网站改版、网站设计公司、网站制作
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联