C. Binary String Reconstruction

 

题意：

给一个长度为n的01串s，以及一个整数x

s是由另一个01串w转换而来的

转换方式：

①如果w[i-x]存在并且w[i-x]=1，则s[i]=1

②如果w[i+x]存在并且w[i+x]=1，则s[i]=1

③如果以上两种都不符合，则s[i]=0

 

求原01串w，如果不存在输出-1

 

思路：

初始化w全部为1

对于所有s[i]=0，修改w[i-x]、w[i+x]为0

判断是否存在s[i]=1，使得w[i-x]与w[i+x]为0，如果存在，则不存在01串w

如果不存在则输出w

 

代码：

#include<bits/stdc++.h>
#define ll long long
#define maxn (ll)1e3+5
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        string s,ss;
        int x;
        cin>>s;
        cin>>x;
        int n=s.length();
        for(int i=0;i<n;i++)ss+='1';
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                if(i-x>=0)ss[i-x]='0';
                if(i+x<n)ss[i+x]='0';
            }
        }
        bool flag=1;
        for(int i=0;i<n;i++){
            if(s[i]=='1'){
                if((i-x>=0&&ss[i-x]=='1')||(i+x<n&&ss[i+x]=='1'))
                    continue;
                else{
                    flag=0;
                    break;
                }
            }
        }
        if(flag){
            cout<<ss<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
}