题目链接:https://codeforces.ml/contest/1743/problem/D
bitse 类似数组,用于存储二进制位 ,可以直接进行位运算
lambda表达式,之前看过,但是没有系统的总结。
https://blog.csdn.net/qq_37085158/article/details/124626913
来看题,一个随机测试的题,从题目中也可以看到,所以几乎不存在卡特例现象,这是在做题中需要想到的。整体概率是1/2,属于一个正态分布的现象,比较均匀一些,对于1e6的数据来讲。
大意是 给出一个随机01子串。你可以获取子串s1 s2 使得s1 | s2的值最大。
做法是先把前0全部截去,然后s1一定是本身,这个傻子都能看出来=.=。s2需要去考量一下,从哪里开始截,首先可以肯定的是s2一定可以是很长的,也就是可以只考虑左端点,暴力一定次数即可,因为很难出现很多1连在一起的现象。对于s2的一个短串,不满足s1中较前的0,就可以直接pass掉。
最后感觉也不是很难的题,但是对于我来说确实少遇的偏题
code:
void solve() { int n; string s; cin>>n>>s; auto erase_leading_zeros=[](string s){ int first = 0; while(s[first] == '0' && first < s.length() - 1) first ++; return s.substr(first); }; s = erase_leading_zeros(s); //因为将string作为参数,因此采用了lambda表达式进行传参 bitset<1000005> b1(s), b2(s);//二进制的容器,可以存储二进制位<长度> 将字符串转换到bitset,可以进行位运算操作 string ans = b1.to_string(); for(int i=1;i<=50;i++) ans = max(ans, (b1 | (b2>>i)).to_string());//max字符串进行比较字符'1'要不'0'大 cout<<erase_leading_zeros(ans); }