Codeforces Round 951 (Div. 2) A~E

A.Guess the Maximum（枚举）

题意：

爱丽丝和鲍勃想出了一个相当奇怪的游戏。他们有一个整数数组 $a_1,a_2,\ldots,a_n$ 。爱丽丝选择了某个整数 $k$ 并告诉了鲍勃，然后就发生了下面的事情：

鲍勃选择两个整数 $i$ 和 $j$ ( $1\le i\lt j\le n$ )，然后找出整数 $a_i,a_{i+1},\ldots,a_j$ 中的最大值；
如果得到的最大值严格大于 $k$ ，则爱丽丝获胜，否则鲍勃获胜。

请帮助爱丽丝找出保证她获胜的 $k$ 的最大值。

分析：

为了最大值尽可能小，爱丽丝会选择所有区间最大值的最小值 $- 1$ ，那么选择的连续子串越短越优。注意到区间长度越大，这个区间的最大值是随着它不减的，所以如果鲍勃要让爱丽丝选的最小的话，区间长度一定是 $2$ 。

枚举所有长度为 $2$ 的连续子串，求出它们最大值的最小值，然后减去 $1$ 输出即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1e6 + 10;

LL n, a[N];

void solve() {
    LL ans = 1e9;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i > 1)
            ans = min(ans, max(a[i], a[i - 1]));
    }
    cout << ans - 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B.XOR Sequences（数学）

题意：

给你两个不同的非负整数 $x$ 和 $y$ 。考虑两个无穷序列 $a_1,a_2,a_3,\ldots$ 和 $b_1,b_2,b_3,\ldots$ ，其中

$a_n=n\oplus x$
$b_n=n\oplus y$

$x\oplus y$ 表示整数 $x$ 和 $y$ 的按位异或运算。

例如，有了 $x = 6$ 之后，序列 $a$ 的前 $8$ 个元素将如下所示： $[7,4,5,2,3,0,1,14,\ldots]$ 。请注意，元素的索引以 $1$ 开始。

你的任务是找出序列 $a$ 和 $b$ 的最长公共子段 $^\dagger$ 的长度。换句话说，求某个 $i,j\ge 1$ 的最大整数 $m$ ，使得 $a_i=b_j,a_{i+1}=b_{j+1},\ldots,a_{i+m-1}=b_{j+m-1}$ 。

$^\dagger$ 序列 $p$ 的一个子段是序列 $p_l,p_{l+1},\ldots,p_r$ ，其中 $1\le l\le r$ 。

分析：

考虑性质，发现对于给定的数 $a, b$ ，设 $c n t$ 表示其二进制下后 $k$ 位（从第 $0$ 位开始）全部相同的最大的 $k$ ，则答案为 $2^{cnt}$ 。

比如对于样例57、37：

57:111001
37:100101

其后的 $2$ 位 $01$ 相等且第 $2$ 位不相等，则答案为 $2^2=4$ 。

所以我们直接扫描二进制位找 $c n t$ 即可。

证明过程：

设 $KaTeX parse error: Undefined control sequence: \oplusx at position 2: a\̲o̲p̲l̲u̲s̲x̲=b\oplusy$ 且 $a\oplus(x−1)\neq b\oplus(y−1)$ 。

则这样的 $x$ 与 $y$ 一定是后面 $c n t$ 位全为 $0$ ，其余位单独构造使其满足上述条件的数字。

那么根据定义， $a, b$ 的第 $c n t$ 位一定不相等，这等价于如果加上大于等于 $2^{cnt}$ 的数字则会发生进位，影响前面构造的结果。

所以加上的数字属于闭区间 $0,2^{cnt}−1]$ ，一共 $2^{cnt}$ 个，即长度为 $2^{cnt}$ 。

证毕。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int MOD = 998244353;

void solve() {
    LL a, b, ans = 0;
    cin >> a >> b;
    for (int i = 0; i < 32; ++i) {
        if ((a >> i & 1) != (b >> i & 1))
            break;
        ans++;
    }
    ans = (1 << ans);
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C.Earning on Bets（思维）

题意：

有人提议让您玩一个游戏。在这个游戏中，有 $n$ 种可能的结果，对于每一种结果，您都必须下注一定整数的硬币。如果第 $i$ 个结果是赢的，您将获得与您在该结果上的投注额相等的硬币，再乘以 $k_i$ 。请注意， $n$ 个结果中正好有一个结果是赢的。

你的任务是决定如何分配硬币，以便在任何一个结果中都能获胜。更正式地说，你对所有结果下注的硬币总数必须严格小于每个可能的获胜结果所得到的硬币数。

分析：

对于第 $i$ 个结果，每下注 $\frac{1}{k_i}$ 个硬币就能期望获得 $1$ 个硬币，所以我们可以得到：设 $S=\sum^n_{i=1}\frac{1}{k_i}$ ，当 $S \geq 1$ 时，本题无解，当 $S < 1$ 时，每种结果下注 $\frac{1}{k_i}$ 个硬币即可。但题目要求每种结果下注的硬币数必须是整数。所以要把每个 $\frac{1}{k_i}$ 乘上 $lcm(k_1,k_2,…,k_n)$ 。由于 $k_i≤20$ ，所以 $lcm(k_1,k_2,…,k_n)$ 的最大值是 $l c m (5, 7, 9, 11, 13, 16, 17, 19) = 232792560$ 。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int MOD = 998244353;
LL a[55];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << "1" << endl;
        return;
    }
    if (n >= 20) {
        cout << "-1" << endl;
        return;
    }
    LL LCM = a[1] * a[2] / gcd(a[1], a[2]);
    for (int i = 3; i <= n; i++) {
        LCM = LCM * a[i] / gcd(LCM, a[i]);
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += LCM / a[i];
    }
    if (ans >= LCM) {
        cout << "-1" << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        cout << LCM / a[i] << " ";
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D.Fixing a Binary String（模拟）

题意：

给你一个长度为 $n$ 的二进制字符串 $s$ ，由 $0$ 和 $1$ 组成。您可以执行以下操作一次：

选择一个整数 $p$ ( $1\le p\le n$ )。
反转子串 $s_1 s_2\ldots s_p$ 。完成此步骤后，字符串 $s_1 s_2\ldots s_n$ 将变为 $s_p s_{p-1}\ldots s_1 s_{p+1}s_{p+2}\ldots s_n$ 。
然后，将字符串 $s$ 向左循环移动 $p$ 次。这一步之后，初始字符串 $s_1s_2\ldots s_n$ 将变成 $s_{p+1}s_{p+2}\ldots s_n s_p s_{p-1}\ldots s_1$ 。

例如，如果用 $p = 3$ 对字符串 $110001100110$ 进行操作，第二步操作后，字符串将变为011001100110，第三步操作后，字符串将变为001100110011。

如果满足两个条件，字符串 $s$ 就会被称为 $k - p ro p er$ ：

$s_1=s_2=\ldots=s_k$ ;
$s_{i+k}\neq s_i$ 为任意 $i$ ( $1\le i\le n-k$ ).

例如，在 $k = 3$ 中，字符串 $000$ 、 $111000111$ 和 $111000$ 是 $k - p ro p er$ ，而字符串 $000000$ 、 $001100$ 和 $1110000$ 则不是。

给你一个整数 $k$ ，它是 $n$ 的整除。请找出一个整数 $p$ ( $1\le p\le n$ )，使得在进行运算后，字符串 $s$ 变成 $k$ （或确定这是不可能的）。需要注意的是，如果字符串最初是 $k - p ro p er$ ，那么仍然需要对它进行一次操作。

分析：

按照原题中的方案按顺序判断前缀是否是合法 $k - p ro p er$ 串的前缀，直到当前前缀不合法或者判断到 $n + 1$ 停止。

如果判断到 $n + 1$ ，那么说明原串是 $k - p ro p er$ 串。选择 $p = n$ 将一整个串翻转即可。

否则，找到一个删掉该前缀后满足后面的串存在至少有 $k$ 个连续值的最长合法前缀进行操作，然后判断操作后的串是否为 $k - p ro p er$ 串即可。

因为如果操作后的串不为 $k - p ro p er$ 串，那么换一个位置操作就一定会使得该不合法前缀存在或者操作后的串前 $k$ 个值不合法，所以这种情况下操作是唯一的。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 1010100;
char s[N];
LL n, a[N], b[N], k;

bool finalcheck(LL x) {
    LL i, j = 0;
    for (i = x + 1; i <= n; i++) {
        j++;
        b[j] = a[i];
    }
    for (i = x; i >= 1; i--) {
        j++;
        b[j] = a[i];
    }
    for (i = 2; i <= k; i++) {
        if (b[i] != b[i - 1]) {
            return false;
        }
    }
    for (i = k + 1; i <= n; i++) {
        if (b[i] == b[i - k]) {
            return false;
        }
    }
    return true;
}

void solve() {
    LL lst = 1, t, pos;
    cin >> n >> k >> s + 1;
    for (int i = 1; i <= n; i++) {
        a[i] = s[i] - '0';
    }
    a[0] = -1;
    for (int i = n; i >= 1; i--) {
        if (a[i] != a[i - 1]) {
            break;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (a[i] != a[i - 1]) {
            t = i - lst;
            pos = i - 1;
            lst = i;
            if (t != k) {
                if (t < k) {
                    if (finalcheck(pos)) {
                        cout << pos << endl;
                        return;
                    } else {
                        cout << "-1" << endl;
                        return;
                    }
                } else if (t <= k * 2) {
                    if (finalcheck(pos - k)) {
                        cout << pos - k << endl;
                        return;
                    } else {
                        cout << "-1" << endl;
                        return;
                    }
                } else {
                    cout << "-1" << endl;
                    return;
                }
            }
        }
    }
    if (finalcheck(n)) {
        cout << n << endl;
        return;
    } else {
        cout << "-1" << endl;
        return;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E.Manhattan Triangle（数学）

题意：

两点 $x_1,y_1)$ 和 $x_2,y_2)$ 之间的曼哈顿距离定义为

$x_1-x_2|+|y_1-y_2|$

我们把平面上每对曼哈顿距离相等的三点称为一个曼哈顿三角形。

给你一组成对的不同点和一个偶数整数 $d$ 。你的任务是从给定的集合中找出由三个不同点组成的曼哈顿三角形，其中任意一对顶点之间的曼哈顿距离等于 $d$ 。

分析：

观察发现，在每个曼哈顿三角形中都有两个点，使得 $x_1-x_2|=|y_1-y_2|$ 。

先用 $(x + y)$ 的值来分配所有的点。

对于每个点 $(x, y)$ 用lower_bound在相应集合中找到点 $(x + d /2, y - d /2)$ 。然后我们必须找到第三个点：它可以在 $(x + y + d)$ 或 $(x + y - d)$ 对角线上。它们在 $x$ 坐标上的边界分别是 $[x + d /2, x + d]$ 和 $[x - d /2, x]$ 同样使用lower_bound找到。

代码：

#include<bits/stdc++.h>

using namespace std;
const int MOD = 998244353;
const int MAXC = 1e5;
const int MAXD = 4e5 + 10;

set<pair<int, int>> diag[MAXD];

void solve() {
    int n, d;
    cin >> n >> d;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        x[i] += MAXC;
        y[i] += MAXC;
    }
    bool found = false;
    {
        for (int i = 0; i < n; i++) {
            diag[x[i] + y[i]].insert({x[i], i});
        }
        for (int i = 0; i < n; i++) {
            auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, -1});
            if (it1 == diag[x[i] + y[i]].end() || it1->first != x[i] + d / 2)
                continue;
            if (x[i] + y[i] + d < MAXD) {
                auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, -1});
                if (it2 != diag[x[i] + y[i] + d].end() && it2->first <= it1->first + d / 2) {
                    cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << endl;
                    found = true;
                    break;
                }
            }
            if (x[i] + y[i] - d >= 0) {
                auto it2 = diag[x[i] + y[i] - d].lower_bound({x[i] - d / 2, -1});
                if (it2 != diag[x[i] + y[i] - d].end() && it2->first <= it1->first - d / 2) {
                    cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << endl;
                    found = true;
                    break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            diag[x[i] + y[i]].erase({x[i], i});
        }
    }
    if (!found) {
        for (int i = 0; i < n; i++) {
            y[i] -= 2 * MAXC;
            diag[x[i] - y[i]].insert({x[i], i});
        }
        for (int i = 0; i < n; i++) {
            auto it1 = diag[x[i] - y[i]].lower_bound({x[i] + d / 2, -1});
            if (it1 == diag[x[i] - y[i]].end() || it1->first != x[i] + d / 2)
                continue;
            if (x[i] - y[i] + d < MAXD) {
                auto it2 = diag[x[i] - y[i] + d].lower_bound({x[i] + d / 2, -1});
                if (it2 != diag[x[i] - y[i] + d].end() && it2->first <= it1->first + d / 2) {
                    cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << endl;
                    found = true;
                    break;
                }
            }
            if (x[i] - y[i] - d >= 0) {
                auto it2 = diag[x[i] - y[i] - d].lower_bound({x[i] - d / 2, -1});
                if (it2 != diag[x[i] - y[i] - d].end() && it2->first <= it1->first - d / 2) {
                    cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << endl;
                    found = true;
                    break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            diag[x[i] - y[i]].erase({x[i], i});
        }
    }
    if (!found) {
        cout << "0 0 0" << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}