本文主要是介绍CF Edu94Div2(1400)A String Similarity，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题面
题目大意
给出字符串s，长度为2*n-1
定义两个01串（a和b）相似为：存在一个位置i，使得a[i]=b[i]
求一个01串w，使得w和s[1…n],s[2…n+1],s[n…2*n-1]这n个串相似
数据保证有解
题解
看到网上有神仙构造法，这里讲一下我的解法
考虑到两个01串不相似，当且仅当一个串是另一个串的取反，那么对于从s中截取的n个串，它们取反后的串是不能选的，剩下的串都是可行的，那么不可选取的串的个数是n个（把这n个串放入集合E中），那么只要枚举一个num=0~n，再转成二进制，那么就是取了n+1个不同的串，看看是否在E中存在，若不存在，则表示这是一个可行的解，输出即可
代码
提交之前调试了一波，所以看着会很奇怪
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[55],b[55];
int n,m,T;
bool same(int s){for (int i=s,j=1;j<=n;i++,j++)if (b[j]!=a[i]) return false;return true;
}
bool check(){for (int s=1;s<=n;s++)if (same(s)) return false;return true;
}
void work(){scanf("%d",&n);m=2*n-1;for (int i=1;i<=m;i++){scanf("%1d",&a[i]);a[i]^=1;}for (int num=0;num<=n;num++){int tmp=num,l=0;memset(b,0,sizeof(b));while (tmp){b[++l]=tmp&1;tmp>>=1;}if (check()){for (int i=1;i<=n;i++)printf("%d",b[i]);printf("\n");break;}}
}
int main(){
// freopen("A.in","r",stdin);scanf("%d",&T);for (;T;T--)work();
}
这篇关于CF Edu94Div2(1400)A String Similarity的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
