题目大意

https://codeforces.com/contest/1400/problem/C
给定长度为n的二进制串w和一个整数x，我们可以按照以下规则构造出字符串s。

$1. 如果i>x且w_{i-x}='1', 则s_i='1'$
$2. 如果i+x<=n且w_{i+x}='1', 则s_i='1'$
$3. 如果以上2个条件都不成立则s_i='0'$

现在事先给出s, 问是否存在一个w可以推出s。

分析&思路

对于w[i]要么取0，要么取1，直接想到思路就是用2sat表示。

分析一下2sat建立边的过程。

对于一个坐标i如果s[i]=1 且2边x距离都有字符，那么w[i-x],w[i+x]这2个字符中至少要有1个1。
对于一个坐标i如果s[i]=0 且2边x距离都有字符，那么w[i-x],w[i+x]这2个字符都要为0。
如果一个坐标i只有1边x距离有字符，那么w[i-x] or w[i+x] = s[i]。

然后跑一遍tarjan, 求出一个可行解w。
最后要根据w恢复一下s查看是否相等。

AC代码


#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>

using namespace std;


const int N = 6e5 +10;
const int E = 6e6+10;
// 边属性
class Edge {
public:
    int toVertex;
    int nextEdge;
};

// 点属性
class Node {
public:
    int head;
    int indu;
};

class Graph {
public:
    Edge edges[E];
    Node nodes[N];
    int usedEdge=0;
    Graph() {
        usedEdge = 0;
    }

    void initEdge(int n) {
        for(int i=0;i<=n;++i) {
            nodes[i].head=-1;
            nodes[i].indu  = 0;
        }
        usedEdge = 0;
    }

    void addEdge(int a, int b) {
        if(a==b) return;
        edges[usedEdge].nextEdge = nodes[a].head;
        nodes[a].head = usedEdge;
        edges[usedEdge].toVertex = b;
        nodes[b].indu++;
        usedEdge++;

        // cout<<"add edge: "<<a<<","<<b<<endl;
    }

        
    int dfn[N], low[N];
    stack<int> st;
    int deep, sum;
    int color[N];

    void initTarjan(int n) {
        deep = 0;
        sum=0;
        memset(dfn, 0,sizeof(int)*n);
        memset(low, 0,sizeof(int)*n);
        memset(color, 0,sizeof(int)*n);

    }

    void tarjan(int u) {
        dfn[u] = ++deep;
        low[u] = deep;
        st.push(u);

        for(int i=nodes[u].head;i>=0;i = edges[i].nextEdge) {
            int v = edges[i].toVertex;
            if(!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if(!color[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if(dfn[u]==low[u]) {
            color[u] = ++sum;
            while(st.top()!=u) {
                int v = st.top();
                st.pop();
                color[v]=sum;
            }
            st.pop();
        }
    }

    map<int, int> loc;

    bool topo(int n, bool deb) {
        queue<int>qu;
        for(int i=1;i<=n;++i) {
            if(nodes[i].indu==0) {
                qu.push(i);
            }
        }
        int l=0;
        while(!qu.empty()) {
            int f = qu.front();
            loc[f]=++l;
            qu.pop();

            for(int i=nodes[f].head;i>=0;i=edges[i].nextEdge) {
                int v = edges[i].toVertex;
                nodes[v].indu--;
                if(nodes[v].indu==0) qu.push(v);
            }
        }

        if(deb) cout<<l<<endl;
        return l==n;
    }
};

Graph og;

void either(int i, bool si, int j, bool sj) {
    og.addEdge(i*2+(si^1), 2*j+sj);
    og.addEdge(j*2+(sj^1), 2*i+si);
}

void must(int i, bool sel) {
    og.addEdge(i*2+(sel^1), i*2+sel);    
}

char s[N];

void solve() {
    int x;
    scanf("%s", s);
    scanf("%d", &x);
    int n = strlen(s);
    vector<int> w(n);
    og.initEdge(2*n+10);
    // cout<<x<<endl;
    for(int i=0;i<n;++i) {
        if(i-x>=0 && i+x<n) {
            if(s[i]=='1') {
                either(i-x, 1, i+x, 1);
                continue;
            }
        }
        
        if(i-x>=0) {
            must(i-x, s[i]-'0');
        }

        if(i+x<n) {
            must(i+x, s[i]-'0');
        }
    }

    og.initTarjan(2*n +10);
    for(int i=0;i<2*n; ++i) {
        if(!og.dfn[i])og.tarjan(i);
    }

    for(int i=0;i<n;++i) {
        if(og.color[2*i] == og.color[i*2+1]){
            puts("-1");
            return;
        }
        if(og.color[2*i]<og.color[i*2+1])w[i]=0;
        else w[i]=1;
    }

    for(int i=0;i<n;++i) {
        int d=0;
        if(i-x>=0 && w[i-x]==1)d=1;
        if(i+x<n && w[i+x]==1)d=1;
        if(d!=s[i]-'0') {
            puts("-1");
            return ;
        }
    }

    for(int i=0;i<n;++i) {
        printf("%d", w[i]);
    }
    puts("");
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        solve();
    }
    return 0;
}
/*

 */