CF1392 A-E

CF1392A

给定长度为 $n$ 的序列 $a$。

如果 $a_i \neq a_{i+1}$ 则可以合并 $a_i$ 和 $a_{i+1}$,合并的元素后值为它们的和，总元素个数减一。

求进行若干次合并操作后最后元素个数的最小值。

$1 \le n \le 2 \times 10 ^ 5$，$1 \le a_i \le 10^9$。

对于序列的最大值，除非两边点值都和它相同，否则它就可以一直合并直到只剩一个。

所以分类讨论一下，是不是所有元素都相等。

CODE

#include <bits/stdc++.h>
using namespace std;
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
int a[200010];
 
int main() {
    for (int T = read(); T --;) {
        int n = read(), id = 0, same = 1;
        for (int i = 1; i <= n; i ++) {
            a[i] = read();
            if (i != 1 && a[i - 1] != a[i]) same = 0;
        }
        if (same) printf("%d\n", n);
        else puts("1");
   }
    return 0;
}

CF1392B

给定一个长度为 $n$ 的序列 $a$，输出执行以下操作 $k$ 次后的序列 $a$ ：

• 找到序列元素的最大值 $d$，将每个 $a_i$ 变为 $d - a_i$；

$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^18$。

手动模拟一下就能发现，$k$ 是奇数时 $a_i = d - a_i$，偶数时 $a_i = a_i - g$，$g$ 是最小值。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define INF (1e9 + 7)
int a[200010];
 
signed main() {
    for (int T = read(); T --;) {
        int n = read(), k = read(), Mx = -INF, Mn = INF;
        for (int i = 1; i <= n; i ++) {
            a[i] = read();
            Mx = max(Mx, a[i]);
            Mn = min(Mn, a[i]);
        }
        if (k & 1) {
            for (int i = 1; i <= n; i ++) {
                printf("%lld ", Mx - a[i]);
            }
        } else {
            for (int i = 1; i <= n; i ++) {
                printf("%lld ", a[i] - Mn);
            }
        }
        puts("");
    }
    return 0;
}

CF1392C

给定一个长度为 $n$ 的序列 $a$，有以下操作：

• 选择一个区间 $[l,r]$，将其中的元素都加上 $1$；

求使 $a$ 单调不减的最小操作次数。

答案就是 $\sum_{i=2}^n max(b_{i-1}-b_i,0)$。

对于 $i \in [2, n]$，如果 $b_i < b_{i-1}$，那么肯定要以 $l=i$ 操作 $b_{i-1}-b_i$ 次。右端点肯定是 $n$ 最优，否则可能使得 $b_r > b_{r+1}$，徒增了操作次数。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define INF (1e9 + 7)
int a[200010];
 
signed main() {
    for (int T = read(); T --;) {
        int n = read(), res = 0;
        for (int i = 1; i <= n; i ++) {
            a[i] = read();
            res += max(0ll, a[i - 1] - a[i]);
        }
        printf("%lld\n", res);
    }
    return 0;
}

让我 1min AC 了，开心

CF1392D

在一个起床战争局面中，有 $n$ 支队伍形成环状，第 $i$ 支在第 $i + 1$ 队伍左边，$n$ 在 $1$ 左边。用一个长度为 $n$ 的由 L、R 组成的字符串给出每支队伍在攻击它的左边还是右边。合法攻击满足以下条件：

• 若只有 $b$ 攻击 $a$，$a$ 必须攻击 $b$；

• 若没有或有两支队伍攻击 $a$，$a$ 可以随意攻击左或右。

求最少改变多少个队伍的攻击状态，使序列合法。

$1 \le n \le 2 \times 10^5$。

唯一的不合法状态：只有 $b$ 攻击 $a$，而 $a$ 没有攻击 $b$ 。转换成字符串就是 LLL 和 RRR。

问题转换成改变多少个 L 和 R，使环形字符串不含 LLL 和 RRR。扫一遍瞎搞搞即可。

代码写得贼丑。

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
char s[200010];
 
signed main() {
    for (int T = read(); T --;) {
        int n = read(), res = 0;
        scanf("%s", s + 1);
        int st = 1, i = 0;
        while (s[st] == s[1]) st ++;
        if (st > n) {
            if (n == 1) puts("0");
            else if (n == 2) puts("0");
            else if (n == 3) puts("1");
            else {
                res = n / 3;
                if (res * 3 != n) res ++;
                printf("%lld\n", res);
            }
            continue;
        }
        i = st;
        do {
            int j = i, nw = 1;
            while (s[(j == n ? 1 : j + 1)] == s[i] && (j == n ? 1 : j + 1) != st) {
                nw ++;
                j ++;
                if (j > n) j = 1;
            }
            res += nw / 3;
            i = j + 1;
            if (i > n) i = 1;
        } while (i != st);
        printf("%lld\n", res);
    }
    return 0;
}

CF1392E

交互题。认真读题。

给定 $n$，要求你构造（注意）一个 $n \times n$ 的矩阵，其中的元素 $a_{i,j} \in [0,10^16]$。

输出这个矩阵后会给你 $q$ 次询问，每次询问给出一条 $(1,1)$ 到 $(n,n)$ 路径（只能向下或右）上所有元素的和，要求你输出这条路径。你的路径与答案不相同即会 WA，这意味着路径是唯一的。

$1 \le n \le 25$，$0 \le a_{i,j} \le 10^{16}$。

让你构造一个矩阵没有两条路径值相同，显然构造题，容易想到和二进制有关。

注意到 $10^{16} \approx 2^{50}$，走过的点的数量 $2n-1 < 50$，诶，对上了，有戏。

考虑将用二进制第 $x$ 位表示经过时第 $x$ 个点是向下还是向右了。

这样的话，就要保证向下和向右一个是 $0$, 一个是 $2^x$。所以对于所有 $i+j=x$，即所有可能在第 $x$ 步经过的点，一条对角线，让 $0$ 和 $2^x$ 交替出现即可。（以上可能有加一减一的问题。）

比如 $n=4$ 时的一个矩阵：

0  0  0   0
2  4  8   0
0  0  16  0
8  0  32  0

CODE

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return f ? -x : x;
}
 
#define N 110
 
int n, s[N], a[N][N];
 
signed main() {
    int n = read();
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            int x = i + j;
            a[i][j] = (s[x] ++ & 1ll) << x - 2;
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            printf("%lld ", a[i][j]);
        } 
        puts(""), fflush(stdout);
    }
    for (int T = read(); T --;) {
        int s = read(), x = 1, y = 1;
        while (x != n || y != n) {
            printf("%lld %lld\n", x, y), fflush(stdout);
            int st = s & (1ll << (x + y - 1ll));
            (st == a[x + 1][y] && x < n) ? x ++ : y ++;
        }
        printf("%lld %lld\n", x, y), fflush(stdout);
    }
    return 0;
}

TIP

使用位运算时别忘了 1ll，这两天被坑了几次了 。