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();
}