CF2200 Codeforces Round 1084 (Div. 3) 题解 图解 超详细版

A. Eating Game

题意：

有$n(1\le n\le 10)$位玩家围绕桌子玩游戏，第i位玩家有$a_i(1\le a_i\le 10)$道菜可以吃。玩家轮流吃菜，轮到第$i$位玩家时，如果他还有剩余的菜，那么他需要吃一道菜，然后第 $(i\mathrm{mod}n)+1$ 名玩家继续，直到所有的菜都被吃完，吃到最后一道菜的玩家被认为是赢家，确定可能成为赢家的数量。

题解：

容易发现，最后成为赢家的一定是菜数量最多的玩家，因为游戏是按顺序来的，每转一圈，所有玩家的菜数减一，换句话说，如果一个玩家有$a_i$道菜，那么至少需要转$a_i-1$圈（在这个玩家处开始，可以少转一圈），假设只有一个玩家有着最多的菜数，那么无论如何一定是他赢。

如果多个玩家有相同的菜数，那么谁会赢呢？假设他们分别是$p_1,p_2,p_3\dots$，菜数是相同的$a_{p_1}$,我们可以指定某个玩家获胜，例如让$p_1$获胜：我们只需令开始的人是$p_1$后面那个，那么转$a_{p_1}$圈后，最后一个吃菜的人一定是$p_1$，并且其余的$p_2,p_3\dots$一定都把$a_{p_1}$道菜吃完了。

所以我们可以任意指定最多菜数的人获胜，故可能成为赢家的玩家数量就是最多菜数的玩家数量。

代码

#include <bits/stdc++.h>
using namespace std;
void work()
{
/*
n: 人数
INF: int的无穷大
maxval: 记录最多的菜数是几
maxcnt: 记录最多菜数出现了几次
*/
int n;
const int INF = 0x7f7f7f7f;
int maxval = –INF, maxcnt = 0;

// 读入
scanf("%d", &n);

for (int i = 1; i <= n; i++)
{//边读入边处理，不需要保存
int t;
scanf("%d", &t);
if (t > maxval)
{// 超过了历史最大值，更新maxval并重置maxcnt
maxval = t;
maxcnt = 1;
}
else if (t == maxval)
{// 等于历史最大值， maxcnt++
maxcnt++;
}
// 小于历史最大值没有用
}

// 输出
printf("%d\\n", maxcnt);
return;
}
int main()
{
/*T: 共有T组数据*/
int T;
scanf("%d", &T);
while (T—)
{
work();
}
return 0;
}

B. Deletion Sort

题意：

AksLolCoding 正在对一个由 n 个正整数组成的数组 a 进行游戏。每一轮操作遵循以下规则：

• 如果数组 a 是非递减的，游戏结束。
• 否则，AksLolCoding 可以选择数组中的任意一个元素并将其移除。

请你求出游戏结束时，数组中可能剩余的元素数量的最小值。

补充说明：若对于数组所有满足 1≤i≤m−1 的下标 i，都有 ai​≤ai+1​（其中 m 是当前数组的长度），则称该数组是非递减的。

题解：

本题关键是想到：我们可以保留一个长度为2的递减子序列，删除其他元素，最后两个元素二选一删除即可，这样剩余元素数量为1。（不可能全部删完，因为长度为一的数组一定是非递减的，游戏会直接结束）

示例 $\{2,4,3,5,7,11,9\}$

当然，如果数组一开始就是非递减的，我们就没有操作的机会了，直接游戏结束。

代码：

#include <bits/stdc++.h>
using namespace std;
void work()
{
/*
n: 数组数字个数
la: 记录上个读入数字的大小
flag: 标记数组是否存在递减子段
*/
int n;
int la = 0;
bool flag = false;

scanf("%d", &n);
for (int i = 1; i <= n; i++)
{// 这个可以边读入边处理，因为只和上一个元素比大小就可以判断递减
int t;
scanf("%d", &t);
if (t < la)
{// 发现递减
flag = true;
la = t;
}
else
{// 非递减，更新下la
la = t;
}
}

// 根据flag的值分类输出答案
if (flag == true) // 一定可以删掉其他的非递减，最后二选一删一个
printf("1\\n");
else // 没操作空间了，直接输出数组长度
printf("%d\\n", n);
return;
}
int main()
{
int T;
scanf("%d", &T);
while (T—)
{
work();
}
return 0;
}

C. Specialty String

题意：

AksLolCoding 在玩一个关于长度为 $n(1\le n\le 5000)$ 的字符串 s 的游戏。一开始，字符串 s 只由小写英文字母组成。

每一回合，AksLolCoding 可以选择一对下标 (i,j) 满足：

• $1\le i<j\le n$
• $s_i=s_j\ne \ast$
• 且在 i 和 j 之间的所有字符 $s_k（i<k<j）$都必须是 ∗

如果不存在这样的 $(i,j)$，游戏结束。否则，AksLolCoding 会把 $s_i$​ 和 $s_j$​ 都变成 ∗。游戏结束后，当且仅当字符串里所有字符都变成 ∗ 时，AksLolCoding 获胜。

请你判断：AksLolCoding 是否有可能获胜。

注：∗ 就是 ASCII 码为 42 的星号字符。

题解：

用栈模拟即可，入栈时若和栈顶字符一致则弹出，如果最后栈是空的则获胜，否则不获胜。

考虑一下为什么这样可行：如果存在子串长这个样子->$abab$，一定没法消掉，能消的只有$abba$这样嵌套的，或者$aaaa$这样多个相同的。对于前者，消除顺序固定；对于后者，虽然消除顺序多样，但题目只要求判断是否获胜，所以用栈模拟，找出一种可行的消除顺序即可。

代码

#include <bits/stdc++.h>
using namespace std;
void work()
{
/*
n: 字符串长度
c: 读入的单个字符
stk: 处理栈，相同字符弹出，否则压入
*/
int n;
char c;
stack<char> stk;

scanf("%d", &n);
getchar(); // 注意读掉换行符
while (n—)
{
c = getchar();
if (!stk.empty() && stk.top() == c) // 栈非空且和栈顶相同
stk.pop();
else // 否则压入
stk.push(c);
}
if (stk.size() == 0) // 栈空说明所有都配对了
printf("yes\\n");
else
printf("no\\n");
return;
}
int main()
{
int T;
scanf("%d", &T);
while (T—)
{
work();
}
return 0;
}

D. Portal

题意：

给定一个长度为 $n$ 的排列${}^{\text{∗}}$ $p$。在位置 $x$ 和 $y$ 处各有一个传送门（$x<y$）。

位于位置 $i$ 的传送门，初始时在数组的第 $i$ 个元素和第 $i+1$ 个元素之间。特别地：

• 若 $i=0$，传送门在数组第一个元素之前；
• 若 $i=n$，传送门在数组最后一个元素之后。

你可以任意多次执行以下两种操作之一：

用 $\mathcal{O}$ 表示传送门。例如，若 $p=[3,\mathcal{O},4,\mathcal{O}]$：

• 对左、右传送门分别使用操作 1，得到数组 $[\mathcal{O},4,\mathcal{O},1]$ 和 $[3,\mathcal{O},2,\mathcal{O}]$。
• 对左、右传送门分别使用操作 2，得到数组 $[3,\mathcal{O},2,\mathcal{O}]$ 和 $[3,1,\mathcal{O},4,\mathcal{O}]$。

求使用这些操作能得到的字典序最小${}^{\text{†}}$ 的排列。注意：传送门不影响排列的字典序比较。

${}^{\text{∗}}$ 长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 每个整数恰好一次的数组。

${}^{\text{†}}$ 排列 $a$ 字典序小于排列 $b$，当且仅当存在下标 $i$，使得对所有 $1\le j<i$ 都有 $a_j=b_j$，且 $a_i<b_i$。

题解：

容易发现，传送门将数组分成了里外两部分，两种操作不会将数组元素跨部分移动。对于里面部分，元素顺序可以滚动，对于外面部分，元素相对顺序不会改变，但可以调整里部分在数组中的位置。

我们的目标是使整体字典序最小。考虑一下，其实就是保证里部分字典序最小，再挑一个外部分最合适的位置将里部分插入。从左到右遍历外部分，里部分的首元素首次小于外部分的元素时，我们就找到了最优插入位置。

代码：

#include <bits/stdc++.h>
using namespace std;
void work()
{
/*
n: 排列长度
x: 第一个传送门的位置
y: 第二个传送门的位置
INF: int的无穷大
vec: 读入的排列
veca: x左y右的部分，即外部分
vecb: x有y左的部分，即里部分
minval_b: vecb中的最小值
minpos_b: vecb中最小值的位置
flag: 判断是否输出过vecb部分
*/
int n, x, y;
const int INF = 0x7f7f7f7f;
int minval_b = INF, minpos_b = 0;
bool flag = false;

// 读入
scanf("%d%d%d", &n, &x, &y);
vector<int> vec(n + 1), veca, vecb;
for (int i = 1; i <= n; i++)
{
scanf("%d", &vec[i]);
}

// 拆分为两个部分
for (int i = 1; i <= n; i++)
{
if (i <= x || i > y)
veca.push_back(vec[i]);
else
{
vecb.push_back(vec[i]);
if (minval_b > vec[i])
{ // 记录一下最小值及其位置
minval_b = vec[i];
minpos_b = vecb.size() – 1;
}
}
}

// 遍历a部分，看时机输出b部分
for (int i = 0; i < veca.size(); i++)
{
if (flag == false && veca[i] > minval_b)
{ // b部分没输出过，并且当前的a值大于b部分最小值
flag = true; // 标记输出过了
for (int j = 0; j < vecb.size(); j++)
{
printf("%d ", vecb[(j + minpos_b) % vecb.size()]);
}
}
printf("%d ", veca[i]);
}
if (flag == false)
{ // 如果没输出过b部分，在最后输出一下
for (int j = 0; j < vecb.size(); j++)
{
printf("%d ", vecb[(j + minpos_b) % vecb.size()]);
}
}
printf("\\n");
}
int main()
{
int T;
scanf("%d", &T);
while (T—)
{
work();
}
return 0;
}

E. Divisive Battle

题意：

爱丽丝和鲍勃在一个初始包含 $n$ 个正整数的数组 $a$ 上玩游戏，爱丽丝先手。

每一轮玩家操作时：

• 如果数组 $a$ 非递减，游戏立即结束。
• 否则，该玩家可以选择数组中的一个元素 $x$，并选择满足 $1<y,z<x$ 且 $x=yz$ 的正整数 $y,z$，将 $x$ 替换为两个数 $y$ 和 $z$（可按任意顺序放在原位置）。
• 若无法进行任何操作，游戏结束。

游戏结束时：

• 如果数组 $a$ 是非递减的，则 鲍勃获胜。
• 否则 爱丽丝获胜。

假设两人都采取最优策略，判断谁会获胜。

${}^{\ast }$ 非递减的定义：对所有 $1\le i\le m-1$ 有 $a_i\le a_{i+1}$，其中 $m$ 是数组当前长度。

题解：

因为数组非递减就立刻结束游戏，所以开始时数组如果是非递减，则直接判Bob获胜。否则考虑是否存在数字可以拆成两个因子相乘，容易发现，如果包含不同大小的质因子，可以将含大质因子的因子放在前面，含小质因子的因子放在后面，假设游戏能持续进行，最后拆到不能再拆，大质因子位置肯定比小质因子靠前，一定不满足数组非递减，那么Alice获胜。但是考虑到拆开的两个因子可能直接让Bob获胜了，例如

$$\{1、70、11\}⟶\{1、7、10、11\}$$

我们可以单独拆一个最小质因子到右边，剩的都放左边，这样无论怎么拆，最后肯定是Alice获胜。

$$\{1、70、11\}⟶\{1、35、2、11\}$$

以上是存在数字包含不同质因子的情况，假设所有数字都是唯一质因子。那么除非最后拆完是非递增的，否则Alice获胜。

$$\{4、16、9\}⟶\{2、2、4、4、3、3\}$$

有同学可能会考虑到下面这样的情况，看起来是Bob获胜

$$\{4、16、9\}⟶\{4、4、4、9\}$$

但我们可以通过Alice的操作来避免这样情况的出现，只需Alice每一步先从最后一个可拆的数字中拆一个质因子出来即可。

$$\{4、16、9\}⟶\{4、16、3、3\}$$

这样无论Bob怎么操作都不可能获胜了。

代码：

注：我的写法把各种情况混合在一起判断了，逻辑比较复杂，称不上好代码，如果看不懂可以分情况讨论，把情况分开写，会更好理解一些。

#include <bits/stdc++.h>
using namespace std;
void work(){
/*
n: 数组长度
flag: 标记存在一个数有多个质因子，或分解成质因子的最终序列不是非递减的
flag1: 标记最开始的数组是否是非递减的
la: 记录读入初始数组过程的上一个数字是几
vec: 所有数字分解成质因子后组成的数组
*/
int n;
bool flag = false;
bool flag1 = false;
int la = 0;

// 读入
scanf("%d",&n);
vector<int>vec,vec1(n+1);
for(int i = 1;i <= n;i ++){ // 读入时顺便判断一下是否是非递减的
scanf("%d",&vec1[i]);
if(vec1[i] < la) flag1 = true;
else la = vec1[i];
}
if(flag1 == false){ // 一打开始就是非递减的，直接Bob获胜
printf("Bob\\n");
return ;
}
for(int i = 1;i <= n;i ++){ // 依次判断每个数字，判断是否存在数字有至少两个质因子
int t = vec1[i];
int cnt = 0; // 记录质因子的个数
for(int j = 2;j*j <= t;j ++){
if(t%j == 0){
vec.push_back(j); // 将分解出的质因子放到vec中
cnt ++; // 质因子个数加一
while(t%j == 0) // 把当前因子除完
t /= j;
}
}
if(t != 1){ // 如果最后不是1，说明还有一个质因子
vec.push_back(t);
cnt ++;
}
if(cnt > 1) flag = true; // 质因子个数大于1个
if(cnt == 0) vec.push_back(1); // 说明这个数字本来就是1,也得特判一下，加入vec中
}
for(int i = 1;i < int(vec.size());i ++){ // 判断最后的vec是否是非递减的
if(vec[i] < vec[i–1]) flag = true;
}
if(flag == true) printf("Alice\\n");
else printf("Bob\\n");

}
int main(){
int T;
scanf("%d",&T);
while(T —){
work();
}
return 0;
}

附上官方题解的代码

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

#define all(x) begin(x), end(x)

int primebase(int x) {
set<int> s;
for (int i = 2; i*i <= x; i++) {
while (x % i == 0) {
s.insert(i);
x /= i;
}
}
if (x > 1) s.insert(x);
if (s.size() > 1) return –1;
if (s.size() == 0) return 1;
return *s.begin();
}

void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &i: a) cin >> i;

// solve
vector<int> b(n);
for (int i = 0; i < n; i++) b[i] = primebase(a[i]);
if (is_sorted(all(a))) {
cout << "Bob\\n";
} else if (*min_element(all(b)) == –1) {
cout << "Alice\\n";
} else if (is_sorted(all(b))) {
cout << "Bob\\n";
} else {
cout << "Alice\\n";
}
}

signed main() {
int t = 1;
cin >> t;
while (t—) solve();
}

F. Mooclear Reactor 2

题意：

Bessie 需要在她的核反应堆中产生尽可能多的能量。她有 $n(1\le n,m\le 2\ast 10^5)$ 种不同的粒子。

每个粒子由两个整数 $x$ 和 $y$ $(1\le x\le 10^9,0\le y\le n)$表示。该粒子产生 $x$ 单位能量，但具有反应值 $y$，意味着它最多只能与反应堆中至多 $y$ 个其他粒子共存。形式化地说，如果选择该粒子来产生能量，那么除它自身外，最多只能选择 $y$ 个粒子一同产生能量。

Bessie 必须选出满足该约束的一个粒子子集来产生能量。产生的总能量为子集中所有粒子的能量之和。

商店里有 $m$ 个粒子。Bessie 必须从商店恰好购买一个粒子。对商店中的每个粒子，分别求出：如果 Bessie 只购买该粒子，她能产生的最大总能量。Bessie 不一定要使用从商店购买的那个粒子。

题解：

本题是一个选粒子问题，有两个限制，第一是总能量最大，第二是每个粒子都有共存粒子数量限制，另外还有个商店粒子混淆视听。其实商店粒子影响不大，因为最多选一个，所以最多在解集中替换掉一个已有粒子。

先简化一下问题，不考虑商店粒子的影响，并假设所有粒子的能量相同且为1，为使能量最大，应该怎么办？只需按反应值从大到小一个个选，直至选到第i个粒子时，发现已选粒子个数 > $y_i+1$，那么就达到能量最大的情况了。但能量大小不是1，而是$1\le x\le 10^9$，这意味着能量大的粒子可能反应值小，反应值大的粒子可能能量小，二者相互钳制难以判定选择谁，怎么办呢？

我们可以考虑限制粒子数，这样就好实现能量最大化了，如何限制呢？假设我们知道最优选法选了k个粒子，那我们就可以确定候选粒子（即哪些粒子有可能组成包含k个粒子的最优选法）：所有$y\ge k-1$的粒子都是可以选的，从中选出能量最大的k个即可；所有$y<k-1$的都是不能取的，因为取了就会使我们的粒子个数受限，从而达不到假设最优解的k个。

因为我们不知道最优选法选了几个粒子，所以分别求出选k$(1\le k\le n)$个粒子的最大能量，再从这些最大能量中取一个最大值$maxn$，就是我们要的全局最大总能量了。具体算法是用小根堆维护候选集中最大能量的k个粒子，随着指定的k减小，候选集不断增大（因为只有$y_i+1>=k$的粒子才可以选，k越小，满足的$y_i$就越多），保证堆的大小不超过k，超过了就把最小能量的堆顶弹出，实时维护堆中所有粒子能量的和即可，时间复杂度为$O(nlogn)$。

那加上商店粒子呢？假设商店粒子的能量为$x_{shop}$，反应值为$y_{shop}$。如果不选择商店粒子，最大总能量就是上面求出的maxn，如果选商店粒子，问题就转换为拿着一个指定的商店粒子，再从已有粒子中选出k$（0\le k\le y_{shop})$个粒子，使得总能量最大。这个问题和我们前文中处理的问题很相似，只需假设最后从已有粒子中选了k($0\le k\le y_{shop}$)个粒子，并保证留一个位置给商店粒子，也就是保证$y_i>=k$（选k个，要留k+1个位置），再从这$y_{shop}+1$种可能中取个最大值，就是我们的答案。

你可能会发现，如果对于每个商店粒子，都$O(nlogn)$跑一遍，时间复杂度是$O(n^{2}logn)$的。但实际上我们为商店粒子跑的每一遍都和商店粒子本身性质无关，只是保证空出一个位置的前提下，找k个最大能量的已有粒子，并取能量的最大值。所以我们完全可以不管商店粒子，直接指定从已有粒子中选k-1($0\le k\le n$)个，要求这些粒子满足$y_i\ge k-1$，和不考虑商店粒子时流程的唯一区别就是要求粒子的$y_i$要大1，留一个空位给商店粒子。这样跑一遍把每次的最大能量存到数组$f[i]$中，再对$f[i]$求一下前缀最大值（求前缀最大值是因为不确定最优选法是几个粒子，反正只要满足商店粒子的$y_{shop}$限制就行），对于每个商店粒子，用$O(1)$的时间复杂度查询。

代码：

#include <bits/stdc++.h>
using namespace std;
void work()
{
/*
n: 已有粒子个数
m: 商店中的粒子个数
x: 粒子能量
y: 粒子反应性，最多共存粒子数量（除自己）
vec1: vector<pair<val1:ll, val2:ll>>
val1和val2分别对应已有粒子的能量和反应性
vec2: vector<pair<val1:ll, val2:ll>>
val1,val2分别记录商店粒子的能量和反应性
now: 不考虑商店粒子时，实时维护的堆中所有粒子价值
maxn: 不考虑商店粒子的最大价值
pq: 小根堆，用于维护k大价值的粒子
cmp: 比较函数，按粒子反应性升序排序
p1: 一个指针，指向未进堆的最具反应性粒子
f[i]: 解集大小不大于i，且只用不多于i-1个已有粒子，空出位置给商店粒子的最大价值
*/
typedef long long ll;
int n, m;
ll x, y;
ll now = 0, maxn = 0;
priority_queue<ll, vector<ll>, greater<ll>> pq;
auto cmp = [&](pair<ll, int> a, pair<ll, int> b) -> bool
{
return a.second < b.second;
};

// 读入
scanf("%d%d", &n, &m);
int p1 = n;
vector<pair<ll, int>> vec1(n + 1), vec2(m + 1);
vector<ll> f(n + 2); // 注意这里是n+2，因为加上商店粒子后最多有n+1个粒子，会用到n+1这个下标
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld", &x, &y);
vec1[i] = make_pair(x, y);
}
sort(vec1.begin(), vec1.end(), cmp); // 按照反应性升序排序
for (int i = 1; i <= m; i++)
{
scanf("%lld%lld", &x, &y);
vec2[i] = make_pair(x, y);
}

// 第一次处理
for (int k = n; k >= 1; k—)
{
while (p1 >= 1 && vec1[p1].second + 1 >= k)
{ // 把反应性限制允许的粒子全部加入
pq.push(vec1[p1].first);
now += vec1[p1].first;
p1—;
}
while (pq.size() > k)
{ // 保证只留最大的k个粒子
now -= pq.top();
pq.pop();
}
maxn = max(maxn, now);
}
while (!pq.empty()) // 清空一下堆，为下一轮做准备
pq.pop();
p1 = n;
now = 0;
for (int k = n + 1; k >= 1; k—)
{
while (p1 >= 1 && vec1[p1].second + 1 >= k)
{ // 和第一轮一样
pq.push(vec1[p1].first);
now += vec1[p1].first;
p1—;
}
while (pq.size() > k – 1)
{ // 注意空出一个位置给商店粒子
now -= pq.top();
pq.pop();
}
f[k] = now;
}
for (int i = 2; i <= n + 1; i++)
{ // 处理一下前缀最大值，因为商店粒子(x,y)可以放到所有反应性限制不超过y的解集中
f[i] = max(f[i], f[i – 1]);
}
for (int i = 1; i <= m; i++)
{ // 输出答案，不一定用商店粒子，两者取较大即可
printf("%lld ", max(f[vec2[i].second + 1] + vec2[i].first, maxn));
}
printf("\\n");
return;
}
int main()
{
int T;
scanf("%d", &T);
while (T—)
{
work();
}
return 0;
}

G. Operation Permutation

文章太长，G、H分做另一篇文章讲解，详情见作者主页。

H. Six Seven

文章太长，G、H分做另一篇文章讲解，详情见作者主页。