(CF1400C)Binary String Reconstruction

发表于 分类于 ，

原题链接

思路:

对于串 s 的某个 0\(s_{i}\), 如果对应的 \(w_{i-x}\) 和 \(w_{i+x}\) 存在，那么这两个位置上一定是 0.

对于串 s 的某个 1\(s_{i}\), 则对应的 \(w_{i-x}\) 和 \(w_{i+x}\) 一定有一个存在且为 1.

根据上面两个定理，可以得到一个算法:

通过串 s 中的 0 确定 w 中 0 的位置，然后使用定理二判断是否合法， 若合法则剩余位置全部填 1.

代码:

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
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) {
        string s;
        int x;
        cin >> s >> x;
        int n = s.size();
        string a(n,'x');    //用'x'表示未填充
        bool isans(true);   //是否合法
        /* 填充0 */
        for(int i(0);i<n;++i) {
            if(s[i]=='0') {
                if(i>=x) {
                    if(a[i-x]=='x') {
                        a[i-x] = '0';
                    }
                }
                if(i<n-x) {
                    if(a[i+x]=='x') {
                        a[i+x] = '0';
                    }
                }
            }
        }
        for(int i(0);i<n;++i) {
            if(s[i]=='1') {
                int cnt(0); //判断对应位置的w是否有至少一个1
                if(i>=x) {
                    if(a[i-x]=='x') {   //若未填充可直接填1
                        a[i-x] = '1';
                        ++cnt;
                    } else if(a[i-x]=='1') {
                        ++cnt;
                    }
                }
                if(i<n-x) {
                    if(a[i+x]=='x') {   //同上
                        a[i+x] = '1';
                        ++cnt;
                    } else if(a[i+x]=='1') {
                        ++cnt;
                    }
                }
                if(cnt==0) {    //如果不合法
                    isans = false;
                    break;
                }
            }
        }
        for(int i(0);i<n;++i) { //剩余位置全部填1
           if(a[i]=='x') {
               a[i] = '1';
           }
        }
        if(!isans) {
            cout << -1 << endl;
            continue;
        } else {
            cout << a << endl;
        }
    }
    return 0;
}