• 欢迎光临~

Educational Codeforces Round 140 D

开发技术 开发技术 2022-12-17 次浏览

D. Playoff

题链
我们观察样例 或者自己想一想就可以知道 这个答案一定是一段连续的数字
那么我们考虑如何确定这个答案的上下界即可
而且只要给出的字符串s有一个0 那么我们的最大数字一定不存在
要是有两个0呢
比如:3 001这个样例
我们想让大的尽可能留在后面
但是8第一轮无论如何都会被消灭
而7要是能通过第一轮的话也只能和8配对 在第二轮也会被消灭掉
6也可以模拟一下也是如此
但是5是可以的
我们换成3 000
发现只有1才能存活
就发现每次0
就会让上界减去 1 2 4 ....
下界同理
不懂咋证明 代码如下

void solve(){
    cin>>n>>s;
    int l=1,r=1<<n,a=0,b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            l+=1<<a;
            a++;
        }else{
            r-=1<<b;
            b++;
        }
    }
    for(int i=l;i<=r;i++)cout<<i<<' ';
}
程序员灯塔
转载请注明原文链接:Educational Codeforces Round 140 D
喜欢 (0)