CF Edu94Div2(1400)C Binary String Reconstruction

本文主要是介绍CF Edu94Div2(1400)C Binary String Reconstruction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

题目大意

有一个01串w，还知道一个定值x
通过这个串可以生成一个新的01串s，长度与w相同，方法如下：
（假设n是串的长度）

if (i-x>=1 && w[i-x]) s[i]=1;
else if (i+x<=n && w[i+x]) s[i]=1;
else s[i]=0;

现在知道生成的串s，求原串w，如果无解输出-1

题解

还是一道比较好想的题
观察发现，如果s[i]=0，那么w[i-x]和w[i+x]一定是0，所以可以先用这个方法把w中必须是0的位置确定下来，然后剩下的位置都是1
但是还要判断是否有解，只要用目前w再生成一次s’，判断s和s’是否相同就好了，具体的说就是：对于位置i，假如s[i]=1，那么w[i-x]或w[i+x]是1才行

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
char ch[N];
int s[N],w[N];
int T,n,x;
int main(){
//	freopen("C.in","r",stdin);scanf("%d",&T);for (;T;T--){scanf("%s",ch+1);n=strlen(ch+1);scanf("%d",&x);for (int i=1;i<=n;i++){w[i]=1;s[i]=ch[i]-'0';}for (int i=1;i<=n;i++)if (!s[i]){if (i+x<=n) w[i+x]=0;if (i-x>=1) w[i-x]=0;}bool bz=1;for (int i=1;i<=n;i++)if (s[i])if (((i+x<=n && !w[i+x]) || i+x>n) && ((i-x>=1 && !w[i-x]) || i-x<1)){bz=0;break;}if (!bz) puts("-1");else{for (int i=1;i<=n;i++)printf("%d",w[i]);puts("");}}
}

这篇关于CF Edu94Div2(1400)C Binary String Reconstruction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---