NFLS Contest 记录
之前本来是想每天每题都写，感觉太唐了不是吗？而且肯定来不及。
现在和别人的差距还很大啊。不能摆了！
记录每天比赛情况/排名，挂分情况，以及订正题目的总结与之后计划。
一 、4题 IOI 赛制
cb 想让我们轻松一点，于是一开始是 IOI 赛制？
12.11 省选训练赛5
总结
100+15+0+90 rk22
T4 是个放 $O(nk\log ^2n)$ 而不放 $O(nk\log n)$ 正解的傻逼题。T3 是个很妙的数据结构维护 dp。T2 不会反射容斥也认了。
T2 头文字 O
根据期望的线性性这 $m$ 个规则是独立的，可以独立计算。
先考虑部分分。部分分去掉了 $s_i$ 的限制，也就是走到 $t_i$ 即可。考虑用总共的减去走不到 $t_i$ 的，观察发现就是给定一个二维网格，不经过 $y=t_i$ 这条直线的方案数。这样可以套用一条直线的反射容斥计算。
部分分会做了，考虑正解。不妨假设 $s_i\le 0\le t_i$ 的情况，其实是和 $(s_i,2s_i-t_i)$ 的情况是一样的，也就是把 $t_i$ 对称过去就不用考虑 $s_i$ 了。就转化成了部分分的情况。
复杂度 $O(n+m)$。
T3 慈善
同 https://www.luogu.com.cn/problem/CF856F。
先离散化成一堆区间。
考虑维护二元组 $(x,y)$ 表示第一个人选了 $x$ 个，第二个人选了 $x$ 个。如果当前加入的只有一个人选我们贪心的选择加入。否则剩下的情况是两个人一起选。考虑一个反悔操作，把 $x<y-C$ 的区间拿出来 $y\gets x+C$ 以后两个全加，先让 $x$ 增加到 $y-C$ 在一起加，或者 $x,y$ 不在一起玩每次只加一经验。
容易发现第一种和第二种的操作是本质相同的。但这样每次状态数还是会 $\times 2$。
继续发现对于 $x<y-C$ 的二元组，选 $x$ 最大的更优，$y<x-C$ 的选 $y$ 最大的。每次只需要新建这两个节点。我们维护以 $x-y$ 为权值的平衡树，要做的操作有区间加上一个数，新建节点，查询 $x/y$ 最大的数。用无旋 treap 即可。复杂度 $O(n\log n)$。
12.16 省选训练赛 8
100+5+70+40 rk17
T2. mwhak
是我一直不会的博弈论题，一定补。
T3. 数据结构
原题 「ROI 2016 Day2」二指禅。
考虑一个暴力，设 $f_i$ 表示匹配到 $i$ 的最小花费。建正串和反串放到 trie 树上匹配，每次一个修改一个查询（实际上是刷表和查表），容易实现到 $O(nL)$，其中 $L$ 是最大长度。
但是这样最大长度大的很多不就寄了吗。
12.19 省选训练赛9
昨天学习了 slope trick 和整理了一下凸性 dp 的优化。
总结
100+40+0+50 rk23
今天感觉 T3 连个 $O(n^2)$ 暴力没搓出来不应该啊！T1 感觉其实还挺难的，但是为什么是个人都切了？T4 是个人类智慧构造，拿满部分分就跑很正确。T2 就差一步正解有点可惜，但是正解还是有点妙妙的。
T1 圆弧
先考虑枚举颜色为 $1$ 的选的点，只有三种情况，选了就可以把环断成链了。
然后就是求最大匹配的方案数。我的做法是先求出以 $i$ 结尾的最大匹配。然后根据上一个的转移来求方案数。因为选择同一种颜色的两个区间是相交的，选了一个另外一个一定不会选，所以只需要前缀和前缀最大值搞一搞就好了。
复杂度 $O(n)$。
T2 整除
先考虑把右边变成 $\dfrac{x^m-1}{x-1}$，然后左边乘上 $x-1$，这样的形式显然更好一点。
发现左边做大除法就是对每一项的系数对 $m$ 取模，取模之后柿子的次数最大到 $n-1$。接下来的讨论默认在取模之后的柿子下。
如果这个式子所有项的系数都是 $0$，那么显然就是有无穷解。否则因为这个式子的最高项数只有 $n-1$，记这个式子为 $F(x)$，容易发现对于充分大的 $x$，有 $F(x)<x^m-1$，因为系数的原因，所以 $x\le 2n=O(n)$。
我们枚举这个 $x$，判断其是否满足 $F(x)=k(x^m-1)$。再枚举这个 $k$，容易发现 $k\le \dfrac{n}{x}$，对于一个 $x$，只有一个 $k$ 满足。然后对 $x^0$ 项加上 $k$ ，暴力判断是否满足。
判断的方法也很巧妙，把它的每个系数看成一个 $x$ 进制数，从 $x^0$ 开始暴力进位。最后是其倍数当且仅当其他项都为 $0$，$x^m$ 这一项的系数为 $k$。
用 map 维护，复杂度分析一下是 $O(n\log ^2 n)$ 左右的。
T3 词典
考虑暴力 dp。
12.20 省选训练赛10
总结
80+100+36+0 rk36 创造新低。
今天因为 T1 一直没找到 hack 自己的数据，再加上误判了 T3 的难度没有想到线段树直接暴力维护，很想拿 T1 的 20 分导致 T1 T3 一个也没拿到。
发现这种 T1 但是有点细节的，老是想不到一些情况。是不是得加练啊？
技不如人。
T1 炮塔
没想到可以往回拿的情况。警戒。
首先如果有一堆东西挡住，那么假设我们在空地上且手里有 $2$ 个，那么一定可以把前面除了 *## 这种情况以外全部拿完并且回到原来的位置。上面这种情况不拿是不劣的，我们就把它放在这里。
首先如果已经有两个，可以在走过的地方来回穿梭，.#** 就 *#* 然后过去把右边的那个拿过来同理。如果有连续的两个 #，我们之前已经在那里放了一个利用那个就可以通行。这样回去也同理。
现在我们考虑什么时候可以只用一个拿到前面的。很显然 *#.* 这样过去再拿回来即可。
也就是说如果有 *#.#. 这样的挡在这里，那么前面的当且仅当后面手上的拿着的大于等于 $2$ 就可以把前面的全部拿完。
复杂度 $O(n)$。不需要栈。
T3 欢乐豆
T3 是 $m=6000,O(m^2\log m)?$，而且还是线段树。感觉没什么意思。线段树模拟 dj 即可。其余的边直接分段覆盖扔进去。
当时脑子不清醒导致全在想堆才什么都没做出来。警戒。
T4 Musician
方心童跟我讲多项式分治 NTT 不用会，会个暴力卷积就好了。虽然我这题暴力都没推出来。考试的时候想了一下容斥但是觉得限制太多不好搞。如果脑子清醒的话应该不难吧！
先考虑一个暴力。
令 $f_i$ 为 $s=s[1,i]$ 的答案。考虑容斥，每次减去最小 border 的方案数可以做到不重不漏。因为有 $v_i$ 单调递增，所以有每个 $j\le i/2$ 必定存在一个方案使得其成为整个串的 border。
有转移
$$
f_i=\prod\limits_{j=1}^n v_j- \sum\limits_{j=1}^{n/2} f_j\prod_{k=j+1}^{i-j} v_k
$$
记 $s_i=\prod_{j\le i}v_j$ 表示前缀积。重写上面那个式子有：$f_i=s_i-\sum_{j\le i/2} f_js^{-1}{j}\cdot s{i-j}$，就是一个卷积的形式。记 $r_i=f_is^{-1}i,t_i=s_i$，对所有 $j\le k$，有贡献 $f{j+k}\gets -r_jt_k$。分治 NTT 即可。有 $1/2$ 常数。
然后发现最后一个包过不去。发现只需要分治到 $n/2$，最后算 $f_n$ 手动算一遍即可。复杂度 $O(n\log ^2n )$，常数很小。
12.21 随机化练习
12.22 省选训练赛 11
总结
90+100+50+0 rk36 持平记录。
今天赛前本来是想重回前 20 的，但是还是输的很惨。
今天为什么有 10 个 AK 的呢？
今天最大的败笔就是 T4 暴力没写，一直在推一个难写的 dp。如果拿到 $O(n^3)$ 的分其实今天排名还是可以看看的。
害，。我不想被别人看不起。
这几天最温暖的时候还是老叶说不会的搞懂就好了，慢慢来。
希望他不是只是不想管我罢了。
T1 小明去旅游2
树套树被卡常。看来之后有必有学一下 cdq 分治了。
T3 路
T4 一般难度的推式子题
EI 题。暴力没写出来，警戒。想到组合意义了但是没有任何思路，警戒！！！
那就先讲一下暴力吧。令 $f_{i,j}$ 表示子树大小为 $i$，高度 $\le j$ 的方案数。
正解其实和 dp 没有太大关系。考虑一个严格弱的问题，树大小为 $x$ 的方案为多少。推一推发现是卡特兰数。
所以考虑组合意义求 $f_{i,j}$。回顾卡特兰数的推导，用欧拉序的出栈入栈理解，起点 $(0,0)$，终点 $(n-1,n-1)$，入栈 $y+1$，出栈 $x+1$，不能触碰 $y=x-1$ 的方案数。
加上 $j$ 的限制，也就是又加了一条直线 $y=x+(j+1)$ 不能碰。用经典的反射容斥做。$j$ 的反射次数是 $O(\dfrac{n}{j})$，最后复杂度是 $O(n\ln n)$ 的。
12.23 省选训练赛 12
二、3题 OI 赛制
回归 OI 赛制。
12.25 省选训练赛 13
总结
100+0+48 rk20
T1 是原题，联赛前刚做过。T3 是妙妙构造。其实 T2 结论已经被我搞出来了，但是 T3 构造玩了三个多小时没时间写了。再加上要吃饭就没时间了。
下次要合理分配时间。觉得一道题是乱搞题或者要花费的时间很久的情况下，起码给另外一题搓个暴力出来再写。
T3 P8984 [北大集训 2021] 末日魔法少女计划
把 $A_{i,j}=1$ 的看成 $(i,j)$ 的有向边，一开始给你一个 $1\to 2\to \dots\to n$ 的链。$(A^k)_{i,j}$ 可以理解为 $\forall i<j,i\to j$ 的最短路 $\le k$。我们需要添加的边尽量小。
$k=1$，全部连起来。
$k=2$，考虑分治，$[l,mid)$ 向 $mid$ 连一条边，$mid$ 向 $(mid,r]$ 连一条边。能通过 $k=2$ 的点。
$k\ge 3$ 的情况，考虑分成 $B+2$ 块的数。有 $B+1$ 个中间点。第 $i$ 个中间点连接第 $i$ 个块和 $i+1$ 个块的每个点。然后对每个块和这 $B+1$ 个点可以归成子问题，递归下去。第 $1$ 个块和最后一个块只连一次边，中间的其他块要连两次。
考虑用 dp 来精细实现这个过程。根据对称性，让两侧大小相等，中间尽量平均，使得边数在不会太劣的情况下减少转移的难度。记 $f_{k,n}$ 表示当前 $n$ 个点加上至少 $f_{k,n}$ 使得最多经过 $k$ 条边所有点可以互相到达。
直接转移是 $O(n^3k)$ 的，考虑根据上面的情况，我们构造中间状态 $g_{k,n}$ 表示 $n$ 个点的中间块最多经过 $k$ 条边使得所有点可以互相到达。
有转移：
$$
f_{k,n}=\min{2\times (f_{k,i}+i-1)+g_{k,n-2i} }
$$
$$
g_{k,n}=\min{f_{k-2,j+1}+w1\times (f_{k,w}+2w-3)+w2\times (f_{k,w+1}+2w+2-3))}
$$
其中 $j$ 表示枚举的中间块的个数，$w=\dfrac{(i-j-1)}{j}$ 表示块的长度，$w1=j-(i-j-1)\bmod j$ 表示中间长度为 $w$ 的块的个数，$w2=j-w1$ 表示长度为 $w+1$ 的块的个数。转移体现了中间均分。
最后记录最优转移点，输出方案。复杂度 $O(n^2k)$。
12.26 省选模拟赛 14
总结
0+10+0 rk41 有分垫底。
今天算是体会了什么叫做调题调一场。
T1 感觉是个思维题看了两眼就先跳了。T2 发现只要维护路径交的最小值即可。然后调到 11 点发现复杂度假了。标记永久化没怎么写过再加上没发现修改的性质到最后也没写出来。就交了个复杂度错的东西上去。T1 懒得写直接摆烂。T3 看都没看。
赛后发现 T2 每一次加入和删除的区间是同一个啊！！！用可删堆维护一下就好了。T1 数据很水赛时随便糊了一个随机化做法应该随便过。T3 是人类智慧看了也不会做。
今天 T2 还是技不如人。要是写过这种题应该 2h 就过了。
T1 998244o5o
因为 $1$ 操作显然是没有用的，就不管他。只有 $2$ 操作就变成了下面这道题：
CF778D https://www.luogu.com.cn/problem/CF788D
如果问到一个点 $(x_0,y_0)$ 的最小距离为 $0$，则可以用两次随机化操作判断 $y=x_0$ 这条直线。$x=y_0$ 同理。
否则，设这个距离为 $d$，则 $(x_0+d,y_0+d)$ 和 $(x_0-d,y_0-d)$ 至少有一个为 $0$，然后递归下去。
考虑给自己加点条件，在直线 $y=x$ 上询问也是等价的，也就是 $x_0=y_0$。每次找到一个直线以后，往两边递归下去即可。
T2 告别
转化为对于每种权值的路径取交以后覆盖，查询一条路径上被覆盖到的最小权值的边。
取交以后树剖放到线段树上。要维护区间上的每个点加入一个数，一个区间上的点删除一个数，查询一个区间上的最小值三个操作。
直接做有点难。但是考虑每次取交的时候，如果先把取交之前的区间的贡献删除，这样对于一个权值，相邻两个加入和删除的操作的区间是相同的。用可删堆（两个堆一个维护值一个维护删除的数）做标记永久化即可。复杂度 $O(n\log^3 n)$，但是树剖和堆的常数很小。
还找到了一个路径取交的好写的姿势：设两条路径的端点分别为 $(a,b),(c,d)$，不同路径的端点两两求 lca，取两个深度最大的点 $x,y$：
- $x\not =y$，那么 $(x,y)$ 就是新的路径交。
- $x=y$，且 $x$ 的深度小于 $lca(a,b)$ 或者 $lca(c,d)$ 那么就无交。
- 否则路径交为 $(x,x)$。
T3 被猫猫入侵的题面
T3 好像是神仙博弈题目，先放了写点 dp 去。
12.27-12.28
神仙凸性优化专题。
做了快一半了。咕咕。
12.29 省选模拟赛 15
100+0+20 rk37
为什么 T2 充要条件都推出来了还是不会
为什么 T2 充要条件都推出来了还是不会
为什么 T2 充要条件都推出来了还是不会
今天 T2 暴力没搓。现在感觉想 dp 反而不会暴力了。而且正解也不难。
这几天确实摆的太厉害了。比赛正解没调出来就摆了。感觉要被老叶讲了。
为了 T3 学了个 LGV 引理。还是感觉很神秘啊还是不太会用。
T2 吴冬拔寻宝
枚举宝藏的位置。
先考虑判断一个点集是否已经能找到宝藏。
令 $d$ 为选择点集的 lca，如果存在 $dis(d,r)=dis(d,x)$ 而且 $x$ 不是根也不在子树中，那么仅通过子树中的点还确定不了宝藏。
否则要所有满足 $dis(d,x)=dis(d,r)$ 的 $x$ 所在子树至少要选一个点。而且要保证 lca 在为 $d$。
总结一下能找到宝藏的条件：
- lca 为 $d$。
- 所有满足 $dis(d,x)=dis(d,r)$ 的 $x$ 所在子树至少要选一个点。
- 不存在 $dis(d,r)=dis(d,x)$ 而且 $x$ 不是根也不在子树中。
考虑计算 $\le i$ 时刻依然不满足的方案数。这样加起来就是总的方案数。只需要确保存在
令 $f_{i,j,k}$ 表示子树中已经选了 $i$ 个点，选了 $j$ 个不同的子树，是否存在一个要选的子树没选一个点，或者本身就在子树外还存在满足条件的点。
容易发现 $j$ 的意义是确保 lca 为 $d$。所以 $j$ 最大只需要到 $2$。同样 $k$ 只有 $0/1$。
复杂度 $O(n^3)$。记得特判 $n=1$ 时答案为 $0$。
12.30 省选模拟赛 16
100+55+0=155 rk15
T3 保龄是因为要去美食节。今天打的算好了，T1 的性质推出来了，T2 的反射容斥，莫队做组合数和 NTT 合并都看出来了。这种学有所成的感觉真不错。
T2 梦魇
1.1 省选模拟赛 17
0+10+5 rk34
元旦还要早八/fn 早上一来头很晕。
T1 是想到结论以后题目就搞错了。T2 是到后面发现是凸包的叉积 $<$ 改成 $\le$ 就过了。
T1 City
观察到 $m=1$ 时，取三个数中出现次数最大的那个至少有 $\dfrac{n^2}{9}$ 的价值，所以有 $m<9$ 。
然后再推一推发现有 $m\le 6$。继续发现循环节中如果一个字母出现了 $3$ 次及以上则不如全取这个字母。所以有效循环节状态很少。然后暴力匹配即可。
T2 Beautiful World
赛时大样例过了。赛后把凸包的叉积从 $<$ 改成 $\le$ 就过了。莫名其妙。
首先看这样的题目就像凸包合并。
具体做法就是把装备看成一条边，把装备栏看成一个点。然后如果合法每个联通块要么是树要么是基环树。然后把一个联通块的所有情况都找出来，树的情况是 $O(n)$ 的，基环树的情况是 $O(1)$ 的。做出凸包以后闵可夫斯基合并即可。复杂度 $O(n\log n)$。
1.2 省选模拟赛 18
65+36+25 rk33
数据结构专场，T1 inf 开小挂分，T3 update 的时候忘记 pushup 样例都过不去。T2 没看出来直径。属实是重开了。
T1 掉落
显然有个树套树做法。
然后发现线段树的每个节点维护一个栈，每次找到高度最小的弹一弹。每次最多加入两个点，复杂度是 $O(n\log n)$ 的。
T2 原神
T3 区间mex快速算法
还是之前那个对顶堆套路，先通过 set 维护区间搞一下转化为相邻的加入操作和删除操作都是一个区间。
题目的 $4$ 操作很明显后面那个东西是诈骗。$3$ 操作的本质是找给区间的 $mex$ 的最小值的位置加上一个数。
上面的操作本质是标记永久化。如果一个标记打在区间上且是这个区间的最小值，则整个区间都要加一个数。否则加东西的标记转移到子区间的较小区间上。
注意到为了防止 update 的时候影响 pushdown，在每次 update 到具体区间的时候，要额外在之前再 pushdown 一次。这样就保证之前的 pushdown 不会建立在新的节点上判断下传了。
1.5 省选模拟赛 19
这是我们搬的。所以就没有成绩。
T1 最小四贪那树
直接预处理状压 dp，然后做个 SOSdp 即可。复杂度 $O(2^nn)$。
T2 数位
每次必须要知道哪几个数是要进位的。考虑现在在第 $i$ 位。
则观察到如果 $i-1$ 位为 $x$ 的没进位，则为 $x-1$ 的必定不会进位。然后再想一下就会发现知道了有几个进位的，就知道是哪些进位的。
基数排序一下即可。复杂度 $O(10n^2)$。
T3
T3 待补。
1.6 省选模拟赛 20
今天学考，待补。
1.8 省选模拟赛 21
今天时间从 5h 改到 4.5h 没交上去，警戒！！！
T1. 盗梦空间
虚树套路题？但是我第一次写虚树。/kk
先建虚树。虚树有三种类型的点：
- 虚树本身的节点。
- 虚树节点边上的点，这样的点只连着两个点。
- 空子树的点。
第一个是好处理的，第二个预处理出 $g_x$ 表示 $fa_x$ 不包括 $x$ 的子树内深度最大。一段链上可以倍增。第三个可以先排序，给第二类的点打上标记，这样遍历到第一个没有标记的点就是最大的且合法的。
复杂度 $O((n+\sum k)\log n)$。
Update：做了虚树几道板题以后发现这是基本套路啊。不会虚树算我技不如人了。
T2. 偷藏女装
弱化版 [ARC068F] Solitaire。
待补，还没看这个结论怎么推出来的。
T3. 楼梯调度
感觉是很好的题目啊，一定补。
1.12 省选模拟赛 23
56+100+10=166 rk26
今天终于做出来一道自己思考出来的题了。T1 暴力没调出来有点小唐。希望一切都能变好。
T1. 星际逃亡
考虑二分。预处理出 $i\to j$ 合法的时间段 $[l(i,j),r(i,j)]$。
然后把 $r\gets r+S$，如果两个边 $i\to j\to k$ 的时间段有交那么就可以连一条边。然后记录 $d(i,j)$ 表示最早到 $(i,j)$ 的时间，跑最短路即可。复杂度 $O(n^3\log n)$ 大概，spfa 跑的很快。
然后考虑把 $i$ 的所有出边时间段算出来 $[s_1,t_1],[s_2,t_2],\dots$，如果两个边时间有交就合并。这样就缩成一些段。这样我们仅可以记录到达这一段的最早时间，段里的每个边的时间都是这个时间。
然后这样的优势在于，如果每次加入的时间递增，那么每条边只会被更新一次。之前的情况一条边可能会被有交的边会被更新好多次所以是 $O(n^3\log n)$ 的或者复杂度更大，现在是 $O(n^2\log ^2n)$。然后细节很多，赛后调了三个小时拍了无数次才过去。
T2. 博弈问题
显然遇到这种问题考虑 trie 树（其实本质是线段树）。
一开始的想法是树上启发式合并，但是因为无法通过 $y$ 来转移 $x$。
考虑从全局的角度出发，如果一个节点的左子树只有一个节点，右子树有很多，则左边这个节点的最大值一定在右子树中。
考虑线段树合并，每次合并的过程中如果遇到左子树有一个节点，右子树节点就暴力更新左子树的答案。而由于线段树合并均摊 $O(n\log w)$ 的优秀性质，只会最多更新 $O(n\log w)$ 次。所以复杂度是 $O(n\log ^2w)$ 的。
T3. 兔子猜拳
弱化版 [AGC022F] Checkers。
感觉是很好的 dp 题目啊。前几步转化都想到了但就是不知道怎么计数。一定补。