欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

题目大意

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

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

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

分析&思路

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

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

1. 对于一个坐标i如果s[i]=1 且2边x距离都有字符，那么w[i-x],w[i+x]这2个字符中至少要有1个1。
2. 对于一个坐标i如果s[i]=0 且2边x距离都有字符，那么w[i-x],w[i+x]这2个字符都要为0。
3. 如果一个坐标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;
}
/*

 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。