比赛 & vp 记录

考试总结

---

向 cmd 学习！

更好的阅读体验

加了星号 $\bigstar$ 就是正常的比赛，不加就是 vp。

焉有过活 如斯潦魄 惯是心向冰河
焉有长歌 拂过阡陌 惯要几人相和
焉有求索 古言朴拙 惯择一语来折
焉有喜乐 纷纷荡过 惯与世事酬酢

CF1559 $\bigstar$

2021.8.15

小号的分终于比大号高了，赶紧用大号开一把 CF。

Codeforces Round #738 (Div. 2) 通过 ABCD1，rank 826，感觉拉胯。

CF1559A Mocha and Math：憨憨题，AC记录。

CF1559B Mocha and Red and Blue：憨憨题，AC记录。

CF1559C Mocha and Hiking：憨憨题，AC记录。

CF1559D1 Mocha and Diana (Easy Version)：结论题，我一开始不敢写，后来写一发发现直接冲过去了，舒服，AC记录。

CF1559D2 Mocha and Diana (Hard Version)：

比较有意思的题。

考虑先把能与 $1$ 连边的点与 $1$ 连边，此时我们发现已经不存在与 $1$ 在两张图都不在同一连通块的点了，而与 $1$ 在两张图中都在同一连通块一定无法加边了，考虑剩下的点有且仅有一张图中与 $1$ 在连通块。

那么我们分成两类，两类的连通块一一对应加边即可，时间复杂度：$O(n\alpha(n))$。

AC记录。

CF1559E Mocha and Stars：

比较套路的题。

我们对 $\gcd=1$ 进行莫比乌斯反演，那么我们每次选取 $d$ 的倍数计算答案，然后乘上容斥系数 $\mu(d)$。

那么我们把所有数除以 $d$，剩下的东西发现可以做一次类似背包的 dp，设 $f_{i,j}$ 为前 $i$个位置，选择的和为 $j$ 的方案数，由于消除了 $\gcd=1$ 的限制，我们每次转移第 $i$ 个位置可以利用前缀和转移代表选择一个区间的数。

这样 dp 一次的复杂度为 $O(n\cdot\frac{m}{d})$，总共的复杂度是调和级数 $O(nm\log m)$。

AC记录。

总结：

前四题的解决速度是正常水平，没有问题。可是 D2 和 E 卡住就暴露了我写题目细节处理不到位，以及执着于一道题或一种思路而不愿意改变，这种思想得改！

ABC215 $\bigstar$

2021.8.21

考试的时候网络有点不稳定，每次交题都卡了很久才交上去。

AtCoder Beginner Contest 215 通过 ABCDEF，rank 459，performance 1882，感觉还行。（但是在 cmd 眼中这种 performance 已经是拉胯的程度了，差距还是很大啊）

ABC 215A Your First Judge：憨憨题，AC记录。

ABC 215B log2(N)：憨憨题，AC记录。

ABC 215C One More aab aba baa：憨憨题，考场想复杂了点，后来发现直接暴力做就好了，但是花了近 $10min$。AC记录。

ABC 215D Coprime 2：比较套路/简单的题，$6min$ 做完，符合预期。AC记录。

ABC 215E Chain Contestant：这里脑子仍然保持在线，很快就想出了做法，但是由于没有思考完整，所以实现了 $15min$，但是还是符合预期。AC记录。

ABC 215F Dist Max 2：

一开始想着用切比雪夫距离和曼哈顿距离替代，发现没有啥前途。

考虑枚举第一个点，二分距离，那么判断是一个二位数点状物，用一个维护前/后缀的主席树就好了，时间复杂度 $O(n\log^2)$。

考试的时候发现主席树已经生疏了，强行写出主席树硬生生调了 1h，最后 5min 才 AC，导致罚时贼高。/ll

AC记录。

ABC 215G Colorful Candies 2：

比较套路的题，可惜没有时间做了，不过做也不一定做得出来。

首先根据期望的线性性，对于每个 $k$，我们要求的是每个颜色选了至少一次的概率（等价于期望），也就是：（设 $c$ 为颜色数，$k_i$ 为第 $i$ 个颜色的糖果个数）

$$\sum_{i=1}^c\frac{{n\choose k}-{n-k_i\choose k}}{{n\choose k}}$$

这个东西仍然不好做，我们观察数据范围，发现 5e4 是常见 $\log^3 n$ 或 $\sqrt n\log n$ 范围，而根号又提示我们不同的 $k_i$ 只有根号种。（经典结论）

我们把相同的 $k_i$ 放在一起计算就是 $O(n\sqrt n\log n)$ 了，实现精细一点是 $O(n\sqrt n)$ 的。

AC记录

ABC 215H Cabbage Master：

如果单纯判断能否成为 Cabbage Master 的话，这是经典问题。

我们以每一个单位为 $1$ 的需求作为左部，吗，每个卷心菜为右部，将可以供给这个需求的卷心菜与需求连边，那么这是一个二分图。使用霍尔定理，我们发现左部存在完美的匹配的充要条件为对于每个需求集合 $S$，它连接的点数至少为 $|S|$。

由于需求太多，我们尝试变形：（设 $f(S)$ 为 $S$ 相邻的结点集合）

$$\min_S\{|f(S)|-|S|\}\geqslant 0$$
$$\min_T\{|T|-\max_{f(S)\subseteq T}\{|S|\}\}\geqslant 0$$

预处理一个 $g(T)$ 为 $f(S)\subseteq T$ 的最大 $S$ 那么我们就可以判断了。（这个 $g(T)$ 要用 FMT 处理一下）

好，那么考虑怎么做原题，那么我们只需要对任意的一个 $T$ 使得 $|T|-|g(T)|$ 为负，那么我们的花费就是 $|T|-|g(T)|+1$，于是我们就求出了最小花费。

方案数也比较简单，对于修改花费等于最小花费的集合，选出这些集合中互不包含且最大的集合直接算任取 $|T|-|g(T)|+1$ 个卷心菜的方案数加起来就好了。（这个还是可以用 FMT 随便判一判，具体可以看代码）

时间复杂度：$O(n2^n)$。AC记录

总结：

搞 OI 不能好高骛远，不能因为是 Beginner Contest 就骄傲自大，你看，你不照样没有做出来 G 和 H？所以说平时做题还是要脚踏实地，多思考，多锻炼比赛状态，少贺题，这样才能带来水平真正的提升。

单论比赛过程的话，ABD 没有问题，C 体现了我解决简单问题的方式不够简单，E 体现了我想 dp 没有想完整，F 则暴露了我一些板子仍然不熟练，且解决问题方法偏向套路，G 不敢开的原因主要是对这种期望的畏惧，H 是我能力不足，肝败吓疯。

ARC125 $\bigstar$

2021.8.22

AtCoder Regular Contest 125 通过 ABC，rank 282，performance 2127，感觉不错。（但是在 cmd 眼里已经是一般的程度了，差距还是很大啊）

ARC125A Dial Up：憨憨题，考虑数组不动指针动，AC记录。

ARC125B Squares：结论题，做了很久才做出来，太拉了/kk。AC记录。

ARC125C LIS to Original Sequence：Dilworth 定理板子题，直接贪心构造，AC记录。

ARC125D Unique Subsequence：憨憨题，直接设 $f_i$ 为前 $i$ 个位置的答案，然后直接树状数组转移就可以了，赛后 5min 过题，非常惨，AC记录。

ARC125E Snack：

nb 题。

这个问题一看就有网络流写法：将每个零食 $i$ 变成一个点，源点向零食连一条 $a_i$ 的边，每个同学 $j$ 变成一个点，零食向每个同学连一条 $b_j$ 的边，每个同学向汇点连一条 $c_j$ 的边，很显然这张图的最大流表示答案。

考虑模拟网络流，求出最小割。下面我们称 $x$ 连向 $y$ 表示存在一条无割边的从 $x$ 到 $y$ 的路径。

假设我们已经决定了零食是否与 $S$ 有割边，那么对于小孩 $i$，如果连向 $S$ 则需要 $c_i$ 的代价割掉与 $T$ 的连边，如果连向 $T$ 则需要 $tot\cdot b_i$ 的代价割掉所有与没有割掉与 $S$ 连边的零食的边，即代价为 $\min\{c_i,cnt\cdot b_i\}$。（$cnt$ 为没有割掉与 $S$ 连边的零食数量）

那么我们发现小孩的决策是仅依赖于 $cnt$ 的，考虑枚举 $cnt$ 的取值，那么我们左边贪心选择最小的 $a$，右边贪心将 $\frac{c_i}{b_i}\leqslant cnt$ 的所有孩子的决策改为 $c_i$ 就好了。

时间复杂度：$O(n\log n+m)$。AC记录。

ARC125F Tree Degree Subset Sum：

这里考虑给所有度数减一，这样会让后面的处理更加方便。（后面会说明原因）

首先出题人告诉你一棵树的含义实际上就是告诉你度数的总和为 $n-2$，这启发我们对相同的度数同时处理，这样由于不同的度数数量为 $\sqrt n$ 级别，所以会让我们的处理更加轻松。

考虑猜结论，设 $f_x$ 为凑出 $x$ 的最少点数，$g_x$ 为凑出 $x$ 的最多点数，那么对于 $f_x\leqslant y\leqslant g_x$，$y$ 个点一定能凑出 $x$。

设 $k$ 为度数为 $0$ 的点数量，由于 $f_x$ 一定不包含任意度数为 $0$ 的结点，$g_x$ 一定包含所有度数为 $0$ 的结点，于是显然 $[f_x,f_x+k]\cup[g_x-k,g_x]$ 区间内的 $y$ 一定可以凑出 $x$，那么我们只需要证明 $g_x-f_x\leqslant 2k$ 即可。

我们选出任意一个子集 $S$，设 $v_S=\sum_{x\in S}deg_x$，考察 $v_S-|S|$ 的取值范围：

• 当 $S$ 都是度数为 $0$ 的结点时其值取到下界，为 $-k$。
• 当 $S$ 都是度数大于 $1$ 的结点时其值取到上界。考虑每个度数大于 $1$ 的结点都会贡献度数减一的权值，而手玩一下会发现每一个单位的权值恰好会对应一个度数为 $0$ 的结点。（可以理解为抢了它原本的权值？）而很容易发现这个值的上界为 $k-2$。

那么带入 $f,g$ 就有 $-k\leqslant x-g(x)\leqslant x-f(x)\leqslant k-2$。

变一下式子就有：$\Rightarrow x-k+2\leqslant f(x)\leqslant g(x)\leqslant x+k\Rightarrow g(x)-f(x)\leqslant (x+k)-(x-k+2)=2k-2$。

于是我们证明了上面的结论，我们使用单调队列或者二进制拆分优化背包就可以了。（代码用的是单调队列优化）

时间复杂度：$O(n\sqrt n)$，AC记录。

好久没有写单调队列优化背包了，写了好久/kk，注意单调队列要先加入当前 dp 值再弹，而不是先弹再加。（有大小为 $0$ 的物品）

总结：这一场打的中规中矩，T1 正常时间内通过，T2 则用时极长，超出预期，还是要积累猜结论能力。T3 正常，T4 调的时间过长，原因是 dp 状态设计不清晰，导致转移方程迟迟无法推出来，这是我 dp 的通病，一定要改正。

CF1561 $\bigstar$

2021.8.24

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine)) 通过 ABCD1D2E，rk 30，感觉牛逼。（orz hzr rk22）

一开始 T1 做了好久，非常自闭，然后 T2 不会做，T3 看了看发现可以做，写了之后挂了一发，发现排名 1000+，非常烦躁。

写完 T3 看 T4，发现 dp 比较简单，两个 $\log$ 过了 D1，发现树状数组改成后缀和就砍了一个 $\log$ 于是过了 D2，发现混进前 100，就变成顺风局了，重新搞了一下 B，然后 hzr 又教育了我 E，于是就混进了 rk 30，非常舒服。

CF1561A Simply Strange Sort：暴力题，AC记录。

CF1558A Charmed by the Game：憨憨题，做了 114514 年没做出来，hzr 姐姐教教我，AC记录。

CF1561C Deep Down Below：憨批题，贪心排序，AC记录。

CF1561D1 Up the Strip (simplified version)：AC记录。

CF1558B Up the Strip：考虑套路地设一下 dp 状态，发现转移可以刻画成 $\log$ 个区间和，直接调和级数就好了，AC记录。

CF1558C Bottom-Tier Reversals：被 hzr 教育了，考虑每次将最大的两个数通过 $5$ 次翻转放在最后面，然后删除这两个数，翻转你可以随便搞一搞，反正我搞不出来，自闭了，AC记录。

reverse(firstpos),reverse(secondpos-1),reverse(secondpos+1),reverse(3),reverse(i);//firstpos 为最大的数位置，secondpos 为第二大的数的位置，i 为当前剩余序列长度

CF1558D Top-Notch Insertions：

考虑最终排好序的序列，如果没有限制则每两个相邻的数之间都是小于等于，一个限制会让某一个小于等于变成小于号，我们考虑计算出小于号的数量 $c$，那么最后的答案就是 ${2n-1-c\choose n}$。

考虑倒序枚举限制，那么一个限制会在前面排好序的序列中在前面插入一个小于号，我们在树状数组上二分一下这个位置，然后判断这个位置前面有无小于号，如果无就加入并更新 $c$ 就好了。

注意 $\sum n$ 很大，我们提前预处理出来树状数组，每次更新完之后撤销就可以了。

时间复杂度：$O((\max\{n\}+\sum m)\log n)$，AC记录。

CF1558E Down Below：咕

CF1558F Strange Sort：咕

CFgym103119

2021.8.25

CF1562 $\bigstar$

2021.8.26

Codeforces Round #741 (Div. 2) 通过 ABCD1D2，rk187，感觉不错。（orz wyz rk117）

咕。

CFgym102433

2021.8.27

CFgym101173

2021.8.28

CF1556 $\bigstar$

2021.8.29

咕

ARC105

2021.8.30

AtCoder Regular Contest 105 通过 ABCDEF（DEF 都看了题解/ll），如果不看题解应该是 rk150，performance 2324 ，感觉挺好。

这次没太认真打，当时会了 F 还没开始，于是准备倒序开题，结果 EF 做的贼快，CD 卡了一年/ll。

ARC105A Fourtune Cookies：简单题，枚举分组方案判断就好了，AC记录。

ARC105B MAX-=min：猜结论题，直接输出 $\gcd$，AC记录。

ARC105C Camels and Bridge：观察 $n$ 很小，考虑枚举全排列，然后 dp 一遍，转移的时候枚举新加入的所有段，计算这些段的最少长度就好了，AC记录。

ARC105D Let's Play Nim：

把两个部分分开看，那么第二个部分就是检验是否异或和为 $0$。

如果 $n$ 是奇数，考虑先手第一步放在哪一个盘子，那么后手每次都拿当前最大的放在那个盘子，这样那个盘子的石子和大于总和的一半，异或和不可能为 $0$，后手必胜。

如果 $n$ 是偶数，后手必胜当且仅当所有石子堆都可以两两配对。考虑如果不能两两配对，先手可以类似上面的方法，让一个堆大于总和的一半。

代码实现就很简单了，AC记录。

ARC105E Keep Graph Disconnected：

又是博弈论，麻了。

设最后 $1$ 所在连通块大小为 $x$，$n$ 所在的连通块大小为 $n-x$，那么最后的边数一定是 $\frac{n(n-1)}{2}-x(n-x)$。

如果 $n$ 为奇数，那么 $x(n-x)$ 一定是偶数，上述值的奇偶性是确定的，那么可以直接判断。

如果 $n$ 是偶数，那么 $x(n-x)$ 的值可以为奇也可以为偶。设 $x_0,y_0$ 为 $1,n$ 最初的连通块大小，那么如果 $x_0,y_0$ 奇偶性一样，那么中间未联通的点数一定是偶数，那么某一方一定可以使得 $xy$ 的奇偶性不变。（如果对方上次未改变奇偶性，那么这次可以把一个偶连通块并入任意零散连通块；如果对方上次改变了奇偶性，那么一定可以把一个奇连通块并入一个 $1/n$ 连通块使得奇偶性与原来一样）如果 $x_0,y_0$ 奇偶性不一样，那么先手可以选择让 $x_0,y_0$ 变为两奇或两偶使得自己可以取得胜利。

代码也相当好写，AC记录。

ARC105F Lights Out on Connected Graph：

感觉这道题和 CF1556F 差不多。

观察发现 $n$ 很小，于是考虑状压。

设 $tot_S$ 为 $S$ 内部的边数量，$edge(a,b)$ 为集合 $a$ 到集合 $b$ 的边数，$f_S$ 为 $S$ 为二分图的方案数，$g_S$ 为 $S$ 为连通二分图的方案数。

转移是比较简单的，考虑 $f$ 的转移直接枚举其中一个部分，$g$ 的转移在 $f$ 的基础上容斥，注意要枚举一个点 $k$ 作为两个连通块的公共点（防止算重）：

$$f(S)\leftarrow 1+\sum_{T\ne\varnothing,T\ne S,T\subseteq S}2^{edge(S-T,T)}\\g(S)\leftarrow f(S)-\sum_{T\ne\varnothing,T\ne S,k\in T,T\subseteq S}g(T)f(S-T)$$

由于有两种颜色，最后答案要除以 $2$。时间复杂度：$O(3^n)$，AC记录。

ABC212

2021.8.30

CF1513

2021.9.1

Divide by Zero 2021 and Codeforces Round #714 (Div. 2) 通过 ABCDEF，rk29（DF 看了题解/ll），感觉牛逼。

这场又尝试了一下倒序开题，结果开幕雷击，F 完全不会做/ll，麻了。

CF1513A Array and Peaks：憨包题，两次没过样例没发现/qd，AC记录。