Codeforces Round 939 (Div. 2) A~E

A.Nene’s Game（循环）

题意：

妮妮发明了一种基于递增序列 $a_1,a_2,\ldots,a_k$ 的新游戏。

在这个游戏中，最初 $n$ 个玩家排成一排。在这个游戏的每一轮中，都会发生以下情况：

妮妮发现第 $a_1$ 、 $a_2$ 、 $\ldots$ 、 $a_k$ 的玩家排成一排。他们会同时被踢出游戏。如果一排中的 $i$ 个玩家应该被踢出游戏，但是一排中的玩家少于 $i$ 个，那么他们就会被跳过。

一旦在某一轮游戏中没有人被踢出游戏，那么所有仍在游戏中的玩家都将被宣布为赢家。

例如，考虑有 $a = [3, 5]$ 名棋手和 $n = 5$ 名棋手的游戏。让棋手按最初排好的顺序依次命名为棋手 $A$ 、棋手 $B$ 、 $\ldots$ 、棋手 $E$ 。那么

在第一轮比赛之前，棋手的排列顺序为 $A BC D E$ 。妮妮发现第 $3$ 和第 $5$ 的球员在一排。他们在第一轮就被踢出局了。
现在棋手们排成 $A B D$ 。妮妮找到了第 $3$ 和第 $5$ 的棋手。第 $3$ 位棋手是棋手 $D$ ，而且一排中没有第 $5$ 位棋手。因此，第二轮只有棋手 $D$ 被踢出局。
在第三轮中，没有人被踢出游戏，所以游戏在这一轮后结束。
宣布玩家 $A$ 和 $B$ 获胜。

妮妮还没有决定最初会有多少人参加游戏。妮妮给了你 $q$ 个整数 $n_1,n_2,\ldots,n_q$ ，你应该针对每个 $1\le i\le q$ 独立回答下面的问题：

如果最初有 $n_i$ 个玩家参加游戏，有多少人会获胜？

分析：

不断循环，如果要删除的位置小于等于剩余的个数，就可以删去该数。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL N = 105;
int a[N];
int k, q;

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> k >> q;
        for (int i = 1; i <= k; i++)
            cin >> a[i];
        while (q--) {
            int n;
            cin >> n;
            while (true) {
                int cnt = 0;
                for (int i = 1; i <= k; i++) {
                    if (n >= a[i])
                        cnt++;
                }
                if (cnt == 0)
                    break;
                n -= cnt;
            }
            cout << n << ' ';
        }
        cout << endl;
    }
    return 0;
}

B.Nene and the Card Game（思维）

题意：

你和妮妮正在玩纸牌游戏。玩这个游戏使用一副有 $2 n$ 张牌的扑克牌。每张牌上都有一个从 $1$ 到 $n$ 的整数，而 $1$ 到 $n$ 的整数正好出现在 $2$ 张牌上。此外，游戏中还有一张放置纸牌的桌子（最初桌子是空的）。

在游戏开始时，这些 $2 n$ 张牌会在你和妮妮之间分配，这样每个玩家都会得到 $n$ 张牌。

之后，你和妮妮轮流进行 $2 n$ 次回合，即从你开始，每人轮流 $n$ 个回合，每个回合

轮到的玩家从手中的牌中选择一张。让 $x$ 成为上面的数字。
如果桌面上已经有一张整数为 $x$ 的牌，则轮到他的玩家会得到 $1$ 点数（否则，他不会得到任何点数）。之后，他将选中的整数为 $x$ 的牌放在桌上。

请注意，回合是公开进行的：每个玩家在每个时刻都能看到桌面上的所有牌。

妮妮非常聪明，所以她总是以最佳方式选牌，以便在游戏结束时（ $2 n$ 轮之后）最大化自己的分数。如果她有几种最佳走法，她会选择在游戏结束时使你的得分最小的走法。

更正式地说，妮妮总是以最佳方式轮流下棋，以便在对局结束时首先使她的得分最大化，其次使你在对局结束时的得分最小化。

假设纸牌已经分发完毕，而你手中的纸牌上写有整数 $a_1,a_2,\ldots,a_n$ ，那么你以最优方式轮流出牌所能得到的最大分数是多少？

分析：

最优策略显然是先出自己手上同个点数有两张的牌，如果对方出了双方都有的点数的牌，跟着出。

这样考虑，最优会变成我们先出手上同个点数有两张的牌，对方也这么出，由于这种牌的个数双方是相同的，轮到我们出牌，对方跟着出相同点数。

最后得分是同个点数有两张的个数。

代码：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            x--;
            a[x]++;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 2)
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

C.Nene’s Magical Matrix（构造）

题意：

魔法少女妮妮有一个 $n\times n$ 矩阵 $a$ ，矩阵中充满了零。矩阵 $a$ 第 $i$ 行的第 $j$ 个元素表示为 $a_{i,j}$ 。

她可以对这个矩阵进行以下两种类型的运算：

类型 $1$ 操作：在 $1$ 和 $n$ 之间选择一个整数 $i$ 以及从 $1$ 到 $n$ 的整数排列 $p_1,p_2,\ldots,p_n$ 。同时为所有 $1\le j\le n$ 指定 $a_{i,j}:=p_j$ 。
类型 $2$ 操作：在 $1$ 和 $n$ 之间选择一个整数 $i$ ，并从 $1$ 到 $n$ 之间选择一个整数的排列 $p_1,p_2,\ldots,p_n$ 。同时为所有 $1\le j\le n$ 指定 $a_{j,i}:=p_j$ 。

妮妮想要最大化矩阵 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$ 中所有数字的和。她要求你找出使这个和最大化的运算方法。由于她不希望进行过多的运算，你应提供一个运算次数不超过 $2 n$ 的解决方案。

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

分析：

手推一下 $n = 3$ 的例子，不难发现最大总和的情况是是依次给 $i$ 行、列赋值 $1,2,3,\dots,n$ 。这一结论可以通过归纳法证明。
然后按照结论构造矩阵即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        LL s = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                s += max(i, j);
            }
        }
        cout << s << ' ' << 2 * n << endl;
        for (int i = n; i >= 1; i--) {
            cout << 1 << ' ' << i;
            for (int j = 1; j <= n; j++) {
                cout << ' ' << j;
            }
            cout << endl;
            cout << 2 << ' ' << i;
            for (int j = 1; j <= n; j++) {
                cout << ' ' << j;
            }
            cout << endl;
        }
    }
    return 0;
}

D.Nene and the Mex Operator（状压）

题意：

妮妮给了你一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$ 。

你可以执行以下操作不超过 $5\cdot 10^5$ 次（可能为零）：

选择 $l$ 和 $r$ 这样的两个整数 $1\le l\le r\le n$ ，计算 $x$ 为 $\operatorname{MEX}(\{a_l,a_{l+1},\ldots,a_r\})$ ，同时设置 $a_l:=x,a_{l+1}:=x,\ldots,a_r:=x$ 。

这里，整数集合 $\{c_1,c_2,\ldots,c_k\}$ 中的 $\operatorname{MEX}$ 被定义为在集合 $c$ 中不出现的最小非负整数 $m$ 。

你的目标是最大化数组 $a$ 中元素的和。找出最大和，并构建一个操作序列来实现这个和。需要注意的是，你不需要最小化这个序列中的操作次数，你只需要在解决方案中使用不超过 $5\cdot 10^5$ 的操作。

分析：

对于一段 $[l, r]$ ，我们要么不变，要么可以通过操作把 $[l, r]$ 段内的 $a [i]$ 全部变成 $r - l + 1$ 。

可以先把 $[l, r]$ 全部变成 $0$ ，再把 $[l, r]$ 变成 ${l-r,l-r-1,l-r-2\dots 0}$ ，使用区间 $[l, r]$ ，最后一步变成 $r - l + 1$ 。

$l - r$ 可以构造 ${l-r-1,l-r-2,\dots 0}$ ，使用区间 $[l, r - 1]$ ，先变成 $r - l + 1$ ，再将 $[l + 1, r - 1]$ 归零。

使用 $D P$ 标记路径即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL mod = 1000000007;
vector<int> a;
vector<pair<int, int>> ans;

void deal(int l, int r) {
    set<int> s(a.begin() + l, a.begin() + r + 1);
    LL mex = 0;
    while (s.count(mex))
        mex += 1;
    for (int i = l; i <= r; i++) {
        a[i] = mex;
    }
    ans.push_back({l, r});
}

void solve(int l, int r) {
    if (l == r) {
        if (a[r] != 0) {
            deal(l, r);
        }
        return;
    }
    int len = r - l + 1;
    int target = len - 1;
    if (a[l] != target) {
        if (a[l] > target)
            deal(l, l);
        solve(l + 1, r);
        deal(l, r);
    }
    solve(l + 1, r);
}

int main() {
    int n;
    cin >> n;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int dp[20]{}, pre[20]{};
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            int len = i - j;
            if (dp[j] + len * len > dp[i]) {
                dp[i] = dp[j] + len * len;
                pre[i] = j;
            }
        }
        if (dp[i - 1] + a[i] > dp[i]) {
            dp[i] = dp[i - 1] + a[i];
            pre[i] = i - 1;
        }
    }
    int pos = n;
    while (pos != 0) {
        int l = pre[pos] + 1;
        if (l != pos || a[l] == 0) {
            solve(l, pos);
            deal(l, pos);
        }
        pos = pre[pos];
    }
    cout << dp[n] << ' ' << ans.size() << endl;
    for (auto [l, r]: ans) {
        cout << l << ' ' << r << endl;
    }
    return 0;
}

E.Nene vs. Monsters（思维）

题意：

妮妮正在与位于一个圆圈中的 $n$ 个怪物战斗。这些怪物的编号从 $1$ 到 $n$ ，第 $i$ ( $1\le i\le n$ )个怪物当前的能量水平是 $a_i$ 。

由于怪物太强大，妮妮决定使用 "攻击你的邻居"法术与它们战斗。当妮妮使用这个咒语时，以下行动会按以下顺序逐一发生：

第 $1$ 个怪物攻击第 $2$ 个怪物；
第 $2$ 只怪物攻击第 $3$ 只怪物；
$\ldots$
第 $(n - 1)$ 只怪物攻击第 $n$ 只怪物
第 $n$ 只怪物攻击第 $1$ 只怪物

当能量等级为 $x$ 的怪物攻击能量等级为 $y$ 的怪物时，防守怪物的能量等级变为 $\max(0,y-x)$ （攻击怪物的能量等级仍然等于 $x$ ）。

妮妮会使用这个咒语 $10^{100}$ 次，并对付那些自己的能量值仍然不为零的怪物。她想让你确定，一旦她使用所述咒语 $10^{100}$ 次，哪些怪物的能量值将不会为零。

分析：

如果连续三个怪物的能量值都是 $(x,y\gt 0)$ ，那么能量值为 $y$ 的怪物将最后"死亡"（能量值为 $0$ ）。

如果连续四只怪物的能量等级为 $(x,y,z,w\gt 0)$ ，并且它们在 $t$ 轮法术后没有死亡，那么 $y$ 将受到至少 $t$ 点伤害， $z$ 将受到至少 $(t-1)+(t-2)+\cdots=O(t^2)$ 点伤害， $w$ 将受到至少 $O(t^3)$ 点伤害。

也就是说，让 $V=\max_{i=1}^n a_i$ ，在 $O(\sqrt[3]{V})$ 个回合后， $x, y, z, w$ 中至少会有一人死亡。

因此，我们可以暴力模拟这个过程，直到没有四个连续存活的怪物为止。

如果连续四个怪物的能量值都是 $(x,y,z\gt 0)$ ， $x$ 将继续存活， $y$ 将最后死亡，并在此之前向 $z$ 造成 $D=(y-x)+(y-2x)+\cdots+(y\bmod x)$ 伤害。因此，只有在 $z\gt D$ 的情况下， $z$ 才会存活。

Tips：事实上，我们可以证明在 $O(\sqrt[k]{V})$ 个回合之后，不会有 $k$ 个连续存活的怪物。让 $k$ 比 $3$ 大，可以进一步降低时间复杂度，但实施和优化的难度会更大，对实际性能影响不大。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 5;
int n, a[MAXN];
bool b[MAXN];

bool check() {
    a[n + 1] = a[1], a[n + 2] = a[2], a[n + 3] = a[3];
    for (int i = 1; i <= n; i++)
        if (a[i] && a[i + 1] && a[i + 2] && a[i + 3])
            return true;
    return false;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (n == 2) {
        while (a[1] && a[2]) {
            a[2] = max(0, a[2] - a[1]);
            a[1] = max(0, a[1] - a[2]);
        }
        b[1] = (a[1] > 0);
        b[2] = (a[2] > 0);
    } else if (n == 3) {
        while (a[1] && a[2] && a[3]) {
            a[2] = max(0, a[2] - a[1]);
            a[3] = max(0, a[3] - a[2]);
            a[1] = max(0, a[1] - a[3]);
        }
        b[1] = (!a[3] && a[1]);
        b[2] = (!a[1] && a[2]);
        b[3] = (!a[2] && a[3]);
    } else {
        while (check()) {
            for (int i = 1; i <= n; i++)
                a[i % n + 1] = max(0, a[i % n + 1] - a[i]);
        }
        for (int i = 1; i <= n; i++)
            b[i] = false;
        auto attack = [&](LL x, LL y) {
            LL k = x / y;
            return (2 * x - (k + 1) * y) * k / 2;
        };
        for (int p = 1; p <= n; p++)
            if (a[p] && a[p % n + 1])
                a[p % n + 1] = max(0, a[p % n + 1] - a[p]);
            else
                break;
        for (int i = 1; i <= n; i++)
            if (!a[i] && a[i % n + 1]) {
                b[i % n + 1] = true;
                b[(i + 2) % n + 1] = (a[(i + 2) % n + 1] > attack(a[(i + 1) % n + 1], a[i % n + 1]));
            }
    }
    int cnt = 0;
    for (int i = 0; i <= n; i++)
        if (b[i])
            cnt++;
    cout << cnt << endl;
    for (int i = 1; i <= n; i++)
        if (b[i])
            cout << i << ' ';
    cout << endl;
}

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