Codeforces Round #721 (Div. 2)

题目链接

A. And Then There Were K

题意

给你一个n，找到最大的k，使得n & (n-1) & (n-2) & ... & k == 0，其中& 表示按位与操作。

分析

首先1&0 = 0，要让最终结果为0，就是让其二进制表示的每位为0，稍加分析可以得出二进制表示为n位的数，其最大的k就是n-1个1组成的二进制数，证明：

正确性： 以1011011为例，从1011011到0111111必然经过1000000，则1011011&1000000 = 1000000，再与一个k = 0111111得到0

最优性： 0111111+1得到1000000，这个数以及这个数到原数之间的所有数相与不能消去最高位的1，所以0111111是最优解

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int cnt = 0;
        while(n) {
            n/=2;
            cnt ++;
        }
        cnt--;
        int ans = 0;
        while(cnt--) ans  = ans * 2 + 1;
        cout << ans <<endl;
    }
    return 0;
}

B. Palindrome Game(博弈+构造)

题意

给你一个由01构成的字符串，每次可以选择两个操作中的一个：

• 操作1：将一个0变为1，花费1美元
• 操作2：将整个字符串翻转，无需花费，如果当前字符串是个回文串或上一轮已经进行此操作，则此次不能选择此操作。

ALICE先手，轮流进行操作，直到字符串中没有0停止，花费最少的获胜，输出获胜方，平局则输出DRAW，保证初始至少有一个0。

本题有easy vision 和hard vision，easy vision初始给的字符串是回文串，hard vision 的任意。

分析

首先来看初始字符串为回文串的情况，我们可以把1都略去只看所有的0，分为偶数个和奇数个两种情况，分别讨论：

• 偶数个0：由于一开始就是回文，所以先手必须选择操作1，Bob可以根据Alice的选择镜像选择更改1，使得整个串一直保持回文状态，直到只剩下一个0的时候，Bob选择进行翻转，Alice只能选择操作1，故Alice的花费会比Bob多2，先手必输。
• 奇数个0：Alice先手将最中间的0修改为1，保持回文性质，Bob也要任取一个0进行修改，接下来Alice只要镜像模仿Bob来选择修改，保证每次修改后字符串还是回文串，一直到只剩下一个0的时候，Alice进行翻转操作，Bob只能修改，最终Bob花费会比Alice多1，先手必胜。但要注意特判一下只有一个0的情况，此时先手必输。

如果初始时字符串不是回文串，我们令cnt1表示01对的数量（如x0xx1x算一个01对，即导致字符串不是回文串的0的个数），故cnt1表示了将字符串变成回文串需要的最少次数，cnt2表示除了cnt1中出现过的0外所有的0的数量（即不会导致字符串不是回文串的0的个数，如101101中cnt2 = 2）。对于Alice来说，最有利的情况就是一直不是回文串，那么Alice每次都可以进行翻转操作，而Bob必须进行操作1。所以，Bob的最优策略就是尽快让字符串变成回文串，所以Bob需要以cnt1那么多美元的代价使得字符串变成一个回文串。

• 当cnt1为0时直接按照初始为回文串讨论即可。
• 当cnt1为1时，Bob花费1美元使得字符串变成回文串并且Alice还是先手并且此时字符串处于回文状态。
  • 如果cnt2为1，则Alice必须选择操作1，游戏结束，平局。
  • 如果cnt2大于1，如果cnt2为偶数，则Alice在第一轮的时候就花费1使得字符串变成回文，那么局面就变成了Bob先手，还有偶数个0的情况，由上文讨论可知，先手会比后手至少多花费2，即Bob会比Alice多花费2，算上一开始Alice的1美元花费，Alice的花费还是少于Bob，Alice胜。如果cnt2为奇数，则Alice在第一轮直接选择操作2，由上面可知，Bob的最优策略是花费1使得字符串变成回文，于是局面变成了Alice先手，有奇数个0，由上文讨论可知先手必胜，即Alice必胜，更别说Bob一开始还有一点花费了，由此可知，cnt2大于1时Alice必胜。
• 当cnt1大于1时，则Bob要让字符串变成回文的花费大于1，结合上面的讨论可以发现，无论cnt2为多少Alice是必胜的。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while (t--) {
        string s;
        int n;
        cin >> n;
        cin >> s;
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < s.size(); i++) {
            if(s[i] != s[n-i-1] && s[i] == '0') cnt1++;
            else if(s[i] == '0')cnt2++;
        }
        if(cnt1 == 0) {
            if (cnt2 % 2 == 1 && cnt2 != 1)
                puts("ALICE");
            else
                puts("BOB");
        }else {
            if(cnt1 == 1 && cnt2 == 1) puts("DRAW");
            else puts("ALICE");
        }

    }
    return 0;
}

C. Sequence Pair Weight（思维+组合数学）

题意

给你n个数字组成的一个序列，定义一个序列的值为 pair<i,j> 的个数，其中 pair<i,j> 表示一对下标，满足 i < j , ai = aj，要求找出所有子串的权值和。

分析

最直观的暴力做法是找到每个子串，然后统计每个子串的值进行相加，时间复杂度为 O(n^2)，铁T，又想了想能不能用DP维护一段序列，没啥思路。还是得多角度去看问题，既然不能去计算每个子串，那么换个切入点，从每个数字下手，计算每个数字的贡献值，最后全部累加就是答案，如果可行的话那么时间复杂度将达到 O(n) 级别。

考虑每个数字可能会给哪些子串贡献答案，比如x1xx1xx，（x表示任意数字），这一对1可以对以下的子串贡献答案：

1xx1
1xx1x
1xx1xx
x1xx1
x1xx1x
x1xx1xx

可以发现，其贡献度就是2 * 3，即第一个1包括自己到左边的字符个数 * 第二个1包括自己到右边的数字个数，公式为 i*(n-i+1)，下标从0开始。为了保证不重复计算，我们可以从序列的第一个数字开始，找其左边和其值相同的所有数字，计算每一对的贡献度，这里可以用一个前缀和来进行优化，具体看代码。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int a[maxn];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        unordered_map<int,LL> mp;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += mp[a[i]] * (n-i+1);
            mp[a[i]] += i;
        }
        cout << ans <<endl;
    }
    return 0;
}