CodeTON Round 2 题解
Andrewzdm
·
·
个人记录
也许更好的阅读体验
写在前面
时隔近两年，这个 Codeforces赛后题解 系列续更了（
但是估计后面很长一段时间又要咕咕咕了
终于没掉分了，还上了一波小分，感动。可惜 E 题没能完成绝杀。还是太菜了 /kk
CF1704A Two 0-1 Sequences
首先不要看错题，只有 a 序列是可以操作的，b 序列是不会变的。而 a 的操作又要删除元素，所以 m\le n 才能使 a 有可能 变成 b。（赛时看题目浏览得比较匆忙，没注意到题目保证 m \le n，所以代码中有一处特判，删去不影响）
由于最后 a 的长度从 n 变为 m，而每次操作只能改变第一个元素，所以原序列 a 和 b 的后 m-1 位必须相同。
时间复杂度 $O(n)$，代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
int n, m;
char a[maxn], b[maxn];
void work()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
if(n < m) //前面提到的特判，删去不影响。
{
puts("No");
return;
}
for(int i = n; i >= n - m + 2; --i)
if(a[i] != b[m + i - n])
{
puts("No");
return;
}
for(int i = n - m + 1; i >= 1; --i)
if(a[i] == b[1])
{
puts("Yes");
return;
}
puts("No");
return;
}
int main()
{
int T;
cin >> T;
while(T--) work();
return 0;
}
```
# [CF1704B Luke is a Foodie](https://www.luogu.com.cn/problem/CF1704B)
本题和 [CF1304C Air Conditioner](https://www.luogu.com.cn/problem/CF1304C) 的思想比较相似，不妨在切完本题后去切一下这题。
把题意抽象并且形象化一下，就是说，有一个区间 $[v-x, v+x]$ 可以通过改变 $v$ 的值移来移去，我们要尽可能地把 $a_i$ 框进去。
为了把 $a_1$ 框进去，$v$ 的范围为 $[a_1-x, a_1+x]$；
在不考虑 $a_1$ 的情况下，为了把 $a_2$ 框进去，$v$ 的范围为 $[a_2-x,a_2+x]$。
那么如果这两个限制区间有交集，我们就可以通过调整 $v$ 的初始值把 $a_1, a_2$ 一次性框进去，$v$ 的范围就是这两个区间的交集；
如果这两个限制区间没有交集，那么就必须改变 $v$ 的值，$ans$ 增加 $1$，总的限制区间设置为 $[a_2-x,a_2+x]$。
此后类似。
总结一下思路：计算把 $a_1,a_2,\cdots,a_k$ 都框进去的 $v$ 的限制区间 $[L,R]$。对其后的 $a_{k+1}$，若 $[a_{k+1}-x,a_{k+1}+x]$ 与 $[L,R]$ 有交集，那么就调整 $L$ 和 $R$；若没有交集，那么 `ans++`，$[L,R]$ 设为 $[a_{k+1}-x,a_{k+1}+x]$。
代码如下，时间复杂度 $O(n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n;
ll a[maxn], x;
inline int read();
void work()
{
n = read();
x = read();
for(int i = 1; i <= n; ++i) a[i] = read();
ll L, R; int ans = 0;
L = a[1] - x; R = a[1] + x;
for(int i = 2; i <= n; ++i)
{
ll l = a[i] - x, r = a[i] + x;
if(r < L || l > R)
{
ans++;
L = l; R = r;
continue;
}
L = max(L, l);
R = min(R, r);
}
printf("%d\n", ans);
return;
}
int main()
{
int T;
cin >> T;
while(T--) work();
return 0;
}
inline int read()
{
int x = 0; bool f = true; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = false; ch = getchar(); }
while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return f ? x : -x;
}
```
# [CF1704C Virus](https://www.luogu.com.cn/problem/CF1704C)
思考一下传染的过程：$m$ 个初始感染点会把 $n$ 个点分隔成 $m$ 个区间（当然有的区间长度为 $0$），每个区间在不加任何干预的情况下会每次感染最左端和最右端的点，不断向中间推进直至全部感染。
要让感染的点最少，也就是让健康的点最多。
怎么样才能让健康的点最多呢？
~~古人云：“求木之长者，必固其根本；欲流之远者，必浚其泉源；思国之安者，必积其德义。”要从源头抓起防患于未然。~~
只要在每一段先堵上最左边的传染源再堵上最右边的传染源，就能让中间的点全部不被感染。
那么不难想到一个贪心的思想：先保最长的区间。
时间复杂度 $O(m\log m)$，代码见下：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 1e5 + 10;
int n, m, a[maxm], b[maxm];
inline int read();
void work()
{
n = read();
m = read();
for(int i = 1; i <= m; ++i) a[i] = read();
sort(a + 1, a + m + 1);
b[1] = n - a[m] + a[1] - 1;
for(int i = 2; i <= m; ++i)
b[i] = a[i] - a[i - 1] - 1;
sort(b + 1, b + m + 1);
reverse(b + 1, b + m + 1); //懒人式排序，从大到小
//其实是赛时智障了一不小心搞成从小到大排序了
//于是直接加了个reverse补救一下
int ans = 0, t = 0;
for(int i = 1; i <= m; ++i)
{
ll inf = 2LL * t; //infected
if(b[i] - inf <= 0) continue;
if(b[i] - inf <= 2) //这种情况只能保一个点
{
ans++;
t++;
continue;
}
ans += b[i] - inf - 1;
//先堵上左边，然后损失一个点，再堵右边
t += 2;
}
cout << n - ans << endl;
return;
}
int main()
{
int T;
cin >> T;
while(T--) work();
return 0;
}
inline int read()
{
int x = 0; bool f = true; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = false; ch = getchar(); }
while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return f ? x : -x;
}
```
# [CF1704D Magical Array](https://www.luogu.com.cn/problem/CF1704D)
~~一道 _Never Gonna Give You Up_ 式的 Rick Astley 诈骗题~~
一道思维好题。
乍一看很难找到突破口——复原数组 $b$ 显然是不现实、不可行的。
那么思考的重点便是：
* 所有由操作 $1$ 得到的数组，有什么共同的特征？
* 由操作 $2$ 得到的数组，如何与操作 $1$ 得到的数组区别开来？
* 既然要计数，那么能否把数组映射为一个数，从而既达到判定又达到计数的目的？
目标：将数组处理成一个值，使得进行一次操作 $1$ 不会改变这个值，而进行一次操作 $2$ 会将这个值增加 $1$。
这种想法属实是妙手偶得的神来之笔。
这其实是一个 hash 的思想，也就是，构建映射。
那么思路呼之欲出了：计算 $\sum\limits_{j=1}^n j \times c_j$。这个值满足我们的目标。
时间复杂度 $O(nm)$，代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m;
vector<ll> c[maxn];
ll v[maxn];
void work()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
c[i].clear();
c[i].resize(m + 1);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> c[i][j];
fill(v + 1, v + n + 1, 0);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
v[i] += j * c[i][j];
ll mx = 0;
int idx;
for(int i = 1; i <= n; ++i)
{
if(v[i] > mx)
{
idx = i;
mx = v[i];
}
}
cout << idx << ' ';
for(int i = 1; i <= n; ++i)
if(v[i] != mx)
{
ll ans = mx - v[i];
cout << ans << endl;
break;
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) work();
return 0;
}
```
# [CF1704E Count Seconds](https://www.luogu.com.cn/problem/CF1704E)
赛时把题意读错了，凉了。
整个流程就好比是一个漫水的过程。
众所周知，在没有什么思路的时候，比较好的办法是手玩模拟一下样例。
不妨先思考没有点权为 $0$ 的情况：入度为 $0$ 的点只减不增，把自己的点权贡献给出边连向的点，点权减到 $0$ 之后删去，从而又有新的一批点只减不增……
**可不就是拓扑排序吗！** 只要把拓扑序在前面的点的点权一直传递下去到汇点，就结束了，这部分很好算。
但问题出现了：我们发现汇点有可能点权为0，这个时候不会把点权排出去，不能用上面的方法直接算。
然而经过 $n$ 轮后，所有的点的点权一定可以传递到汇点，假如在这前 $n$ 轮中不是所有点的点权都变成了 $0$，那么一定会使得汇点点权 $>0$。
上代码，复杂度 $O(nm+n^2)$。一些细节见代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int mod = 998244353;
int n, m;
vector<int> g[maxn];
int in[maxn], a[maxn], add[maxn];
int ans;
bool del[maxn];
queue<int> q;
int tpo[maxn], tim;
inline int read();
void bruteforce()
/*
这里a和add的值都不要取模
因为可能涉及a是998244353的倍数的情况，取模后会出现错误
而且此处不取模是不会溢出的
*/
{
ans++;
fill(add + 1, add + n + 1, false);
for(int i = 1; i <= n; ++i)
if(a[i] > 0)
for(int v : g[i])
add[v]++;
for(int i = 1; i <= n; ++i)
if(a[i] > 0)
a[i]--;
for(int i = 1; i <= n; ++i) a[i] += add[i];
return;
}
void toposolve()
{
tim = 0;
for(int i = 1; i <= n; ++i)
if(in[i] == 0)
q.push(i);
while(!q.empty())
{
int p = q.front(); q.pop();
tpo[++tim] = p;
for(int v : g[p])
if((--in[v]) == 0)
q.push(v);
}
for(int i = 1; i <= n; ++i)
a[i] %= mod;
for(int i = 1; i <= n; ++i)
{
for(int j : g[tpo[i]])
a[j] = (a[j] + a[tpo[i]]) % mod;
}
ans = (ans + a[tpo[n]]) % mod;
return;
}
void work()
{
ans = 0;
n = read(); m = read();
fill(in + 1, in + n + 1, 0);
fill(del + 1, del + n + 1, false);
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) g[i].clear();
for(int i = 1; i <= m; ++i)
{
int x, y;
x = read(); y = read();
g[x].push_back(y);
in[y]++;
}
for(int i = 1; i <= n; ++i)
{
bool flag = true;
for(int j = 1; j <= n; ++j)
if(a[j] != 0)
{
flag = false;
break;
} //记得check，可能没跑满n轮就结束了
if(flag)
{
cout << ans << endl;
return;
}
bruteforce();
}
toposolve();
cout << ans << endl;
return;
}
int main()
{
int T;
T = read();
while(T--) work();
return 0;
}
inline int read()
{
int x = 0; bool f = true; char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = false; ch = getchar(); }
while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return f ? x : -x;
}
```
# 写在后面
太难了后面的题，
大钟楼下送快递，
一边开摆一边寄。
~~（押韵成功）~~
做不来，不写了。