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时游戏结束，花钱少的人胜，问谁胜。

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

但也有一些特殊情况，比如一开始串就全为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 Round #721 (Div. 2)A. And Then There Were K(位运算,二进制) B1. Palindrome Game (easy version)(博弈论)

题意

题解

结论

代码

代码

最新文章

热门文章