Codeforces Round #721 (Div. 2)A. And Then There Were K(位运算,二进制) B1. Palindrome Game (easy version

半个月没看cf 手生了很多(手动大哭) 

 

 Problem - A - Codeforces

题意

给定数字n, 求出最大数字k, 使得  n & (n−1) & (n−2) & (n−3) & ... (k) = 0

题解

&:有0则0

假如n转为二进制共有x位 , 要使&后=0, k的最高位需=0

我们使最高位=0,后面都为1; 那么此数+1=什么

=100000(x-1个0), 这样就能&后=0了

-------------------------------------------------------------------------

结论

k= (1<<x - 1)

1左移x位再-1

 

代码

#include <iostream>

using namespace std;

int main()
{
    int n, t;
    cin >> t;
    while(t --)
    {
        cin >> n;
        int s = 0;
        while(n)
        {
            s ++;
            n >>= 1;
        }
        s --;
        cout << (1 << s) - 1 << endl;
    }
    
    return 0;
}

 

 

Problem - B1 - Codeforces

题意:对一个01回文串,每次有两个操作(1)将一个0变为1,消耗1美元;(2)将字符串翻转,不消耗金钱(条件:  1). 此时不是回文串  2). 上次别人操作没用翻转)当串全为1时游戏结束,花钱少的人胜,问谁胜。

题解:先手初始时为回文, 不能翻转,但只要他改变了一个数,就破坏了回文串的属性,使得后手可以翻转;因此显然大多数情况下后手能让先手多花两美元,从而后手胜。

但也有一些特殊情况,比如一开始串就全为1,那么直接平局;

假如回文串是奇数长度且最中间为0,那么先手还可以操作一下:如果此时只有这中间的一个0,那自然还是输;但假如不是,那么先手把中间的0转换了就先后手易位,两 极 反 转,此时虽然先手多花了1美元,但根据上面的结论,局势转换后后手方可以让先手多花两美元,因此可必胜。

 附: 先手一定会少花2美元原因

假如该串为0000

操作:  A:0100  -->   B:1100   -->   A: 1110  -->B: 翻转成0111   -->   A: 1111

A花费3元, B花费1元

 

代码

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n, t;
    cin >> t;
    while(t --)
    {
        int n, sum = 0;
        string s; bool f1 = 0;
        cin >> n;
        cin >> s;
        int n1 = s.length();
        if(n1 % 2 && s[n/2] == '0')
            s[n/2] = '1', f1 = 1;
            
        for(int i = 0; i < n1/2; ++ i)
            if(s[i] == '0')
                sum ++;
        
        
        if(f1 && sum > 0)
            cout << "ALICE" << endl;
        else if(f1 || !f1 && sum > 0)
            cout << "BOB" << endl;
        else
            cout << "DRAW" << endl;
    }
    
    return 0;
}

部分参考于 Codeforces Round #721 (Div.2)部分题解 - 知乎 (zhihu.com) 

 

上一篇:codeforces A-B Palindrome


下一篇:POJ 3280 Cheapest Palindrome(区间dp)