记录下刷题过程中每一道有价值的题目，算法笔记写在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
这题逻辑有点绕。首先不能作为周期的数有两种情况：
- a[i] != a[j]，则 abs(i - j) 的所有约数都不能作为周期
-
该周期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
试了下洛谷树同构那题，我才发现洛谷那题是无根树哈希，这题是有根树哈希。也就是说无根树哈希比较困难，能处理的数据范围比较小，有根树哈希还是比较容易
Comments | NOTHING