问题简述

        给定一个串，要求找到它的两个子串（可以有重叠），使得两个子串表示的二进制数按位或的结果最大。

        题目链接：https://codeforces.com/contest/1743/problem/D

思路

        “随机生成”、“不允许Hack”。这样的字眼提示非常明显了——本题大概率需要利用随机性质来保证复杂度/贪心的正确性等。

        首先不难发现两个朴素的事实：1）给定字符串的前导零对于问题而言毫无意义；2）让其中一个子串从首个非零位延展到末位一定是最优解的一部分。这样问题转化为，假设原字符串删去前导零之后的字符串为，求：

        其中是的一个子串。这里将字符和其表示的二进制数混用了，但不会带来理解的困难。

        即然问题是按位或，那么关键的肯定是的的位置，假设首个的位置是。由于必然以开头，因此不难发现，取时，按位或能将的处的转变为。由于越高位位权越大，那么如果某子串不能将的处的转变为，则一定比更差。这就意味着，最优的子串必须以前个中的某一个开头，且长度至少为。

        由此，可以得到一个复杂度为的暴力的枚举算法。但由于生成数据的随机性，我们得到的分布如下：

        那么，不小于概率地，该算法的实际复杂度为：，取时，已经能以超过的概率通过全部测试点（40个），而此时复杂度还不到，可以通过本题。

后记

        本场的实况录屏地址为https://www.bilibili.com/video/BV1bG4y1n7oH。

        没过E/F呢（E大概需要动态规划吧），还需要继续加油。