Codeforces Round 953 (Div. 2) A~F

A.Alice and Books（思维）

题意：

爱丽丝有 $n$ 本书。第 $1$ 本书包含 $a_1$ 页，第 $2$ 本书包含 $a_2$ 页， $\ldots$ 第 $n$ 本书包含 $a_n$ 页。爱丽丝的操作如下：

她把所有的书分成两个非空的书堆。这样，每本书最后都会被恰好放在两堆书中的一堆里。
爱丽丝阅读每一堆中编号最高的一本书。

爱丽丝非常喜欢阅读。帮她找出把书分成两堆后，她最多可以阅读的总页数。

分析：

观察题目很容易看出来，最后一个数字是必须取的，用前 $n - 1$ 个数字的最大值加上最后一个值求和即可。

代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 110;
int a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int ans = a[n];
    int ans2 = 0;
    for (int i = 1; i < n; ++i) {
        ans2 = max(ans2, a[i]);
    }
    cout << ans + ans2 << endl;
}

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

B.New Bakery（数学）

题意：

鲍勃决定开一家馒头店。开业当天，他烤出了 $n$ 个可以出售的馒头。通常一个馒头的价格是 $a$ 个硬币，但为了吸引顾客，鲍勃组织了以下促销活动：

鲍勃选择某个整数 $k$ ( $0\le k\le\min(n,b)$ )。
鲍勃以修改后的价格出售第一批 $k$ 个馒头。在这种情况下，售出的 $i$ （ $1\le i\le k$ ）个馒头的价格是 $(b - i + 1)$ 个硬币。
剩下的 $(n - k)$ 个馒头以每个 $a$ 个硬币的价格出售。

注意 $k$ 可以等于 $0$ 。在这种情况下，鲍勃将以每个 $a$ 硬币的价格出售所有的馒头。

帮助鲍勃确定出售所有 $n$ 个馒头所能获得的最大利润。

分析：

首先当 $a \geq b$ 时， $k$ 取 $0$ 即可。

当 $a\lt b$ 时，要想使利润尽可能大，必须满足前 $k$ 天的利润都比 $a$ 大，即要满足 $b - k \geq a$ 。可以得出 $k$ 最大为 $b - a$ ，然后计算即可。

注意 $k$ 需要满足不超过 $min (n, b)$ 的限制，所以最终 $k = min (n, b - a)$ ，答案为 $\frac{(b+b−k+1)k}{2}+(n−k)a$ 。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

void solve() {
    LL n, a, b;
    cin >> n >> a >> b;
    if (a >= b) {
        cout << n * a << endl;
        return;
    }
    LL k = min(n, b - a);
    cout << (b + b - k + 1) * k / 2 + a * (n - k) << endl;
}

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

C.Manhattan Permutations（构造）

题意：

让我们把排列 $^{\dagger}$ 的曼哈顿值 $p$ 表示为 $|p_1-1|+|p_2-2|+\ldots+|p_n-n|$ 的值。

例如，对于排列 $[1, 2, 3]$ ，曼哈顿值为 $∣1 - 1∣ + ∣2 - 2∣ + ∣3 - 3∣ = 0$ ，而对于排列 $[3, 1, 2]$ ，曼哈顿值为 $∣3 - 1∣ + ∣1 - 2∣ + ∣2 - 3∣ = 2 + 1 + 1 = 4$ 。

给你整数 $n$ 和 $k$ 。请找出长度为 $n$ 的排列 $p$ 使其曼哈顿值等于 $k$ ，或者确定不存在这样的排列。

$^{\dagger}$ 长度为 $n$ 的排列是一个数组，由 $n$ 个不同的整数组成，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1, 3, 4]$ 也不是一个排列（ $n = 3$ ，但数组中有 $4$ ）。

分析：

首先我们可以发现，排列 $p$ 的哈曼顿值一定为偶数，不存在为奇数的情况。

因此无解的情况有两种：

$k$ 为奇数或者
超过排列 $p$ 的最大哈曼顿值

对于有解的情况，考虑构造。
首先，令我们要得到的排列 $p$ 为单调递增的，也就是 $p_i=i(1≤i≤n)$ ，那么此时 $p$ 的哈曼顿值为 $0$ 。很明显，如果在此基础上交换两个数 $x, y$ ，那么 $p$ 的哈曼顿值便会增加 $2 \times ∣ x - y ∣$ 。也就是说，可以将一些数字两两配对，由于它们所产生的贡献值是互不干扰的，所以相当于是将 $\frac{k}{2}$ 拆分成若干个不超过 $n - 1$ ，且互不相等的数的和。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL N = 200010;
const LL MOD = 998244353;
LL a[N];

void solve() {
    LL n, k;
    cin >> n >> k;
    if (k % 2 == 1)
        cout << "No" << endl;
    else {
        LL ans = 0;
        for (LL i = 1, j = n; i <= n; i++, j--) {
            a[i] = i;
            ans += abs(j - i);
        }
        if (k > ans)
            cout << "No" << endl;
        else {
            LL x = k / 2;
            for (LL i = 1, j = min(x, n - 1);; i++) {
                swap(a[i], a[i + j]);
                x -= j;
                j = min(x, n - 2 * i - 1);
                if (!x)
                    break;
            }
            cout << "Yes" << endl;
            for (LL i = 1; i <= n; i++)
                cout << a[i] << " ";
            cout << endl;
        }
    }
}

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

D.Elections（贪心）

题意：

伯兰正在举行选举。有 $n$ 名候选人参加选举，编号从 $1$ 到 $n$ 。第 $i$ 名候选人有 $a_i$ 名粉丝会投票给他。此外，还有 $c$ 人对自己喜欢的候选人举棋不定，我们姑且称他们为 “举棋不定者”。未决定的人会把票投给编号最小的候选人。

获得最高票数的候选人赢得选举，如果多个候选人获得相同的最高票数，则其中票数最低的候选人获胜。

您觉得这些选举太无聊且难以预测，因此决定将一些候选人排除在外。如果您不允许 $i$ 号候选人参加选举，那么他的所有 $a_i$ 个粉丝都会变得犹豫不决，并将票投给编号最小的候选人。

你很想知道，从 $1$ 到 $n$ 的每个 $i$ 中，第 $i$ 号候选人要想赢得选举，至少需要排除多少个候选人。

分析：

直接把 $c$ 加到 $a_1$ 上，之后求出 $a$ 中最靠前的最大值编号 $k$ ，显然 $k$ 的答案为 $0$ 。

考虑其他 $x$ 的答案。由于 $a_x$ 本身不是最大值，即使是排除目前最大的 $a_k$ ，这一部分也会加到编号最小的 $a_i$ 上，最大值一定不降。所以至少要将 $x$ 之前的 $x - 1$ 个人全部排除，才能使 $x$ 为编号最小，增加 $a_x$ 让其最大。

所以维护 $a$ 的前缀和 $s$ ，若 $s_x≥a_k$ ，只需要把前面全去掉即可，答案为 $x - 1$ 。否则需要把前面全去掉，并且把 $x$ 后面的最大值 $a_k$ 也去掉，答案为 $x$ 。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL N = 2e5 + 10;
const LL MOD = 998244353;
LL n, c, a[N], s[N];

void solve() {
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[1] += c;
    LL maxx = 1;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
        if (a[maxx] < a[i])
            maxx = i;
    }
    for (int i = 1; i <= n; i++) {
        if (i == maxx) {
            cout << "0" << " ";
        } else {
            if (s[i] >= a[maxx]) {
                cout << i - 1 << " ";
            } else {
                cout << i << " ";
            }
        }
    }
    cout << endl;
}

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

E.Computing Machine（贪心、数学）

题意：

萨沙有两个长度相同的二进制字符串 $s$ 和 $t$ ，长度为 $n$ ，由字符"0"和"1"组成。

还有一台计算器可以对长度相同的二进制字符串 $a$ 和 $b$ 进行两种运算 $k$ ：

如果 $a_{i}=a_{i+2}=0$ ，则可以赋值 $b_{i+1}:=1$ ( $1\le i\le k-2$ )。
如果 $b_{i}=b_{i+2}=1$ ，则可以赋值 $a_{i+1}:=1$ ( $1\le i\le k-2$ )。

萨沙对下面的问题产生了兴趣：如果我们考虑字符串 $a=s_ls_{l+1}\ldots s_r$ 和字符串 $b=t_lt_{l+1}\ldots t_r$ ，那么使用计算器最多可以在字符串 $a$ 中得到多少个"1"字符。由于萨沙非常好奇但很懒惰，所以由你来回答他感兴趣的几对字符串 $l_i,r_i)$ 的问题。

分析：

对于区间，寻找最优操作方案，我们贪心地考虑，先用 $s$ 的 $0$ 增加 $t$ 的 $1$ ，再用 $t$ 的 $1$ 使 $s$ 的 $1$ 变多，这样做一定是最优的，保证了第一步之后 $t$ 中的 $1$ 最多，从而最终 $s$ 中的 $1$ 也最多。

接着我们考虑每一位会怎样被改变。若 $s_i$ 被变为 $1$ ，需要 $t_{i−1}=1$ ，同时 $t_{i+1}=1$ 和 $t$ 的这两位又会受到 $s_{i−2},s_i,s_{i+2}$ 的影响，所以对于每一位 $s_i$ ，都只会受到 $[i - 2, i + 2]$ 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 $s$ 求前缀和。对于询问长度不超过 $4$ 的情况暴力操作求解。超过 $4$ 时由于 $[l + 2, r - 2]$ 只受区间 $[l, r]$ 内的影响，答案不变，记录下原来的答案，再单独对 $[l, l + 4]$ 操作并记录前两位的答案，然后对 $[r - 4, r]$ 操作并记录后两位的答案，最后三部分相加即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 2e5 + 10;
LL n, q, pre[N], s[N], t[N], t1[N], t2[N];
char ss[N], st[N];

void deal(int l, int r) {
    int len = r - l + 1;
    for (int i = l; i <= r; i++) {
        t1[i - l + 1] = s[i];
        t2[i - l + 1] = t[i];
    }
    for (int i = 1; i + 2 <= len; i++) {
        if (!t1[i] && !t1[i + 2])
            t2[i + 1] = 1;
    }
    for (int i = 1; i + 2 <= len; i++) {
        if (t2[i] && t2[i + 2])
            t1[i + 1] = 1;
    }
    for (int i = 1; i <= len; i++)
        t1[i] += t1[i - 1];
}

void solve() {
    cin >> n >> ss >> st >> q;
    for (int i = 1; i <= n; i++) {
        s[i] = ss[i - 1] - '0';
        t[i] = st[i - 1] - '0';
    }
    deal(1, n);
    for (int i = 1; i <= n; i++)
        pre[i] = t1[i];
    while (q--) {
        LL l, r;
        cin >> l >> r;
        if (r - l < 4) {
            deal(l, r);
            cout << t1[r - l + 1] << endl;
        } else {
            int res = pre[r - 2] - pre[l + 1];
            deal(l, l + 4);
            res += t1[2];
            deal(r - 4, r);
            res += (t1[5] - t1[3]);
            cout << res << endl;
        }
    }
}

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

F.Large Graph（并查集）

题意：

给定一个长度为 $n$ 的数组 $a$ 。我们来构造一个大小为 $n\times n$ 的方阵 $b$ ，其中第 $i$ 行包含了循环右移 $(i - 1)$ 的数组 $a$ 。例如，对于数组 $a = [3, 4, 5]$ ，得到的矩阵是

$b=\begin{bmatrix}3&4&5\\5&3&4\\4&5&3\end{bmatrix}$

让我们构建下面的图形：

该图包含 $n^2$ 个顶点，每个顶点对应矩阵中的一个元素。我们把元素 $b_{i,j}$ 对应的顶点记为 $(i, j)$ 。
我们将在顶点 $i_1,j_1)$ 和 $i_2,j_2)$ 之间画一条边，如果 $|i_1-i_2|+|j_1-j_2|\le k$ 和 $\gcd(b_{i_1,j_1},b_{i_2,j_2})\gt 1$ ，其中 $\gcd(x,y)$ 表示整数 $x$ 和 $y$ 的最大公约数)。

你的任务是计算所得图形中的连通块数 $^{\dagger}$ 。

$^{\dagger}$ 图中的连通块是一个顶点集合，在这个集合中，任何顶点都可以通过边到达其他顶点，如果在这个集合中添加任何其他顶点，都会违反这一规则。

分析：

题目保证 $k \geq 2$ ，说明斜着相邻的格子如果 $g c d > 1$ ，必定连边，很明显每个 $a_i$ 在循环移位之后分成的至多两条全是 $a_i$ 的斜线，所以除了数字为 $1$ 的情况，对角线的斜线一定同属一个连通块。

相邻两条斜线的距离是 $1$ ，由此我们可以把二维问题转为一维。使用 $l o g$ 分解质因数，预处理每个数的质因子，对于每个质因数找到上一次出现的位置，如果距离 $\leq k$ 就有边，并查集维护连通性，特判 $1$ 的情况即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 2e6 + 10;
int p[N], s[N], tot, k, a[N], lst[N], fa[N];

void init(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!s[i])
            s[i] = p[++tot] = i;
        for (int j = 1; j <= tot && p[j] <= n / i; ++j) {
            s[i * p[j]] = p[j];
            if (!(i % p[j]))
                break;
        }
    }
}

int n;
vector<int> used;
bool vis[N];
LL ans;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    if (find(x) != find(y))
        fa[fa[x]] = fa[y];
}

void solve() {
    cin >> n >> k;
    for (int i = n; i < n + n; ++i) {
        cin >> a[i];
        a[i - n] = a[i];
    }
    int tmp = n;
    n = (n << 1) - 1;
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        while (x != 1) {
            int now = s[x];
            int pre = lst[now];
            if (pre && i - pre <= k)
                merge(i, pre);
            lst[now] = i;
            while (!(x % now))
                x /= now;
            if (!vis[now]) {
                vis[now] = true;
                used.push_back(now);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 1)
            ans += tmp - abs(tmp - i);
        else if (find(i) == i)
            ++ans;
    }
    cout << ans << endl;
    ans = 0;
    for (int x: used) {
        vis[x] = false;
        lst[x] = 0;
    }
    used.clear();
}

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