Codeforces Round 951 (Div.2) 个人题解

A. Guess the Maximum

如果任意子段的最大值都要大于 $k$，只需要保证所有长度为 $2$ 的子段的最大值大于 $k$ 即可。因此答案为：

\[\min_{1 \le i < n}\left(\max(a_i,a_{i+1}) - 1\right)\]

时间复杂度: $O(n)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int t, n, a[N];

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int main() {
    t = read();
    while (t--) {
        int ans = INT_MAX;
        n = read();
        for (int i = 1; i <= n; i++) a[i] = read();

        for (int i = 1; i < n; i++) {
            ans = min(ans, max(a[i], a[i + 1]) - 1);
        }

        printf("%d\n", ans);
    }
    return 0;
}

B. XOR Sequences

思路

假设给定的 $x,y$ 可以找到对应的 $n,m$ 满足 $n \oplus x = m \oplus y$，如果 $n,m$ 在自增之后依然满足这个条件，那么 $n,m$ 每一个对应的二进制位必须同时改变或同时不变。

对于这个条件，我们可以找到一组特殊的解：$x=n,\ y=m$，这样使得等式的异或值为 $0$。然后，我们将 $n,m$ 相同的二进制位全部变为 $0$，这样就得到了一组最小的解。

这个时候，$n,m$ 能够自增的次数是最多的，公共子序列也是最长的。

要使得自增的时候等式成立，那么只有 $n,m$ 对应的二进制数末尾连续的 $0$ 能够被改变。假设 $n,m$ 末尾分别有 $c_1,c_2$ 个 $0$，那么答案就是：

\[2^{\min(c_1,c_2)}\]

又因为 $n \oplus m = x \oplus y$，令 $z = x \oplus y$，我们要求的结果其实就是：

\[z \& (-z)\]

时间复杂度: $O(1)$。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

int t;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

signed main() {
    t = read();
    while (t--) {
        int x = read(), y = read(), z = x ^ y, ans = 0;
        printf("%lld\n", z & (-z));
    }
    return 0;
}

C. Earning on Bets

思路

我们很容易发现，获胜结束后收回的硬币数一定是 $k_i$ 的倍数。本题是一道构造题，所以我们不妨设最后收回的硬币数是所有 $k$ 的最小公倍数 $L$，然后下注的硬币数为：

\[x_i = \frac{L}{k_i}\]

最后再统计下注的硬币数 $T$：

\[T = \sum_{i=1}^{n} x_i\]

比较 $T$ 和 $L$ 之间的大小关系。

选择最小公倍数 $L$ 的原因：收回的硬币数一定是 $k_i$ 的倍数，那么一定是 $L$ 的倍数；若选择 $L$ 能够满足题目要求，选择 $L$ 的倍数并将 $x_i$ 扩大相应的倍数也一定能够满足题目要求。

选择 $x_i=\frac{L}{k_i}$ 来构造的原因：

若 $x_i$ 过大，会使 $T$ 增大，可能会使 $T < L$ 变成 $T \ge L$；
若 $x_i$ 过小，使得当第 $i$ 种结果被判定为获胜时，$T$ 减小，可能会使 $T < L$ 变成 $T \ge L$。

时间复杂度: $O(n\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;

int t, n, k[55], x[55];

#define int long long

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int lcm(int a, int b) { return a * b / (__gcd(a, b)); }

signed main() {
    t = read();
    while (t--) {
        n = read();
        for (int i = 1; i <= n; i++) k[i] = read();

        int sum = 1, total = 0;

        for (int i = 1; i <= n; i++) {
            sum = lcm(sum, k[i]);
        }

        for (int i = 1; i <= n; i++) total += sum / k[i];

        if (total >= sum) puts("-1");
        else {
            for (int i = 1; i <= n; i++) printf("%d ", sum / k[i]);
            putchar('\n');
        }
    }
    return 0;
}