B. A Tide of Riverscape

题目链接

Codeforces Round #487 (Div. 2)--B. A Tide of Riverscape

题解

中档题。这题有点意思,给定一个由'0','1','.'组成的字符串,将所有'.'变成'0'或'1',使得整个字符串不以p位循环。
先尝试以p位循环将字符串补齐,如果某一位没出现过'1',则补上'1',否则补上'0',补齐后直接判断是否是p位循环即可。

代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
int n, p;
int a[2005];
string out;
int main() {
    cin >> n >> p;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1')a[i%p] |= 4;
        else if (s[i] == '0')a[i%p] |= 2;
        else if (s[i] == '.')a[i%p] |= 1;
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '.') {
            if (a[i%p] & 2)out = out + '1';
            else { 
                out = out + '0'; 
                a[i%p] |= 2;
            }
        }
        else out = out + s[i];
    }
    memset(a, 0, sizeof(a));
    for (int i = 0; i < s.size(); i++) {
        if (out[i] == '1')a[i%p] |= 4;
        else if (out[i] == '0')a[i%p] |= 2;
        else if (out[i] == '.')a[i%p] |= 1;
    }
    for (int i = 0; i <= p; i++) {
        if (a[i%p] == 6) {
            cout << out;
            return 0;
        }
    }
    cout << "No";
}

标签: strings, constructive algorithms

添加新评论