[toc]

记录下刷题过程中每一道有价值的题目，算法笔记写在iPad上

2.2

https://codeforces.com/group/SiKhFBFwPd/contest/423801

Short Question

切比雪夫距离转曼哈顿距离

P3964 [TJOI2013]松鼠聚会

切比雪夫距离转曼哈顿距离

Factory Balls

BFS 竟然可过，时间复杂度为 $\mathcal O(2^{N+M} (K + M)) \approx \mathcal O(20,971,520)$

D – Triple Sword Strike

将 sumy 按照从大到小排序，设第 x 列有 |Sx| 个 坐标，对于每个x，在 sumy 暴力修改 |Sx| 个值，再在 sumy 中前 |Sx| + 2 大的值中找出 top2，再暴力恢复 sumy 数组原来的值。由于 |Sx| 的总和是 O(n) 的，所以时间复杂度正确。

2.3

毒瘤场

https://codeforces.com/group/SiKhFBFwPd/contest/423802

Sticks

想了好久，一开始暴力+贪心，后来贪心不对，又开始想网络流，但由于不是二分图，无法做最大独立集，最后半小时想到还可以状压DP，过了，最后题解告诉我暴力DFS枚举所有可能就行了

https://codeforces.com/contest/1791

CF Div 4.

本以为 AK 了，结果 G2 假了，Div4. AK 成就又达成失败了

Teleporters (Hard Version)

正确做法应该是枚举第一个位置，然后二分排序后的前缀和数组

2.4

https://atcoder.jp/contests/abc288

史上打得最烂的 ABC，参赛体验只有 10min

D – Range Add Query

这题卡了整场比赛，期间看了下 E 感觉 DP 也不简单，遂一直做 D，要是看下 F 的话还是能做出来 F 的

结论就是区间下标同余K的元素求和，得到的相等就是YES，不相等就是NO

E-Wish List

感觉这 DP 不太容易想到，状态设 $f[i][j]$ 表示前 $i$ 个物品里面买 $j$ 个的最小花费（当然前 $i$ 个物品里在清单里的必须要买）。对于第 $i$ 个物品，如果买它之前它前面的物品有 $j$ 个已经被买走了，那么附加花费就是 $\min {C_{i-j}, C_{i-j+1}, \dots , C_i }$。转移就简单了，不写了

F-Integer Division

F 是自己想出来的，对我来说感觉比 D、E 简单，$DP$ 很显然，方程很好推：
$$
\large f_i = \sum_{j \ge 0} f_j \cdot \text{Num}(j+1,i)
$$
然后就是优化，容易发现 $\text{NUM}(j+1, i) $ 和 $\text{NUM}(j+1, i+1) $ 是有联系的，所以不妨继续推下 $f_{i+1}$，懒得打公式了，最后结果就是
$$
\large f_{i+1} = 10 f_i + \text{sum}(i, a_{i+1})
$$

2.5

https://codeforces.com/contest/1786

Div1 + Div2 都是 tourist 出题

Letter Exchange

我是纯人脑分类大讨论，眼睛都看花了，花了 2h。后来看了 jiangly 的代码，发现思路是一样的，不过如果 STL 用得好的话能够减少很多冗余代码

2.6

https://codeforces.com/gym/103627

毒瘤场纯纯浪费时间

Yet Another Interval Graph Problem

E过了，下午的做法是假的。题解的做法是考虑如何让剩下的连通块size <= K 且权值和最大，将区间端点离散化，f[i]表示仅考虑区间右端点 <= i的所有区间，选取若干区间使得构成的连通块合法且权值和最大

枚举最后一个构成的连通块，f[i] = max { f[j] + g(j + 1, i) }, g(j + 1, i)表示仅考虑区间左右端点都在[j+1, i]的区间，构成1个连通块，权值最大为多少。g(j+1, i)只需要取 top-k 即可

2.8

https://codeforces.com/group/SiKhFBFwPd/contest/426108

CCPC 2018 绵阳

H – Hamming Distanc

有点意思的贪心题。相同的位置一定放 a。将不同的位置拿出来一起处理，从后往前，尝试放 1 ~ i 放 a 是否可行。

B – Array Modify

和洛谷 P5488 前缀和与差分 那道题类似。这题先反转数组，然后乘上生成函数即可。据说正解是 $\mathcal O(n\log n)$，但我不会。

A – Array Merge

vp的时候穷尽了各种思路和方法，还是没有想出来。

这题有意思，我做了严格的推理和证明，写在平板上了。

2.10

https://codeforces.com/group/SiKhFBFwPd/contest/423806

Periodic Ruler

这题逻辑有点绕。首先不能作为周期的数有两种情况：

1. a[i] != a[j]，则 abs(i – j) 的所有约数都不能作为周期

2. 该周期t不是最小循环节。即模t后不产生矛盾，所有生成元都存在，且存在t’ < t, t’是周期，则t不是周期

Or Machine

很有意思的Dij，多起点的Dij

建图不难想到，考虑一个结点最早什么时候能有1到达，这是一个多起点的最短路，距离需要特殊定义

这里的距离是用二元组(i, j)来定义的，i表示需要多少整数轮, j表示i轮后还需要多少次操作

Equivalent Pipelines

哈希。像这种大型抽象集合的比较，应该想到哈希

Automatic Sprayer 2

构造题，坑待填。

2.12

https://codeforces.com/group/SiKhFBFwPd/contest/425283

Divisible by 3

使用平方和公式，可以将 $\text{weight}(i, j)$ 化为两个前缀和相减的形式，再在 mod 3 下简单 DP 就可。坑待填

Reverse Game

由于这种题曾被 CF Div2 C 题卡过一次，还记得。

观察给的 4 种子串变换，就是等价于每次把 0 移到 1 的前面，每次轮最多可以操作 2 次

统计总共能移的次数为 $n$，操作转化为每次可以将 $n$ 减 1 或 减 2，最后无法再减（ $n=0$）就输。打个表可以很容易发现当 $ n \bmod 3 = 0$ 时先手会输

Mistake

拓扑序竟然没有用。对于输入的数字 $x$ ，$x$ 第几次出现就输出几。?

Modulo Permutations

排列计数，基本遇到一次就放弃一次，这次经过不懈奋斗终于想出来了。

第一步。由于比较条件“循环”的，圆排列的感觉，故钦定 1 排在第 1 位，最后答案乘 $n$

第二步。观察发现，$n(n \ge 3)$ 只能放在 $1$ 或 $2$ 的后面

上面两步一般都能发现，接下来这一步就看能不能观察出来了

第三步。考虑一个合法的排列是如何生成的，就是从小到大插入数，每次把数插在 $1$ 或 $2$ 的后面，并且插入的数和插入位置右边的数满足题目条件。可以证明，该生成方法和与所有的合法排列之间是充要条件。由此，我们可以得到一个 $\mathcal O(n^2)$ 的 DP 做法

第四步。实现第三步的做法，验证正确性。然后观察如何优化，

每次计算出当前答案后，枚举 $i$ 的倍数，把对后面答案的贡献累加上。时间复杂度降至 $\mathcal O(n \log n)$

没想到正解做法就是这样，1s 1e6 nlogn 这样出题真行啊，虽然常数确实小。

2.28

https://codeforces.com/contest/1796

Edu 144 Div. 2

气麻了，室友吵得没法写题，白打一场，不然肯定不会掉分，ABCD 肯定能过

牛客15165 字符串的问题

答案要么是 nxt[n] 要么是 nxt[nxt[n]]

3.2

https://codeforces.com/contest/1800

第一场 CF Div3. ，体验不错，还以为能 AK 了，最后一题没出，最后 Rank 296 可还行，可惜不计rating

D-Remove Two Letters

感觉题目很诈骗，我写的字符串双哈希过了，正解果真很简单

G-Symmetree

一眼树哈希，我觉得 CF 应该不会考这种 useless 的算法，我还去看了下洛谷树哈希的板子，n 的范围很小，而这题 n 范围比较大，应该不是哈希

哈哈，没想到题解真是树哈希，属实不会科技没办法，会估计就有机会 AK 了

关于树哈希的两篇文章：

https://peehs-moorhsum.blog.uoj.ac/blog/7891

https://codeforces.com/blog/entry/113465

试了下洛谷树同构那题，我才发现洛谷那题是无根树哈希，这题是有根树哈希。也就是说无根树哈希比较困难，能处理的数据范围比较小，有根树哈希还是比较容易