Educational Codeforces Round 137
https://codeforces.com/contest/1743
D. Problem with random tests
给你长 n的0/1
问它的两个子串(连续)的 bit or 的最大为多少
范围
n 1e6
4s
512mb
随机生成数据 不支持 hack
我的思路
首先一个肯定是原串,为了最高位1
那么剩下的一定是从最前连续1里面开始的
1 | 11100001.... |
那么为了尽量高位填1, 如果len1 <= len0, 那就是都从第一个1开始,长度差为len1
1 | 11110001..... |
但如果len1 > len0
那么可以选的 有从头开始,和从偏移一个开始, 这两个都会or掉第一节的0, 但是后面的情况是未知的
看着禁止hack 似乎需要上string hash的意思?
如果暴力找就是 候选的开头在
1 | 11111110001.... |
然后对于原串, 找每个0的位置, 反过来在候选中找是否为1, 不为1则剔除候选,
这样感觉要n^2
有点想后缀数组排序, 但问题是, 这里只有原串为0的对应位置需要是1(参与比较), 而原串已经是1的则可以忽略
不会啊,干