好题胡扯（缓更）

~~突然发现我博客背景没图，哪位好鸽鸽能给我白嫖下 qwq~~

打 * 的是没有代码实现过的，非常容易口胡错误，欢迎指正博客中的错误。

去年的 Good Bye 2019 忘打了，补一补。

(08.23)

CF1270F Awesome Substring

根号分治。~~这 tm 想了一个午睡~~

对于 ((r-l+1)/cnt_1<sqrt n) 的部分，直接把 (0) 设成 (1)，(1) 设成 (-k) 计算。

对于 ((r-l+1)/cnt_1ge sqrt n) 的部分，可以枚举有 (k) 个 (1)，然后答案是一个等差数列的形式，可以直接计算。

然后我降智了，(<sqrt n) 的部分没想到直接开 (nsqrt n)，写了离散化，时间变成 (mathcal{O}(nsqrt{nlog n}))，不过都能过啦，无所谓。

*CF1270G Subset with Zero Sum

~~看到题解就不想打了~~

当场降智，这道题 nb。

发现 (1le i-a_ile n)，可以 (i ightarrow i-a_i)，这是一个基环树内向森林，找到其中一个环即可。

*CF1270E Divide Points

~~发现去年看过题解的题忘了~~

考虑将 (x,y) 坐标奇偶分类，检查是否能两组（即两组都有数），(00,11) 和 (01,10)，(00,01) 和 (10,11)。若都不符合，把最后一位去掉。因为 (n) 个坐标两两不同，所以一定有解。

为什么把最后一位去掉呢？

因为欧几里得距离是 (sqrt{(x_i-x_j)^2+(y_i-y_j)^2})，不能分组说明他们的欧几里得距离可以整除 (2)，所以都除以 (2) 不影响答案。

*CF1270H Number of Components

~~又 tm 不想写了，线段树 nb~~

先大胆猜想，一个连通块是一段连续的区间。~~然后我又降智用 next_permutation 验证了一下~~，发现是对了。又想了一下，设 (i<j<k)，(p_i<p_k,p_i>p_j>p_k)，矛盾。

~~然后就 sb 的套用楼房重建的方法，发现 Wrong Answer on test 2，简称 WA2~~

答案是若干个区间 (min in [l_{i-1},l_i)>max in [l_i,l_{i+1}))，那个可以数前缀 (min>) 后缀 (max) 的个数。若我们把 (ge w) 的看成 (1)，(<w) 看成 (0)，那么分界是形如 (111111111000000000) 这样的，那么可以维护 (b_i ot =b_{i-1}) 的个数，这个数至少为 (1)，且答案也是这个数 (1) 的数量，可以维护最小值和最小值的个数。线段树即可，时间 (mathcal{O}(nlog n))。注意，分界 (w) 一定是当前序列 (a) 中的某个数。

~~md，luogu 翻译里没有 a_i 互不相等，自闭了，还是看英文题面吧~~

(08.24)

CF1270I Xor on Figures

nb。

重新定义矩阵乘法，把 ((+, imes)) 换成 ((igoplus, imes))，乘法换成循环的形式，然后求 (F^{-1}=F^{2^k-1})。因为乘法是异或，所以当 (i ot =j) 时，((x_i,y_i)) 和 ((x_j,x_j)) 对答案的贡献会计算两次，只有 ((x_i,y_i)) 翻倍的贡献。时间 (mathcal{O}(kt4^k))。

(08.25)

vp 了一场 cf，发现 B 差点 tle，C 看了半天发现题意看错，其他全不会做，被吊打了。

CF1361A Johnny and Contribution

发现答案一定是按从小到大的顺序填，然后判断是否有解即可。

CF1361B Johnny and Grandmaster

出题人卡掉了我各种写错的地方，nb。

~~然后题意看错了一年~~

有一个直观的想法，按幂从大到小排序完后，前面取若干个数互相抵消，其他的数，一个集合放最大的，其他集合全放最小的，这样一定最优。可以维护一个答案，每次乘 (p^{k_i-k_{i-1}})，然后判断是否 (ge i-1) 即可。

然后我的写法有若干种要判（n 很小，k 很大）：

ans=0 要 continue，因为 ans*p 若干次都是 0。
ans>=i-1 要 break，然后要先乘再模。

CF1361C Johnny and Megan's Necklace

题意又看错了，Owen sb。

建个图，跑欧拉回路即可。有解条件：1 个连通块，所有点的度数为偶数。

证明待补。

*CF1361D Johnny and James

对于每条射线单独考虑，算一下贡献。

CF1361E,F 待补。

(08.26)

昨天太懒，今天写不太动。。。

Edu div2 好啊，没 div1 那么难，还是能做一做的。

CF1354G Find a Gift

~~为数不多会做的交互题~~

首先想到倍增。再次看到 (1le kle frac n2)，猜测这个性质有用。从大到小倍增不行，那就从小到大倍增，花费 (2log n) 次询问，接下来变成判断 (1) 是否为礼物的子问题。发现石子很多，可以随机 (T) 次，判断是否 (1) 位置小于随机的位置，错误率为 ((frac kn)^T)，所以 (T=20sim 30) 即可通过。其实 (T=20) 次就行了。

昨晚的 Edu div2F，x-prime Substrings

看到这题肯定要压状态，跑 (dp) 套 (dp)，然后 (Owen) 这个 (sb) 算了一下，(n=20)，用 (1sim 9) 拆分有大约 (10^6) 个状态，时间爆炸。一看题解，发现可以把所有的 x-prime Substrings 找出来建 (AC) 自动机，最多只有大约 (2400)，自闭了。然后……就不想写了。

昨晚的 Edu div2G，Mercenaries

一个很直观的想法是容斥，先 (2^m) 跑一跑，(mathcal{O}(1)) 算答案，然后发现时间爆炸，答案不会算，自闭了。

打防沉迷了王者一个号后一想，这只和 (m) 个限制并的大小有关！可以把所有状态找出来，(sort) 一遍去个重。然后枚举集合大小 (i)，这个 (l_jle ile r_j) 可以差分算。但是限制里也要算进去！说明我们容斥的 (m) 个限制的一个子集，可以预处理的时候做一遍高维前缀和，预处理子集的答案乘上容斥系数 ((-1)^{|S|})。注意，答案是 (cnt_i-jchoose i-j)，因为限制中的 (j) 个是要强制选的。

*AGC023F 01 on Tree

~~居然有我一眼看出做法的 F，菜鸡落泪~~

发现可以运用某 noip 模拟赛的方法，每次合并与父节点的连通块，所有点按 (frac {cnt_1}{cnt_0}) 从小到大排序即可，用 set 即可维护。

*AGC027F Grafting

出题人 nb。

假设根节点不操作，一个点的父亲在 (A,B) 树不同，则操作的顺序是 (fa_B(u) ightarrow u ightarrow fa_A(u))，像树上的数一样判个环即可。

根节点会操作的话就枚举第一次操作，加上枚举根，拓扑排序，时间 (mathcal{O}(Tn^3))。

AGC035C Skolem XOR Tree

以前做过的，忘了。大 sb。

发现 (n=2^k) 无解，因为没有其他数能消掉最高位。

否则考虑增量构造，因 (2|i,iigoplus i+1=1)，可以每次 (i ightarrow i+1 ightarrow n+1-> ightarrow i+n ightarrow i+1+n)，(1) 和奇数的情况挂任意一个分支即可。

*ARC103B Robot Arms

先发现，所有坐标 (x) 和 (y) 奇偶不同无解。否则考虑倍增，每次操作与目标点差值绝对值最大的那一维即可。

为什么是对的呢？

考虑一个数减去一个比它大二进制位，肯定把一次取反，然后绝对值 (+1) 进位。没错，这就是求 lowbit 的方法。考虑归纳。若当前在第 (k) 位，两个数都小于 (2^k) 且不相等。那么两个数下一位只有一个 (1) 或全是 (0) 可以变成 (k-1) 的子问题，否则最大的数操作后有两种情况：

在另一个数一串 (1) 后，出现两个数某一位都是 (0)，那么也可以变成子问题。
若有进位，则原来最大的数二进制拆分后是 (...1111111111)，所以一定是某个 (2^k)，所以这一位去掉就达到了目标点的一维，那么就不用管了。

诶，那这么归纳的话，保证最大岂不是要从 (2^{31}) 开始而不是 (2^{30})？这个问题我再想想。

*ARC103D Distance Sums

成功的没想到最后一步。

容易发现 (D) 在一条边的转移：(D_v=D_u+n-2 imes siz_v)。

容易发现 (D) 最小一定在重心，证明很简单，因为所有点到重心 (D) 的变化一定递减，因为重心是树上唯一/二的点 (max(siz_{son})le lfloor frac n2 floor)。

容易发现 (D) 最大一定在某个叶子。

~~然后就不会了~~

一点开题解，发现可以删叶子，然后根据那条转移找编号。重新一看题意，(D) 互不相同。

我是 sb。

AT5761 Odd Sum Rectangles

又成功的没猜到结论。Itst 写的太好了，去膜他吧（雾

传送门

看了下 Global Round 10，发现又什么都不会，被吊打了。

*CF1392G Omkar and Pies

这 tm 都可以前缀和了？？？

发现两者在最后都操作任意次相同的操作不改变，可以预处理前缀操作交换到哪里。然后 (r-l+1ge m) 的限制可以一边加点一边最短路。因为路径长度最多为 (k)，那么每个点被更新的次数只有 (k) 次，所以直接暴力即可。

*CF1392H ZS Shuffles Cards

推了一个 (mathcal{O}(n^3)) 的式子，怎么都不会，官方题解也看不懂，于是点开 luogu 的题解，发现 TA 的做法好 nb 啊。。。

期望是迭代次数乘一次迭代的期望轮数，由于每张牌的概率为 (frac 1{m+1})，根据期望的可加性，再加上抽到一张鬼牌，期望是 (frac n{m+1}+1)。接着设 (f_k) 为还有 (k) 张牌没取的期望，(f_k=frac m{m+k}(f_k+1)+frac k{m+1}f_{k-1})，发现 (f_k=f_k+frac mk)，(f_1=m+1)，所以 (f_n=1+msum_{i=1}^{n}frac 1i)。时间 (mathcal{O}(n+m))

*CF587D Duff in Mafia

zju 集训的题，又忘了。

二分答案，跑 2-SAT。约束条件是选出来的边，对于一个点的所有边，只能选一个；没选出来的边，对于一个点的同种颜色所有边，只跟选一个。发现连的边只和除了自己、并且在一个集合中的点连边，这些东西只和前后缀有关，于是前缀优化建图即可。

(08.27)

跟 ljc vp 了一场 Global Round，结果他不知为何不在状态……有点惨

CF1326A~CF1326C

A 是 233333...，B 可以直接递推（也不算），C sb 了两次，题意差点看成不用全分，最后发现前后的段长不用算进答案。

CF1326D1/2 Prefix-Suffix Palindrome

当场降智系列……

传送门

CF1326E Bombs

发现答案单调不增，可以把 >= 答案的位置 +1，标记的位置 -1，线段树维护前缀 min。记得把前面 <0 的一段去掉。

*CF1326F1/2 Wise Men

这都能容斥，nb。

把 0 的限制去掉，发现只和连续的 1 有关，剩下的就类似子集 exp。

然后我去补学了一下子集 exp，发现就是重复的位也算，只不过跟答案没关系……看完感觉 NOIOL3 那时候我怎么没看懂……我怎么这么傻……

(09.01)

前几天太懒了……今天来补坑。

前天打了一场 ZROI，开场什么题都不会，冷静了一下，发现 A 可以找规律，B 不像字符串神题，可以 manacher，C 的贡献可以 oeis，~~当然也是看到 oeis 的式子才会证的~~，然后就 1h30min 写完，打了一小时对拍，丝毫没用，后来发现大家都阿克了。

*AGC015D A or...or B Problem

一道神奇的题……

先去掉前缀相同的二进制位，假定 r 有 t 位，那么我们可以构造出 ([l+2^t,l+2^{t+1}))。

因为 or 只会使原数变大，所以接下来我们找到次高位的 1，构造出 ([2^t,2^t+2^{k+1}))，最后并上 ([l,r]) 即可。

*AGC043D Merge Triplets

找规律未果，开始疯狂猜结论，然后并没有猜到，agcnb。

首先，一定不会出现连续的四个数，(x_1>x_{2..4})，这样说明前缀 (max) 的划分不超过 (3)。

再发现一组中的三个数 (a,b,c)，若 (a>b)，那么 (a) 选后一定会选 (b)。这样的话一组可能会被分成 (1+1+1,2+1,3)，这就启发我们长度为 (2) 的段必须大于等于长度为 (1)，否则无法匹配，不然就有解，而且一定能构造出来。

那么可以 (dp)，(f_{i,j}) 表示放了最大的 (i) 个数，长度为 (2) 的段数-长度为 (1) 的段数为 (j) 的方案数，这样就可以转移了。

*AGC016D XOR Replace

看出了第一步，看来不是全看题解。

发现异或的操作等价于当前的数于全局异或和交换，那么有解的情况就是序列 (B) 的数是序列 (A) 加上全局异或和构成的集合的子集。

接着算最小操作数，将 (A_i ot =B_i) 的位置连一条边，发现答案就是边数+连通块-1，直接做即可。

*CF704E Iron Man

~~又降智了~~

先考虑在序列上怎么做。因为我们只关心最小，肯定是相对位置的前驱后继。

放在树上，树剖一下，在每条重链上做即可。

*CF1290E Cartesian Tree

还能这么做……

发现笛卡尔树的子树大小其实是一段区间，我们可以算出 (sum (R-L+1))。

接着就是支持以下操作：

区间加
区间取 (min)

吉司机线段树正反做两次即可。

*AGC021F Trinity

没救了……计数题不会做了……

首先发现不是对称的形式，且 (N) 和 (M) 不在一个数量级，猜想是 (mathcal{O}(Mpoly(N))) 的算法。

因 (A) 只和第一次加入的列有关，而且编号没有太大关系，可以 (dp)，(f_{i,j}) 表示 (i) 行每行都有至少一个黑格子，放到第 (j) 列的方案数，答案就是 (sum {nchoose i}f_{n,i})。

[f_{i,j}=(1+i+{ichoose 2})f_{i,j-1}+sum_{k<i}{i+2choose k}f_{k,j-1} ]

( ext{NTT}) 优化即可。

(09.11)

*CF983D Arkady and Rectangles

去年不会做的题，再看了一遍题解，终于懂了。

可以扫描线，然后把颜色覆盖变成时间戳最大，维护两个值，一个是可视的最大值，一个已统计过的最小值，因为如果线段树子节点所有的颜色都大于最大值，当前节点覆盖的线段就没用了。然后每次把根节
点的最大值删去，重复此过程，因为一种颜色只用统计一次，所以时间是对的。

线段树+set，时间 (mathcal{O}(nlog^2n))。

CF627F Island Puzzle

好题。

先把不加边的情况特判掉。

接着考虑加边的情况，发现连一条边是一个环，那么可以走到这个环，然后走若干圈，到达目标点。所以不匹配的点必定构成一条树上的路径。

细节有些多，有时间好好理一遍再写。

坑：抄别人的代码的时候他是 tot，我是 cov，结果我抄成 tot，但是我的 tot 是邻接表的边数，自闭了

(09.12)

上次考了两场长乐一中的题，~~感觉自己 noi 回来不挂题 buff 附体，成功把 OI 打成了 ACM，使自己的期望除以 2 到 3 的随机实数，自闭了~~

其中有三道题我觉得挺不错的，记录一下。

*D1T4 permutation

题意：随机生成一个排列，将偶数的位置排序一遍再放回去，然后分 k 段，问每段逆序对个数乘积的期望。

n^5+特判，90pts:

每段逆序对个数的乘积等价于每段选一个逆序对，(f_{i,j,k,0/1/2}) 表示 (isim n)，偶数的位置是 (j)，分了 (k) 段，(0) 表示没选右边和左边的位置，(1) 表示选了右边的位置、没选左边的位置，(2) 表示选了右边和左边的位置，偶对偶没贡献，奇对奇可以用 (frac 12) 算，奇对偶可以这样算，偶对奇还要在上述的 dp 再加一维，容斥掉，状态也加几个。

正解：

出题人 nb，将偏序关系抽象成一棵树，不是内向树的部分可以容斥，转成内向树后就是问合法拓扑序期望，可以用 (prod frac 1{siz_i}) 算。

~~严重怀疑出题人做过 Shrinking Tree~~

*D1T2 tree

题意就不说了，就是一个 trick。

若 ((u,v)) 是直径并且字典序最小，加入集合的点 (w) 要满足以下几个条件：

( ext{dis}(u,v)> ext{dis}(u,w)) 或 ( ext{dis}(u,v)= ext{dis}(u,w),v<w)

对于 (v) 类似。

那么是否有 ((a,b)) 满足上述条件却是直径呢？事实上是没有的。

证明的话将 ((u,v)) 的路径抽出来，考虑不以任何点为根，这里的子树指除了这个点在 ((u,v)) 路径上相邻的点、能到达的点。显然 (a,b) 不在 (u) 或 (v) 的子树里，接着发现 ( ext{dis}(a,b)le ext{dis}(a,u)+ ext{dis}(b,v)- ext{dis}(u,v)le ext{dis}(u,v))，Q.E.D。

*D1T3 cactus

题意：求一个仙人掌邻接矩阵的行列式。

~~退役吧 sb~~

发现交换两个数，逆序对的奇偶性只改变一次。证明的话……有更简单的证明，不过行列式交换两行会取反，不就行了。

接下来就是仙人掌覆盖所有点的问题，一个环的贡献是 (2 imes (-1)^{len-1})，一条边的贡献是 (-1)，在圆方树上 dp，分圆点和方点讨论即可。

~~还有我考试的时候把 k-Nim 的结论记错了，转成二进制的我转成了 m 进制，报警了~~

~~我也并不知道在扯啥，就把 CF & Atcoder 好题胡扯改成了好题胡扯~~

记录几道一眼题。

*CF627E Orchestra

枚举矩形上边界，用双向链表即可做到 (mathcal{O}(n^2k))。

*CF639F Bear and Chemistry

先 tarjan 缩点，对于每个询问建出虚树，再把边放进去，跑一遍 tarjan 即可。

*CF671D Roads in Yusland

整体 dp 即可。

线性规划的做法待补。

~~在题解区看到 Fading 的题解，Fading 居然做过这道题还没做出来 NOID1T2，有点惨~~

还有一道以前看过题解的题。

*CF643G Choosing Ads

将区间众数的方法拓展到 (p\%) 上即可，用线段树维护 (lfloor frac {100}p floor) 个数即可。

(09.14)

CF1320D Reachable Strings

这类题不会，打 ZROI 被暴打了……

题解

*ZROI Round3 B

相同的长度为 (k) 的串取反等价于将 (0/1) 平移 (k) 位，这样可以把连续 (k) 个删掉，直接判断即可。

C 我写了个暴力，大概是 (6 imes 10^8) 的状态+一大坨剪枝，就过了……我谔谔

ZROI Round3 A

补一个证明，考试的时候想到的。

证明：有一个 (n) 个点 (m) 条边的图，(m>0) 时，(>frac m2) 的割（异色边数量）一定存在；(m=0) 时，一定不存在。

(m=0) 时显然。
(m>0)，考虑局部调整。一个点取反，若与他相连有 (i) 条异色边，那个 (Delta ans=deg-2 imes i)。这就告诉我们，度数只要有奇数就一定有解。若度数全为偶数，那么只需判断是否只存在 (=frac m2) 的方案，即每个点的度数平分。

考虑继续调整。当 (m>0) 时，一定存在一条异色边，同时取反与异色边相连的两个点，(Delta ans=2)。所以一定有解。

AGC022F Checkers

LH 讲过，所以去补了一下……具体看 FJ 省冬的课件吧。

*CF1375H Set Merging

这都能分块……确实，用值域分块拟合序列分块，可以分治。答案在每个块查一遍即可。

理论上可以用归并排序、双指针让时间去掉一个 (log)，但数据很小，没什么意义……

(09.15)

*CF1396D Rainbow Rectangles

比赛的时候想到了枚举左边界，想到了 set 维护，就是没想到把插入变成删除，使得答案跟改变的方向（max -> min）一样，~~退役吧 sb~~

*CF1396E Distance Matching

orz liouzhou_101。

还有一篇匹配问题的方法也很好，极其推荐。

题解

MtOI2018 魔力环

前段时间做的，复习了一下 Polya 定理。

一个数约数之和大概是 (mathcal{O}(nlog log n)) 级别的。（以后记得要看看证明，包括质数密度啥的

还有要注意的是，若一个环没出现超过 (k) 的黑色连续段，那么它复制若干次也不会出现。

~~然后我 m=0 特判错了 WA 了一发~~

CF1349D Slime and Biscuits

推了一张草稿纸，具体的可以看 liouzhou_101 的推导。

题解

势函数和鞅的停时定理天下第一！

任务计划：

线性规划
转对偶问题
计算几何
博弈论

(09.16)

CF1418F Equal Product

没想出来，题解做法 nb。

先想到设 (largefrac {x_2}{x_1}=largefrac {y_1}{y_2}=largefrac ab)，这样虽然多引入了两个量，但是 (a|x_2,a|y_1,b|x_1,b|y_2)，所以这两个量实际上是四个量的桥梁。因 (y_2<y_1)，所以问题转化成求 (y_1,a,b)。

接下来就是套路的时间了。枚举 (x_1) 和约数 (b)，发现就是支持询问区间大于一个数的最小值。刚开始我写了单次 (mathcal{O}(log^2 n)) 的线段树+vector，本想改成 (mathcal{O}(log n)) 的主席树，发现刚刚是 ( ext{MLE})，空间不变……

在线不行考虑离线，从大到小枚举 (b) 和倍数，这样就只用线段树维护区间最小值了。时间 (mathcal{O}(nlog^2 n))。

坑：判 (x_2=x_1 imes largefrac ab) 的时候要转成 long long，不然会 WA。

*CF1261F Xor-Set

用字典树将区间分成 (log w) 段，答案只和前缀较长的区间有关，直接算即可。

(09.19)

打模拟赛，写子任务的时候忘了保留恰好 5 位数字，直接输出整数，自闭了。又想偷懒用 long double 代替 __int128，成功的又自闭了。

CF1218B Guarding warehouses

计算几何好题！

然而 p_b_p_b 的做法看懂了，细节不会写，去借鉴 cz_xuyixuan 的了……

cz_xuyixuan 的做法：极角排序，对于每个极角序区间开棵线段树，然后在线段树上插入线段。因为除了凸包相邻的线段，其他两两不交，所以只需考虑极角序区间中点引出的射线到凸包线段的距离。维护距离最小值和次小值的线段，面积可以用叉积算。

坑：下传标记的时候哪条线段不要写错，还有注意求交点的时候向量不要搞反，注意各种共线的特判，atan2 是从 x 轴负半轴逆时针旋转的，情况很多，有一种没判就可能导致求交点的时候输出 nan。

CF1025F Disjoint Triangles

~~退役吧 sb~~

枚举公切线，只需考虑平面右边点的个数，注意到内公切线会被算两次，所以我们只需考虑 atan2<=0 的情况。

(09.20)

md，昨天打 ZROI，吃完饭 20:00，打 B,C 无果，最后一小时发现 A 是个 dp，写完 21:40。我想：反正 20 分钟我暴力也写不完，数据也不好造，就不写拍了吧！

~~WDNMD，以后有时间不写拍，pei，不写拍我就是 sb。~~

Owen_codeisking 8:15:46
我刚开始写的是对的/kk

Owen_codeisking 8:15:56
然后策略弄错了/kk

Owen_codeisking 8:16:09
就把 E 中间的式子改错了/kk

Owen_codeisking 8:16:23
然后尝试输出 E，发现跟答案没什么关系/kk

Owen_codeisking 8:17:01
要是我刚开始就输出 E，可能就 A 了/kk

分享一个 sb 的比赛经历。

(09.21)

*CF733F Test Data Generation

好题！感觉在什么模拟赛见过加强版。

考虑 (sum [2|i]{ichoose j}) 的组合意义，(f_{i,j,0/1}) 表示长度 (le i) 的序列，染黑 (j) 个位置，(i ext{mod} 2=0/1) 的方案数，倍增 + MTT 即可。或者根据题目所求的，设最后一个位置是奇数还是偶数。具体的：（第二种解法）

[F(2a,p)=F(a,p)+(F(a,0)+F(a,1)+1) imes F(a,pigoplus (a ext{mod} 2)) ]

*「2017 山东三轮集训 Day7」Easy

~~怎么对 DS 选手这么友好~~

可以使用 Border 的四种求法中的方法，树剖后用可持久化平衡树维护一条重链链头到当前点轻儿子的距离最小值，或者动态点分治。

*「JOISC 2020 Day1」扫除

nb。

还得培养子任务对我的启发能力。

题解等我写完再更。

*Codechef MARCH17 Sum of distances

最短路等价于从一段支配点出发，分别计算它们到起点和终点的距离，合并这些距离。所以这题连续三个数构成一个支配集合，即删掉它们原图不连通。接下来用树状数组做二维偏序。

*「WC2018」即时战略

定期重构动态点分治或 LCT + 重链上二分，后一种做法找到点后要 access 一次，保证复杂度。

对了，找到我模拟赛有一道哪里挂分了。我设 sf 是子树的 min，f 是当前的值，上传的时候 sf[v]=min(sf[v],f[u]);

报警了报警了。

(09.30)

咕咕咕。

ARC078F Mole and Abandoned Mine

写了一个 (mathcal{O}(3^nn^2)) 的解法过了，发现分两步转移就少掉一个 (n) 了，我是 sb。

*AGC033C Removing Coins

思维好题，转成取石子游戏。

ARC068F Solitaire 待补。

*AGC028C Min Cost Cycle

发现 min 和最小是同向的，所以把 min 去掉，改成选点，考虑不合法的连边情况，用堆维护即可。

*AGC028D Chords

区间 dp，方法和计算 (n) 个点的连通块个数差不多，正着不好算就反着算，容斥掉不合法的方案即可。

AGC028E,F 待补。

*AGC034C Tests

发现经过调整，可以做到只有一个 (in (0,X))，剩下的贪心取。二分后枚举特殊的是哪个即可。

*AGC034D Manhattan Max Matching

发现 max 和最大同向，把 max 拆掉，跑费用流。

*AGC034E Complete Compress

我怎么把枚举聚集的点忘掉了……

*AGC034F RNG and XOR

看来我 FWT 没学好啊……

题解

*DPC6 E Span Covering

好题！跟 ZJOI2012 波浪的 dp 思想有点像，都是边 dp 边确定状态，并且这种状态能唯一表示一种方案。

这道题的状态即为线段覆盖的左端点相对顺序和相邻左端点之差。

而前者可以使用插入法，后者可以边 dp 边确定。

考虑插入法，而极长段的合并不好合并，考虑长度从大到小插入，这样最多只会合并两个极长段。而且这样的话，dp 的时候极长段个数之和是调和级数级别的。（很多题解说是线性的，有些不懂，不过常数很小，可以忽略不计？）

接着就是推式子的时间了。

(10.2)

昨天回去看了一下 THUWC2020 的数据结构题，刷新了我对数据结构题的认识，特别是 D1T3,D2T2,D2T3 这三道题目，虽然解法对于见过类似题目的人略微有些套路，但是这些 idea 还是很好的。

（具体题解有些长，看别人的吧）

看了一场 agc，差点 A 都不会做，这真是。

*AGC040C Neither AB nor BA

没想到。

将奇数位置的 (A) 改成 (B)，转化为相同的 (AA) 和 (BB) 不能取，用总方案数-不合法的方案数，组合数算一算即可。

*AGC040E Prefix Suffix Addition

不可做题 (mathcal{O}(n)) 系列……

先想只有前缀的版本，设 (A_0=A_{n+1}=0)。因为要求加的是不降序列，所以考虑 (A_i>A_{i+1}) 的位置，称这些位置满足性质 (X)。

Observation 1. 若位置 (i) 没有操作过，则不可能一次操作同时消去 (i) 和 (i+1)。

证明不难。若操作的位置 (<i)，则没有影响；若操作的位置 (>i)，因为 (x_ile x_{i+1})，所以 (A_i-x_i>A_i-x_{i+1})，满足性质 (X)。

由 Observation 1，我们发现答案至少为满足性质 (X) 位置的个数。考虑构造，每次操作 ((A_1,A_2,...,A_i)) 即满足条件。所以答案取到下界，问题转化为将 (A) 分成两个序列 (x,y)，(x_i+y_i=A_i)，最小化 (ans=sum_{i=1}^n [x_i>x_{i+1}]+sum_{i=1}^n [y_{i-1}<y_i])。

直接 (dp) 不是很行，看看这个式子有什么性质。

Observation 2. 若填完 (1sim i) 后某些 (f_{i,j}) 相等，那么 (j) 越小越优。

Observation 3. (f_{i,j}le f_{i,0}+2)

由 Observation 2,3，我们只用记录最小和严格次小的方案即可转移。时间 (mathcal{O}(n))。

(10.07)

感觉有点咕，开个待做清单。

	(A)	(B)	(C)	(D)	(E)	(F)
(1)	✔	✔	✔	✔	✔	*
(2)	✔	✔	✔	*	✔	✔
(3)	✔	✔	✔	*	*
(4)	✔	✔	✔	✔	*	*
(5)				✔		✔
(6)	✔	✔	*	✔	✔	*
(7)	✔	✔	*	*	*
(8)					*
(9)			*
(10)			*
(11)			*	*	*
(12)		*	*	*		*
(13)				*
(14)					*
(15)			*	*	*
(16)				*	*	*
(17)				✔
(18)			*
(19)						*
(20)
(21)			*	✔		*
(22)					*	✔
(23)					✔	*
(24)					✔	✔
(25)
(26)
(27)				*		*
(28)			*	*	*	*
(29)
(30)				*		✔
(31)
(32)					*
(33)			*	*
(34)			*	*	*	*
(35)			✔	✔	✔	✔
(36)
(37)
(38)			✔		✔
(39)
(40)	✔	✔	*		*
(41)
(42)
(43)			*	*
(44)			*	*
(45)
(46)
(47)	✔	✔	✔	✔	*	*
(48)	✔	*	*

(10.14)

CF1381E Origami

CF1175G Yet Another Partiton Problem

CF538G Berserk Robot

CF494E Sharti

SP11414 COT3 - Combat on a tree

(10.15)

ACL1D Keep Distances

老年人不行了，D 都不会了……

思维好题！（滑稽.jpg）

总结：这类题目可以寻找极大和极小的值来得到一些强的性质。或者可以写个暴力，打表发现决策区间恰好有最大答案个，而且左端点/右端点都是极小/极大的点。

（当然，直接看题解懒得打暴力就无法发现这些性质了）

ACL1E Shuffle Window

注意到打乱顺序只能确定第一个数的位置，所以把题意转化成不断的 push 和 pop，开始 push k 个，最后 random_shuffle k 个，然后用树状数组算一算贡献。

总结：若只是 swap 两个数，逆序对可以对于两个位置算贡献，任意打乱的话，直接算两个数的相对位置顺序会好算很多。

ARC104F Visibility Sequence

这题跟多校的 Kcats 十分相近……我 TM 比赛的时候 E 打不出来，F 没开，感觉亏大了。

(10.16)

怎么最近天天打比赛 E 不会，F 又很傻……

*CF1422F Boring Queries

简单题，考虑根号分治，(le sqrt{n}) 开 (maxp=86) 棵线段树，(>sqrt{n}) 开一棵主席树，因为最高幂次只有 (1)，可以用 HH 的项链的方式维护。

不过有更 nb 的……将 (>sqrt{n}) 的方法拓展一下，因为 (log_p maxa) 最多只有 (17)，可以对于每个幂次维护一个单调栈。因为最多只有 (log n) 个指数，时间与空间相同，(mathcal{O}(nlog nlog maxa))。

*CF1422E Minlexes

我一直在想怎么贪心……我是不是 sb……

记一个后缀的答案，发现是一个 naive 的比较字典序大小，倍增 hash 即可。

(10.17)

ARC 好难……

*ARC105C Camels and Bridge

想了很久，发现差分约束限制有 m 个，过了一会儿发现可以反向思考，询问一段前缀的最大值，于是跑最长路即可。

ARC105D Let's Play Nim

发现使若干个数的和 xor=0 的局面很少。接下来，先奇偶讨论。

若 n 为奇数，则先手在 nim 游戏中是后手，使得 xor=0。那么无论先手选择什么，后手都选择剩下最多的金币加到最多金币的盘子中，这样一定后手必胜。

若 n 为偶数，则先手在 nim 游戏中是先手，使得 xor!=0。那么只有一种情况后手必胜，即所有相同的数出现的次数为偶数。因为先手无论怎么选，后手都可以将加上的数抵消掉。其他的情况先手只要每次选择剩下最多的金币加到最多金币的盘子中就一定必胜。

ARC105E Keep Graph Disconnected

我 TM 写的代码和想的是两个东西……看完题解发现自己就是对的……

首先考虑 n 是奇数的情况，这种情况因为 xy=0，和怎么操作无关。

再考虑 n 是偶数的情况，题解是考虑什么使得奇偶性改变，我是考虑什么时候先手要必胜的话 xy 是奇数还是偶数，发现 x=y=0,ans=1 和 x=y=1,ans=0 的局面一定后手必胜，因为每次先手转换到 x=0,y=1 或 x=1,y=0 局面后手一定能找到一个奇连通块，将它还原。其他的情况先手能通过类似的策略必胜。

ARC105F Lights Out on Connected Graph

好，我二分图都没看出来……

首先连通二分图只有两个染色方案。考虑用所有的染色方案减去不合法的染色方案，容斥一下。

坑 1：因为枚举的是某种颜色子集，所以要 /2，初始值 g[0]=1，枚举子集包括 i 本身。或者可以把 0 也算进去

坑 2：注意容斥的时候要选 lowbit(i)，而且这个连通块不能包含 i，即全集。

ARC096C Everything on It

容斥即可。注意子集族的子集个数是 (2^{2^n})。

*ARC098F Donation

神题！

先转化 (c_i=max(a_i-b_i,0))，表示经过一个点最大的点。图中的边权就是 (max(c_u,c_v))。然后找最小生成树，做一个类似点分治的过程，找 (c_i) 最大的点，然后分成多个子问题。因为根的权值大于等于子树的权值，所以答案只和最后选了哪个子树有关。最小生成树可以用并查集建出来，时间瓶颈在排序上。

(10.18)

昨天打 ZR，正解莫队+分块，我写了分块+bitset，常数翻倍，愉快失去了阿克的机会。（怎么那题是我 yy 过的 idea，我也写过 Ynoi 的题，只想到了次优解，报警了报警了）

今天打 cf(div1+div2)，F 的做法过于麻烦，最后没调出来，然后发现我写了两个相似函数，发现有一个函数有些错误（线段树上二分用了 else if），还在另一个函数写了备注，记得要改掉，结果只改了一个，愉快的爆了，最后赛后 2 分钟 AC 了。

以后再 TM 写代码犯强迫症我。。。。。。（此处省略一万句 flag）

记得上次还启发式合并还原的时候没有用可撤销并查集，一整场没调出来，我。。。

口胡 luogu 月赛：

*lg10月月赛IIA 梦中梦与不再有梦

把 1 和 2 判掉，奇数有欧拉回路，偶数的应该是边数-n/2+1。

*lg10月月赛IIB 深海少女与胖头鱼

枚举开始删掉了多少个没圣盾的鱼，接着攻击有圣盾的鱼时，其他鱼都有了圣盾，期望成了一个等比数列状物，算一算即可。

*lg10月月赛IIC 蝴蝶与花

发现 (n,mle 2 imes 10^6) 而且输出的左端点还要最小，那么这个 (val={1,2}) 肯定有很强的性质。

先 check 一下 l=1 有没有答案，没有，~~则找到最靠左的位置 (l') 使得 (val_{l'}=1)，判一下 (l=l'+1) 有没有答案即可。~~则找一下 LCP，这样既能保证和最大，又能讨论所有情况，显然最优。

~~昨晚和 cyw 交流了一下做法，发现自己的做法伪了，然后想了半天 LCP 不怎么会快速求，自闭了~~

upd: 我又自闭了，当时想对了一半，实际只要找右边最靠近 (l,r) 的 (1) 就行了。

*lg10月月赛IID 象棋与马

先把式子列出来，猜测 (gcd(a,b)=1 ext{and} a ext{mod} 2 ot=b ext{mod} 2) 即可。具体证明不怎么会，想到了再补。

接下来就是把 (frac{1-(-1)^n}2) 和 (frac{1+(-1)^n}2) 代进莫比乌斯反演的式子了。

待做：

hdu 6773 King of Hot Pot
hdu 6791 Tokitsukaze, CSL and Palindrome Game
以及很多当时多校不会的题。
Lyndon 分解法
BM 求递推式
JOISC2020

找到一些 nb 博主：

CF1428D Bouncing Boomerangs

坑 1：注意 (a_i=3) 的位置可以重复利用

坑 2：注意 (a_i=3) 是优先从大到小，因为要让这些位置重复利用。

(10.19)

*CF1307F Cow and Vacation

好题！把 k 转成控制半径（即/2），用 bfs 将距离 <=k 的点加入并查集，最后起点和终点都向目标点跳 k 步，倍增即可。

HHKBPC2020F Random Max

~~看着非常模板，但是我就是不会均匀分布的概率期望~~

先套路的分成 (2N) 段，类似扫描线，整体维护一个多项式，支持乘或除一个一次式，然后每段算答案时把多项式积分一下。积分这部分要用分部积分法。

~~怎么感觉我没学过微积分一样，高数水平为 0~~

坑 1：一次式的常数是 0 时，多项式除法要特判，循环移位一次。

坑 2：注意算区间的答案时扫描线端点要 (>lmax)，除法不用。

(10.20)

zju第一次集训Day9E Epah

(nle 10^5) 的完全二叉树上，点权为 ([0..a_i]) 内随机实数，求形成堆的概率 ( ext{mod} 998244353)。

坑：在子树的多项式加的常数是 (F_j(b_j)) 而不是 (F_j(b_i))，因为子树的多项式只需满足子树的限制。

(10.21)

AGC024E Sequence Growing Hard

注意 dp 数组的定义是大小为 i 的森林，根节点最大值为 j 的方案数，转移枚举最小的 dfn。

AGC021C Tiling

构造好题！考察了黑白染色，直接构造等知识点，给出题人点赞！

AGC021E Ball Eat Chameleons

考虑分类讨论+调整。

*AGC025D Choosing Points

*CF1299D Around the World

将本质不同的线性基都预处理出来，然后跑类似 dp 套 dp 的东西。时间 (mathcal{O}(cn),c=374)。