CF1743D Problem with Random Tests

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

这题比较考察做题的经验

因为或操作对一个数的值只增不减,所以我们要往高位考虑.我们截取的第一段需要满足最高位的1在原串中也是最高位的1,这样才能做到别的所有的数都不如他大.截取的第二段需要能首先满足把第一段截取出来的数的最高位0给搞成1,然后再继续考虑把低位的0也尽可能搞成1.

这道题说了所有测评数据随机,所有位上为‘1’和‘0’的概率都是1/2.

我们找截取的第一段非常容易,只需要把原串所有的前导0全部去掉即可(如果全部都是0那么就做个特判输出0即可).那么截取第二段我们需要寻找第一段中从高往低第一个出现的0.根据数据随机的这个定义,我们假设前面99位都是1,100位是0.那么这种数据出现的概率就是1/(2^100),他已经明确告诉你只有40组测试样例,那么这种数据出现的概率已经近似为0.那么0出现的位置一定不会太靠后.如果你是一位做题经验丰富的老手,那么你很容易就能想到只用枚举前100位的情况即可!但是这种做法,只适用于你知道有多少组测试数据的题目,如果测试数据有多少个不清楚,那这种方法成功的概率就很小.

至于两个字符串整体做或操作,用bitset可以很好的解决.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin>>n>>s;
    auto elz = [&](string s) ->string
    {
        if(s.find('1')!=string::npos)
        return s.substr(s.find('1'));
        else return "0";
    };
    s=elz(s);
    bitset<1000010> b1(s),b2(s);
    string ans=b1.to_string();
    for(int i=1;i<=100;i++)
    {
        ans=max(ans,(b1|(b2>>i)).to_string());
    }
    cout<<elz(ans)<<'\n';

}