D. Problem with Random Tests(暴力&贪心)

D. Problem with Random Tests(暴力&贪心)

$s_1=s$，显然是最优的，因为答案不会更坏。

$s_2$ 取前缀答案不会更劣。

不如$s|(1101),s|(0101)$ 比$s|(101)$好。

因此枚举前缀。

因此我们只需找到第一个0的位置即可。

注意到数据随机，所以前$30$位都为$1$的概率为$\frac{1}{2^{30}}$很小。所以枚举前30位即可。

时间复杂度：$O(30n)$

#include
using namespace std;
int n;
string s;
int main() {
    cin >> n >> s;
    string an = s;
    for(int i = 1; i < 30; i++) {
        string t = s;
        for(int j = i; j < n; j++) t[j] |=  s[j - i];
        if(an < t) an = t;
    }
    int st = 0;
    while(st < n - 1 && s[st] == '0') st++;
    cout << an.substr(st) << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17