感觉 tf 的时候还是打几场 VP 好……
加*号的是当场过掉的，这样以后复习可以用。
*A. Mystical Mosaic
题意好难翻译啊，那就不翻译了吧。
反正直接模拟就可以了。
代码：58555087
*B. Three-level Laser
题目大意是给你一个长度为 𝑛(𝑛≤105) 的严格递增的正整数序列 {𝐸}，让你求 𝑖<𝑗<𝑘 使得 𝐸𝑘−𝐸𝑖≤𝑈 且 𝜂=𝐸𝑘−𝐸𝑗𝐸𝑘−𝐸𝑖 最大。
考虑到严格递增应该是单调性问题。
显然如果 𝑖 和 𝑘 固定，那么 𝜂 与 𝐸𝑗 负相关，于是 𝑖=𝑗−1。
然后考虑枚举 𝑖 算 𝑘，直接把上面的 𝐸𝑘 去掉即可：𝜂=𝐸𝑘−𝐸𝑗𝐸𝑘−𝐸𝑖=𝐸𝑘−𝐸𝑖+𝐸𝑖−𝐸𝑗𝐸𝑘−𝐸𝑖=1+𝐸𝑖−𝐸𝑗𝐸𝑘−𝐸𝑖
二分一下就好了。
代码：58555515
*C. Riverside Curio
题意大概就是有一个人每天去看一条河的水位，每次在水位上画一条线，并记录下严格高于当前水位的线有几条，记为 𝑚𝑖。令第 𝑖 天严格低于当前水位的线有 𝑑𝑖 条，求 ∑𝑑𝑖 的最小值，𝑛≤105。
显然最少有 max{𝑚𝑖} 条线，然后我们找到这个位置，然后往两边跑。往后跑就直接模拟即可，因为之后是不会画新的线了。往前跑相当于是删线，显然是能删就删，维护一下前缀 max 即可。
代码：58556096
题意是说有 𝑛(𝑛≤105) 架飞机在一条数轴上飞，坐标为 𝑥𝑖，速度为 𝑣𝑖，有 𝑥𝑖𝑣𝑖<0（往原点飞），现在可能有一速度为 𝑣 的风，只能预测出 𝑣∈[−𝑤,𝑤]，当然保证 |𝑣𝑖|<𝑤。求有多少对飞机可能同时到达原点。
感觉自己好菜啊，推式子发现是跟斜率相关的一个东西，然后惊喜地发现这好像是道计算几何，然后码了一年……
我们考虑计算出飞机到达原点的时间 𝑡𝑖∈[𝑙𝑖,𝑟𝑖]，考虑到风速与时间是呈一个一次函数的关系，画图便可知道如果是相向飞行的飞机 𝑖,𝑗，只要 [𝑙𝑖,𝑟𝑖]∩[𝑙𝑗,𝑟𝑗]≠∅ 即可，如果是同向的飞机 𝑖,𝑗，只要 [𝑙𝑖,𝑟𝑖]⊆[𝑙𝑗,𝑟𝑗] 或 [𝑙𝑖,𝑟𝑖]⊇[𝑙𝑗,𝑟𝑗] 即可。
然后就变成了一个二维数点问题。
代码：58560521
E. Wardrobe
题解写在了另一篇文章里。
F. Minimal Subset Difference
太菜了，不会。
*A. Sasha and a Bit of Relax
题意大概就是给你一段长度为 𝑛(𝑛≤3×105) 序列 {𝑎}(0≤𝑎𝑖<220)，求有多少个区间 [𝑙,𝑟] 使得 𝑟−𝑙+1 是偶数且 ⨁𝑚𝑖=𝑙𝑎𝑖=⨁𝑟𝑖=𝑚+1𝑎𝑖，其中 𝑚=𝑙+𝑟−12，⨁ 是指 xor。
显然只要 ⨁𝑟𝑖=𝑙𝑎𝑖=0 即可，然后开个桶算。
代码：58788064
*B. Sasha and One More Name
题意是给你一个回文串 𝑠(1≤|𝑠|≤5000)，求最小割多少刀然后重组变成一个不同的回文串，无解输出 Impossible。
显然答案只有 1、2、Impossible 三种，Impossible 直接判，1 直接暴力枚举，剩下来的都是 2。
代码：58788424
C. Sasha and One More Name
数据结构题，直接抄了这篇博客的翻译：
维护以下三种操作
1 t s：在时刻 𝑡 插入命令 𝑠。保证任意操作后，任意时刻至多只有一个命令。2 t：删除时刻 𝑡 的命令。3 l r v：求最小的 𝑡∈[𝑙,𝑟]，使得 𝑓(𝑡)=0。
其中
𝑓(𝑡)=𝑣+∫𝑡𝑙𝑔(𝑥)d𝑥
其中设在 [𝑙,𝑟] 时间内的命令依次为 (𝑡1,𝑠1),…,(𝑡𝑚,𝑠𝑚)，则：
𝑔(𝑡)=⎧{
{
{
{⎨{
{
{
{⎩0𝑙≤𝑡<𝑡1𝑠1𝑡1≤𝑡<𝑡2…𝑠𝑘𝑡𝑘≤𝑡<𝑡𝑘+1…𝑠𝑚𝑡≥𝑡𝑚.
若不存在，则返回 −1。
题解留坑吧……
打了场 Div. 2 感觉自己心情舒畅，然鹅还是自闭了……
话说我的 hash 好菜啊，为什么一定要打双哈希啊……
自闭了：
*A. Hotelier
直接模拟就可以了。
代码：58884080
*B. Block Adventure
还是直接模拟就可以了。
代码：58884001
*C. Round Corridor
大概就是有类似这样的一个圆形屋子，内层有 𝑛 格，外层有 𝑚 格，每层都有一面墙在 12 时的位置，每格大小均匀。内外层没有墙，但每层格子与格子之间有墙。多次询问 (𝑠𝑥,𝑠𝑦) 和 (𝑒𝑥,𝑒𝑦) 询问着两个格子能否相互到达。
𝑛,𝑚≤1018,𝑞≤104。
显然可以把这个环形分成一段一段，每段都相连且独立（与其他格子不连通）。
假设一段有 𝑥 个内层格子与 𝑦 个外层格子，那显然有 𝑛𝑥=𝑚𝑦，即 𝑛𝑦=𝑚𝑥，我们需要找到最小的 𝑥,𝑦，也就是 𝑛𝑦=𝑚𝑥=lcm(𝑛,𝑚)=𝑛𝑚gcd(𝑛,𝑚)，也就是 𝑥=𝑛gcd(𝑛,𝑚),𝑦=𝑚gcd(𝑛,𝑚)，然后每次 O(1) 判断两个点是否在同一联通块中即可。
代码：58883764
*D. White Lines
题意是有一块 𝑛×𝑛 的画布，有一些像素点是 W，有一些是 B，你可以将一个 𝑘×𝑘 的子矩阵中所有的 B 全部变成 W，问做多能有多少行列是全白色的，𝑛≤2000。
我们考虑行和列分开来看，我们令 𝑓𝑖,𝑗 表示左上角在第 𝑖 行第 𝑗 列，会把多少原来不是全白的行变成全白的行，同理可以定义 𝑔𝑖,𝑗 表示会把多少原来不是全白的列变成全白的列。当然，为了复制粘贴方便，代码中把 𝑔𝑖,𝑗 定义为了左上角在第 𝑗 行第 𝑖 列。
由于转移是对称（行和列的方程一样）的，所以我们就仅考虑行。我们考虑要把一行变成全白，必须把该行上最左边的黑色格子和最右边的黑色格子全部覆盖到，所以对于每行我们可以 O(1) 计算。
我们考虑先 O(𝑛𝑘) 暴力算出 𝑓1,𝑗，然后每次计算 𝑓𝑖,𝑗 考虑增加第 𝑖+𝑘−1 行的贡献并删除第 𝑖−1 行的贡献即可。
这样复杂度就是 O(𝑛2) 的了。
代码：58884654
E.Compress Words
题目大意是有 𝑛 个字符串 𝑠𝑖，从左往右依次合并每一个字符串，就是找到之前合并完的串的最长后缀使其是要合并的那个串的前缀，输出最终合并完的串，𝑛≤105,∑|𝑠𝑖|≤106。
直接哈希就可以了，复杂度 O(𝑛)……
大概需要双哈希，我的单哈希 wa on 66。
代码：58886006
又是一场愉快的 Div. 2。
可惜窝还是爆蛋了……
*A. Distinct Digits
直接模拟即可……
代码：61680483
*B. Filling the Grid
直接模拟即可……
代码：61680658
*C. Primes and Multiplication
题目大意有点复杂，然后我就看错了一年的题……
定义 prime(𝑥) 表示 𝑥 的质因子集合，𝑔(𝑥,𝑝) 表示最大的 𝑝𝑘∣𝑥(𝑘∈ℕ)，𝑓(𝑥,𝑦)=∏𝑘∈prime(𝑥)𝑔(𝑦,𝑘)，求 ∏𝑛𝑖=1𝑓(𝑥,𝑖)。（𝑥≤109,𝑛≤1018）
考虑到全是乘法，显然满足交换律。
所以我们对每个质因子分开来求，最后乘起来即可。
我们考虑质因子 𝑘，显然 1∼𝑘−1 的区间贡献是 1，𝑘∼𝑘2−1 的贡献是 𝑘，𝑘2∼𝑘3−1 的贡献是 𝑘2……
然后不难发现只有 log 个这样的区间，所以总复杂度 O(√𝑥+log𝑥log𝑛)。
代码：61681335
*D. Complete Tripartite
有 𝑛(3≤𝑛≤105) 个点 𝑚(0≤𝑚≤min(3⋅105,𝑛(𝑛−1)2)) 条边的无向无自环无重边图，需要对每条边染色（1,2,3），使得每种颜色自己的点之间没有边，其余的必须两两有边，求一种方案或无解。
直接模拟即可……
代码：61681851
*E. Another Filling the Grid
有一个 𝑛×𝑛 的矩阵，需要将每个格子用 1∼𝑘 的数字填充，要求每行每列都有至少一个 1，求方案数。𝑛≤250,𝑘≤109。
O(𝑛3) 的 dp 很好想，直接令 𝑓𝑖,𝑗 表示到第 𝑖 行已经有 𝑗 列有 1。
考虑转移，枚举一个 𝑡 表示这一列之前有多少列有 1，那么这些格子可以乱填，为 𝑘𝑡。其中 𝑗−𝑡 个格子只能填 1，其余格子不能填 1。这样直接转移过去即可。
由于每一行也至少要有一个 1，所以转移时一行中没有一个 1 的方案数减掉即可。
代码：61682746
结果一看题解发现复杂度可以更优。
我们考虑容斥，有 𝑖 行 𝑗 列没有 1，所以答案就是：
𝑛∑𝑖=0(−1)𝑖(𝑛𝑖)𝑛∑𝑗=0(−1)𝑗(𝑛𝑗)𝑘(𝑛−𝑖)(𝑛−𝑗)(𝑘−1)𝑛𝑖+𝑛𝑗−𝑖𝑗
当然写的好看一点也可以是：
𝑛∑𝑖=0𝑛∑𝑗=0(−1)𝑖+𝑗(𝑛𝑖)(𝑛𝑗)𝑘(𝑛−𝑖)(𝑛−𝑗)(𝑘−1)𝑛𝑖+𝑛𝑗−𝑖𝑗
这样就可以 𝑛2log𝑛 啦！
然后我们考虑继续优化。
我们观察后面那只 ∑：
𝑛∑𝑗=0(−1)𝑗(𝑛𝑗)𝑘(𝑛−𝑖)(𝑛−𝑗)(𝑘−1)𝑛𝑖+𝑛𝑗−𝑖𝑗
我们发现她可以转换成一个二项式展开的形式，也就是把后面的 (𝑘−1)𝑛𝑖+𝑛𝑗−𝑖𝑗 看成是 (𝑘−1)𝑖(𝑛−𝑗)⋅(𝑘−1)𝑛𝑗：
𝑛∑𝑗=0(𝑛𝑗)(𝑘𝑛−𝑖(𝑘−1)𝑖)𝑛−𝑗(−(𝑘−1)𝑛)𝑗=(𝑘𝑛−𝑖(𝑘−1)𝑖−(𝑘−1)𝑛)𝑛
于是最终答案就变成了：
𝑛∑𝑖=0(−1)𝑖(𝑛𝑖)(𝑘𝑛−𝑖(𝑘−1)𝑖−(𝑘−1)𝑛)𝑛
复杂度 O(𝑛log𝑛)。