本来说要一天五场vp，结果没人陪我打/ll
那就换成高强度切题吧。
要的是速度。rush。
打开cf，选rating 2200~2600，通过人数降序。
好像咕了。
86D
21:08开始。
莫队。
13min。
600E
21:22开始。
静态链分治。
20min wa on test 25。¿
想不到吧，要开long long。21min passed。
52C
模板 线段树。
21:44开始，51写完。结果输入格式很阴间啊!还是却死吧。
342E
6:48开始。
/xia这是点分树吗/xia
大概7:10写完，写的是cdq分治，点分治。开调。
7:18交了一发，然后T飞了。发现应该在虚树上点分治。那还是写动态点分治吧（
28写完了动态点分治，然后re了。我完全不知道哪里可以re。
然后自己造了一个，发现是找重心找错了。38过了。一个签到题用我50min/fn
617E
7:39开始。
莫队。
7:46 wa on test 5¿
删除的时候写反了。47过了。
438D
吉老师线段树。48开始。
58写完，然后wa on test 3。
然后发现是区间取模的时候写反了，应该先判直接return的情况。8:10过了。
570D
11开始。
bfs序，压位一下就是查区间xor。
查了半天lower_bound和upper_bound怎么用，47写完了，一发过了。
375D
静态链分治，BiT。50开始。
9:04一发过了。
1400E
前年wa过。再来一遍/fn
把它画成一个柱状图这样的。然后我们考虑什么时候第一种操作才有用。
当且仅当它可以用\(k\)次操作清理超过\(k\)个位置。
考虑我们肯定是在操作2之前用所有的操作1，而操作1必然一直推到全局min。这会把序列分成若干段，每一段分别继续模拟即可。不知道啥复杂度，应该是\(O(n^2)\)吧。
9:11开冲。15写完了然后wa on test 4/yiw
这个小样例强度为0/fn，22过了。
165E
模板 法嘛塔。23开冲。
29写完，直接过了。
1537E2
考虑逐位贪心确定。每一位的结果只可能是第一个字符或者已经被copy到当前位置的字符，问题出在这两个字符相同时应该如何决策，也就是说我们是一直删到这个位置，再copy一遍，还是用之前copy的结果。二分hash判断哪个后面更优就行了。36开冲。
然后发现完全不需要这么麻烦。考虑我们找到重复之后字典序最小的前缀，然后不停重复这个前缀就行了。然后这个 重复之后字典序最小 看起来不是很容易。考虑有没有什么牛逼做法可以快速比较两个前缀重复之后的字典序。
容易想到hash。我们先求出每个前缀最多在原串中匹配多少次，然后就可以\(O(1)\)比较两个前缀。然后就做完了。
1e19以上第一个素数是1e19+51。不过我没有用到（
写了一年，10:45一发过了。串串还是不好写啊/fn
1407D
直接dp。然后考虑如何优化。
单调栈。做完了。46~54，一发wa on test 1，然后是复制的时候有一个没改。然后wa on test 13。¿
注意这里是严格的，而可能有相同的数。所以需要试一试边界。11:12过了。
558E
每个字符开一个线段树。
13开冲。38才过/ll，循环展开写错了。
1333F
这个题结论还是比较牛逼。手玩一下可以感受到类似的性质，但是我并无法抽象出来。
考虑必然存在一个最优策略，满足如果选了一个数，那么选了它的所有因数。如果一个策略中，一个选了的数有因数没有选，那么把它换成这个因数，方案仍然合法。
于是一个数的贡献就是它的最大真因数。我们按照最大真因数从小到大枚举即可，而最大真因数可能可以线筛，不过至少可以\(O(n\log n)\)爆力。
21:01开冲，21:07过了。反复写错/fn
1188B
容易想到上一个三次方程求根公式，但是那需要求解三次剩余。
然后就不会了。
然后这是套路数学题。我们希望把\(a_i,a_j\)独立开，可以乘上一个\(a_i-a_j\)，然后就得到\(a_i^4-a_j^4=k(a_i-a_j)\)，因为所有数互不相同，这是充要的，然后就做完了。
并不想写这道题，因为它实在是缺少营养，让人想起小学奥数。
1438D
全局xor和是不变的。
如果\(n\)是奇数，那么全局xor和就是最后的每个数。先给每个数xor上全局xor和，然后问题是把每个数都搞成0。
容易想到用线性基把每个数凑出来，但是那样复杂度和操作数都爆了。
4号回来了。早上还是很有精神，每天早上都可以切掉一个遗留问题/se
考虑一个牛逼想法，我也不知道是怎么随到的。从左往右操作一遍，把相邻两个都搞成相同的，最后三个是相同的。那么由于相邻两个是相同的，xor一下全消掉了，而全局xor和是0，所以最后三个必然全是0。然后往回操作一遍，居然就全都变成0了。实在是非常的见鬼。
如果\(n\)是偶数，那么全局xor和必须是\(0\)。继续考虑刚才的牛逼想法，我们还是把这些数搞成两两相同的，但是最后会剩下一个位置。由于全局xor和是0，我们知道最后一个位置必然和倒数第二个相同，也就是说最后四个都是相同的。此时我们把所有数xor上最后四个，然后就感觉再扫回去就行了。7:17开冲，20写完。26过了。
1474D
rnm，读错题/fn
34开始重读。
考虑最左边的，它只能和右边的老哥贴贴。然后右边的老哥会减少，变成\(a_2-a_1\)。
然后第三个老哥是\(a_3-a_2+a_1\)，第\(i\)个是\(\sum\limits_{j=1}^i(-1)^{i-j}a_j\)。如果它们全是正的，并且最后一个是\(0\)就行，否则就不行。
考虑这个交换有啥用。我们找到第一个负的位置，交换必然可以在它周围，尝试\(O(1)\)种情况即可。这里又读错题了，只能换相邻的啊/yun
如果没有负的位置，但是最后一个不是\(0\)，就换最后一个和倒数第二个。做完了。然后wa on test 2。看起来这个考虑的并不对，因为交换不一定在周围，可能出现在比较靠前的地方换了一手。
简单想法是直接线段树维护这个。看起来完全没有必要。
复杂想法是，注意到我们换的两个位置的差是确定的，因为最后一个必须是\(0\)。此时我们就知道交换的影响了，然后每个位置就知道一个可能进行的交换的区间，然后如果一个交换的差正确，并且在所有这些区间里，那就是彳亍的，否则不彳亍。感觉需要写一年，8:04开冲。
25写完，然后wa on test 2并且wa的不是很靠前，看不到数据。/fn
换个想法。刚才几乎已经指出了，我们可以直接知道一次操作的效果。然后枚举每次操作，直接看操作之后后面奇数位和偶数位分别的变化即可。这样也是线性并且更好写了。
然后发现这是交换相邻，所以直接前后缀和就行了。这也是线性并且更更好写了。8:49过了。
628D
数位dp。50开冲。
读错题/yun，原来是偶数位必须总是d。
9:14写完，然后wa on test 29/xia，原来是特判a的时候没有判奇数位出现d。16过了。
1110E
经典题。差分之后这个操作相当于交换相邻两项，对差分排序就行了。
17开冲。20过了。
903D
模拟，对第一种情况特判即可。可以用map查三次。
21开冲。
25写完了，少了一个long long，wa了test 7，然后改完了又wa了29。原来这题答案可以爆long long/xia
然后用int128存，直接输出int128就行了。30过了。
1406D
经典题。\(a\)中的下降完全由\(b\)贡献，上升完全由\(c\)贡献，也就是说在\(a\)的差分为正的地方，\(c\)的差分和\(a\)相同，\(b\)的差分为\(0\)；为负的时候反过来。
区间加只会改变两个差分。
剩下的问题完全是我们怎么安排这两个序列的第一项。\(b\)的最大值是\(b_1\)，\(c\)的最大值是\(c_n\)，假设所有正的差分之和是\(d\)，那么有\(c_n=c_1+d\)，同时有\(a_1=b_1+c_1\)。于是我们要最小化\(\max(b_1,c_1+d)\)，显然是取\(b_1=c_1+d=\frac{a_1+d}{2}\)。由于两个序列都需要是整数，所以上取整就好了。39开写，然后wa on test 6。»1总是下取整，而/2是向零取整。58过了。
551C
二分答案，然后每个人分一段。10:00开冲。
09写完了，然后感觉要挂。结果果然挂在了test 54/xia
改了一个更正常的双指针写法，18过了。
1009F
模板 长链剖分
19开冲。32过了。
598C
模板 极角排序。34开冲。
43终于写完了，忘了回去找到原来的下标，实在是太智障了/fn
然后还有一个地方写反了/fn
然后wa on test 118/yiw，改成long double之后48过了。
1092D1
请注意这是Div.3 D/xia，讲道理这难度比较离奇。不过想到另一个做法是模拟，看起来也就可以理解了（
每个位置最多给左右各接一个横着的，所以先给每个位置膜\(2\)，注意如果膜完了是\(0\)要改成\(2\)。然后枚举是\(+1\)还是不，然后模拟即可。
读错题。这是经典问题，但是我没见过，不过我可以想起来joi open 2016 A. JOIRIS，然后它好像不是很一样。
我们可以用类似的方法考虑。先把它变成单增的，然后强行放就行了。然后这个也假了。
结论是，这相当于给每个数膜\(2\)，然后跑一个类似括号匹配的东西，让0和0匹配，1和1匹配。这看起来很可以理解，但是是怎么想到的呢?
1092D2
实际上这题通过数没有那么多，但是看到了就一起写了吧。
不能放竖着的了，我们还是考虑抽象成括号匹配。新加入的必须要比之前的栈顶更低，不然就把之前的栈顶卡死了。然后如果最后没剩下或者剩下的是全局最大值那就可行，否则不可行。2min就写完了。
1336C
20:47开始。
考虑一下这玩意怎么双向加字符。你发现它不行。
考虑这个串前一半是操作1出来的，后一半是操作2出来的，于是我们枚举这个分界的位置，或者说枚举第一个字符在哪。然后就可以\(O(n^3)\)了，也就是dp两边各放到哪了。
考虑换个方向。当需要枚举中间的时候，我们倒过来，从两边往中间做。此时问题变得简单起来。设\(dp(i,j)\)表示左边放了\(i\)个，右边放了\(j\)个，目前看起来合法的方案数，转移枚举哪边继续放就行了。
草，21:10写完了，然后读错题，原来不需要全放进去（
那看起来这个dp也修补不动了。
咕了一会，然后发现一个很要命的事情，也就是并不需要从两边往中间扫。刚才那个\(n^3\)做法中，我们并不需要知道左右各放了多少，只需要知道一共放了这么多，然后知道开始位置就行了。所以设\(dp(i,j)\)表示放了\([i,i+j-1]\)这一段的方案数，然后就做完了。55开始写，58一发过了。
1450C2
这题目十分的经典（
由于太经典就不多说了。22:04开冲，11过了。
713C
给\(a_i\)减去\(i\)，问题变成把它变成非严格单增的。容易发现每个数必然会操作成原来在序列中就存在的数，离散化之后dp即可。
13开冲，22写完了，然后inf开小了wa了一发。
11D
经典问题。状压dp。
24开冲。53好歹调出来了，然后wa on test3，原来压根没有判有没有边。54过了。
587C
/xia
树剖线段树，每个点维护区间内的有序数组，合并的时候开一个堆。复杂度是\(O(n\log n+qa\log^2n)\)。看起来比较难过。
更牛逼的方法是，点分治，然后直接维护十个值。复杂度是\(O(na\log n+qa)\)。7:46开冲。
8:16写完了，然后tle on test 39。原来vector直接传进函数是会飞的，需要传引用。22过了。
1110D
显然如果一堆很多，那么我们可以把它变的少一点。发现一堆不会拼超过六个顺子，所以可以不停拼刻子拼到\(9\)以内，然后存前面两个进行dp即可。25开冲，然后不会写了。9:07写完了，然后居然一发过了。
1470D
看起来是说，找一个独立集，使得这个独立集的邻边可以让图连通。
样例连通都有解，所以猜测连通则必然有解。
考虑了dfs树，发现很困难。然而做法非常离奇。随便找一个点，把它染黑，然后把邻接点染白，然后每次随便找一个白点的还没染色的邻接点，把它染黑，把它的邻接点染白。
正确性看起来很简单。首先它肯定是独立集。然后归纳一下，我们假设所有已经染色的点都是连通的，而每次染的点保持这一假设。最后没有没有染色的点，所以这是对的。
10:13开冲。挂了两发，23过了。
1327D
读错题/xia，原来是有一个环同色就行，我还以为是所有环都同色（
注意到答案必然是某个环长的因数，所以就\(O(\sum l_id(l_i))=O(nd(n))\)地枚举就行了。55过了，但是啥时候开始写的来着?
1520G
Dij。然后一发把-1也连边了，一发没有判-1，然后tle on test 73。¿
哦确实是卡着上界跑的。11:22放弃了，先去拿基数堆写个世界上最快的dij板子。
二叉堆的问题在于它不能维护到每个元素的指针，如果维护了那么常数就很大了。
实际上做法应该是直接bfs。如果不走传送门，就不走了。如果走，求出起点和终点到每个传送门的距离。
然后拿基数堆冲了半上午和半下午，终于4:28过了。非常牛逼。
833B
4:44开始。
看起来直接dp，套一个数颜色的经典trick，然后问题就是区间加全局\(\max\)。复杂度是\(O(nk\log n)\)。
学习一下怎么写zkw线段树。草，怎么这么牛逼啊/xia
可惜zkw线段树做不了这个题。不过没有关系，啥线段树都挺好写的（
4:55开冲，5:11过了。
1353F
看起来像是最短路之类的。注意到走到一个位置时走过的长度是确定的，所以可以给每个格子减去走到它的时候走过的长度，此时问题变成走过的格子的高度都相同。然后我们要找一条路径，使得上面所有高度的和减去\(n+m-1\)倍的最小值最小。
注意到\(n,m\)很小，所以可以枚举这个最小值，然后只能走更大的，直接求一条最短路。复杂度是\(O((nm)^2)\)。
6:07开冲。17过了。
1567E
看起来比较的简单。线段树，只需要维护左右极长递增段的长度。6:19开冲，写一发zkw线段树。
然后开始考虑zkw线段树到底是个啥。7:47一发过了，但是跑的飞慢啊!
1389E
看起来说的是，算有多少\(x+yd\equiv y+xd\pmod{w}\)。除掉\(g=\gcd(d-1,w)\)，我们得到\(x\equiv y\pmod{w^\prime}\)。直接计算即可。8:07开冲，14一发过了。
1328F
考虑枚举最后有\(k\)个的那个数，然后就需要把更大的或者更小的拿下来。注意到一定会先尽可能拿一种下来，不够了再拿另一种，所以模拟就行了。
需要先特判是否需要操作。什么无敌讨论题/fn
9:02过了。
449D
模板 少项式卷积。看起来是说，少项式的法嘛塔点起来有很好的性质。
可能27开始写，31过了。
7D
hash!35开冲，44过了。
1156D
显然可以点分，也就是统计有多少点到分治中心有1，有0，有1也有0。考虑有没有线性。
发现直接在lca处统计就是线性。拉了啊/ll
写不完了，明天再来。去玩wordle了。
8号。粗略估计了一下，一天要做20题以上，才有可能做到第五页，也就是通过数1000人的题。看起来还是有点困难呢。但是不能放弃!
开写。现在是6:46。7:03写完了，然后wa on test 7。原来是调试的时候数组开小了，开大点直接过了。
915D
看起来就是求所有环的边有没有交。这个题在ptzsc16有加强版（
\(O(nm)\)看起来是简单的。注意到如果有超过一条返祖边，一定存在一条树边在所有环的交上，或者所有环没有交。枚举这条边把它断掉，然后重新dfs看有没有返祖边即可。
然后发现这个是满的。实际上完全没有必要使用dfs树。所有环的交一定在一个环上，所以断掉环边即可。7:17开冲。
38写完了，然后就wa on test 4，没判本来就没有环的情况。然后wa on test 12。发现是把loop[i]写成i了，实在是十分的智障啊!50过了。
1503C
感觉见过这个，并且好像庭队长当场秒了。
容易想到邻项交换排序。但是这个不彳亍。
考虑一个牛逼想法，答案的下界是\(\sum c_i\)，为了让我们的答案尽可能接近下界，那个max应该总在前者取到。
容易想到一个极优的策略，也就是我们改成从最小的出发，先一步走到最大的，然后从最大的顺着往下走，这样后一部分必然达到下界，而前一部分可能飞的离谱。不过这给我们一个启发，也就是一旦走到最大的，必然一直顺着往下走。
直接猜测前一部分必然是一直往上走。考虑我们把\(c_i\)提出来变成\(\max(0,a_{i+1}-(a_i+c_i))\)，也就是说\(i\)可以没有代价地往上跳\(c_i\)的距离。然后你发现就容易证明前一部分必然是一直往上走了。
然后问题就变的简单，我们只需要求一条从\(1\)到\(n\)的最短路这样的，建图看起来是\(a_i\rightarrow i\)，\(i\rightarrow c_i+a_i\)，然后\(x\rightarrow x-1,x+1\)，其中往上走是有边权\(1\)的。跑Dij即可。
也许是30左右开冲的吧。9:09终于写完了，然后就wa on test 3了，换了个写法，然后就wa on test 5了。看了一年终于发现数组开小了，27过了。
865D
容易想到dp，但是n足有3e5。
容易想到吉老师线段树优化dp，但是这题真的只有2400啊?
考虑贪心。发现不行。
考虑模拟费用流。容易得到一个简单建图，也就是中间建一排表示时间，然后源连到每天，每天连到汇，表示价格，然后注意汇要连到源，表示这是循环流。然后考虑如何模拟费用流。
考虑从左往右每次加入一天。此时可能有效的负环 :
-
把前面卖了的一天换成这一天
-
买前面的一天，在这一天卖
然后就做完了。瞬间就写完了，但是没过样例。看了半天，发现一天总可以作为被买的前面的一天，而我只在这一天没有被卖的时候才加入了这个决策。11:06终于过了。
282E
读错题（
相当于求一个前缀和一个后缀的最大xor和。枚举后缀，用trie维护所有的前缀，就结束了。
11:16写完了，然后wa on test 33。有地方忘开long long了。然后找了半天找到了，27过了。
1373E
这个数应该不超过1e17?
注意到当\(k\)比较大的时候，这个数应该会比较小。我们可以爆搜一下试试。
然后可以发现对于\(k\geq 3\)，绝大部分的情况在1e5以内有解。超过1e5的我们尝试证明它们确实无解。这里放一段表。
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
122: 5 8
123: 8
124: 5 8
125: 5 8
126:
127: 5 8
128: 5 8
129: 8
130: 5 8
131: 5 8
132: 8
133: 5 8
134: 5 8
135:
136: 5 8
137: 5 8
138: 8
139: 5 8
140: 5 8
141: 8
142: 5 8
143: 5 8
144:
145: 5 8
146: 5 8
147: 8
148: 5 8
149: 5 8
150: 8
搜到了1e7，前面是\(n\)，后面是无解的\(k\)，这里\(k\geq 3\)。
注意到当\(n\bmod{3}\neq 0\)时，\(k=5\)是无解的。\(n\bmod{9}\neq 0\)时，\(k=8\)是无解的。考虑证明。
考虑由于\(k\leq 9\)，所以在\(x,x+1,x+2,...,x+k\)的过程中最多产生一次进位。除掉进位，每次\(+1\)都使各数位和增大\(1\)，而进位设它额外减少了\(9d\)，其中\(d\)是进位时末尾极长连续\(9\)的个数。设一开始的数位和是\(s\)，在加到第\(i\)次进位了，那么总和就是\(s+s+1+s+2+...+s+k-9d=s(k+1)+\frac{k(k+1)}{2}-9d(k-i+1)\)。当\(k=5\)时，\(k+1=6,\frac{k(k+1)}{2}=15\)，然后这个东西膜\(3\)就总是\(0\)，所以当\(n\bmod{3}\neq 0\)时无解。\(8\)是一样的。
然后这个证明好像已经给出做法了。我们枚举在第几次进位，以及进位时末尾极长连续\(9\)的个数，然后就可以算出\(s\)，直接贪心分配即可。注意极长连续\(9\)上面的第一位应该是\(8\)。
看起来很难写。11:53开冲。
12:13写完了但是没冲出来。下午1:53继续。
2:09过了。需要判\(s<0\)的情况。
383D
看起来是求选一个区间，每个数可以是正的或者负的，得到\(0\)的方案数。
如果不是区间，那么显然可以背包。
如果是区间，先考虑一个简单做法，分治一下，然后两边卷起来。恐怖故事是，这个复杂度是\(O(v^2\log n)\)。如果正解是这个，那么不会开1s（
考虑一个爆力做法，枚举左端点，然后扫右端点，这个复杂度是\(O(n^2v)\)。
然后就智障了。实际上这个可以直接dp。设\(dp(i,j)\)表示以\(i\)结尾的区间和是\(j\)的方案数，复杂度是\(O(nv)\)。2:33开冲，43一发过了。
1520F2
王卷王昨天刚给我讲了这个题（
建出线段树。大概是什么\(q(1+\log\frac{n}{q})\)。46直接开冲。3:00过了，回答的时候忘了fflush/hanx
55D
数位dp，只需要存它膜\(\mathrm{lcm}(1,2,3,4,5,6,7,8,9)=2520\)的值。然后再存一下每个数是否出现过，要乘一个\(256\)(\(1,0\)不需要存)。这就很完蛋，不过我们相信它能跑
考虑我们先枚举哪些数出现过，然后常数就很牛逼了，然后我们不能存哪些要出现的数已经出现了，所以最后要做一个子集差分。加上4s，看起来就秒了。3:08开冲。
晚上回来。看了一眼题解有一车常数优化。慢慢写呗（
9:46没卡常，光加了个ofast就过了，跑了3962ms。有点吓人（
13C
最后每个数都可以变成一个之前在序列中存在的数，所以离散化后直接dp即可。要放学了，明天写。
回来了。今天是3月9日，我没有多少时间了。7:01开冲，05写完了，但是cf炸了。
32活了，然后一发过了。
1515E
看起来是说，如果开一台的时候，左边第二台是开着的，那么左边第一台就会打开；右边是一样的。也就是说只会影响周围一点距离。然后如果左右都已经打开，那么这一台就不能再被打开了。最后目标状态是相邻两个手动开了的距离不超过\(2\)。
考虑对手动开的连续段进行dp。对于一个长\(l\)的连续段，它可以从中间任何一个地方开始，往两边开，方案数可以预处理。然后就dp就行了，复杂度是\(O(n^3)\)。7:37开冲。
47写完了，没想到我速度这么吓人。一发过了。
915E
模板 动态开点线段树。连续段均摊太难写了。
49开冲。然后数组开小了，开大了会爆空间，就卡了一波空间。8:02过了。
1628C
容易考虑高消。然后随便玩一玩，你发现这玩意不是满秩的。
考虑如果我们要把这些东西选一些xor起来得到全局xor和，那么就要求每个数周围都选了奇数个，并且这是充要的。
然后这就转化成lights out了。但是高消怎么求任意解啊（
题解给了一个离奇构造，看起来还是非常牛逼。除了这个离奇构造，还有一个离奇结论，也就是第一行的任何状态都确定一个解，所以随便取第一行，并从上往下递推即可。证明还是很绝妙，假设我们有一个解，现在改变了它第一行的一个位置，比如\(n=8\)，我们改变了第三个位置，那么可以给整个解xor上这个东西
1
2
3
4
5
6
7
8
00100000
01010000
10101000
01010100
00101010
00010101
00001010
00000100
其中每个位置周围都有偶数个1，所以得到的仍然是一个解。而题目中指出必然有解，所以就结束了。
8:49开冲。纠结了一会为什么不能不清数组，最后并搞不懂，还是清了。54过了。
1215E
只有20种颜色。考虑状压dp。
设\(dp(S)\)表示放了\(S\)中颜色的最小逆序对数，转移枚举下一个颜色，问题是查询一些颜色到一个颜色的逆序对数。这个是可以拆开的，然后就枚举两种颜色预处理一下就好了。复杂度是\(O(nv+2^vv)\)这样的。8:58开冲，9:24终于调过了样例，然后wa on test 4。¿原来是折半的子集前缀和写错了。然后wa on test 7。看起来是算两种颜色的逆序对的时候没有开long long。然后就在9:26过了。
839D
他给军队定义了一个这么奇怪的计量标准，但是别的军队又不会用相同的标准，这有啥用呢（
这是Div.2 D，所以不太可能是gcd卷积之类的。不过\(v\)只有1e6，也可能是一个\(\log\)的gcd卷积之类的。
考虑dp。设\(dp(i,j)\)表示前\(i\)个数，gcd是\(j\)，所有方案中选的数的个数之和。看起来第二维并不是非常小。
考虑莫反，枚举gcd。然后就结束了。长\(n\)的序列的所有子集大小之和是\(\sum\limits_{i=0}^n\binom{n}{i}i\)，可以预处理组合数做到\(O(n)\)。
39开冲，51一发过了。
1037E
如果是单次询问，这个问题是经典的，我们只需要不停删掉度数\(<k\)的点。
但是现在有加边，考虑倒过来变成删边，然后还是模拟即可。54开冲。10:05过了。
1316E
按照\(a\)从大到小排序，然后状压dp，这样选的观众一定是一个前缀。10:12开冲，23过了。
1059D
计算几何/xia
看起来像是最小圆覆盖，然后还有一条线，需要和这条线相切。
简单做法是二分答案，然后考虑和直线相切的点可行的范围。或者可以三分这个和直线相切的点。
复杂做法是真的最小圆覆盖。我们可以总是要求所选的圆和这条线相切。
geogebra画了一下，一个离奇事情是，两个点和一条直线可以确定两个圆，而我们不知道这两个圆哪个更优。如果我们两边都递归下去，复杂度是不是就飞了啊（
考虑一个牛逼结论，这个圆必然使得那两个点在x轴上的投影分列圆心两侧，否则我们可以把这个圆向两个点都在的那一边移动，于是必然可以不是这两个点确定了这个圆。
现在问题是怎么求解二次方程。直接解即可。具体一点，观察那两个抛物线，设焦点是\((a,b)\)，看起来它是\(x^2-2ax-2by+a^2+b^2=0\)。直接消去\(y\)然后硬解就行了。
在谷blog上发了一篇题解。
1114E
先二分找到最大值，然后随机问一些位置，它们和最大值的差必然是公差的倍数，全都取gcd，有很大概率得到公差，看起来这是因为随机两个数互素的概率是\(\frac{6}{\pi^2}\)。
9:26开冲。今天有场离奇校模拟赛，拿了A就摆了/hanx
9:34过了。大部分时间在给样例输入60次查询的答案（
508D
在我做的过程中，这个题突然跑到上面去了（
这是一个经典问题。我们给每个两个字母建一个点，那么三个字母就对应一条边，这个串就对应一条欧拉路。写完1253E再写这个。
2:07开冲。
草，有向图欧拉路咋写啊?
哦直接搜啊，那没事了（
一直没有搞懂欧拉路和欧拉回路咋写。oi-wiki上讲的也不明不白的。
调了一年，写了一车疲倦的bug。3:23终于过了。
1253E
\(n\leq 80\)/xia
看起来很是不好做。考虑dp，设\(dp(i)\)表示\(i\)和前面的位置都被覆盖了，\(i\)恰好被前面某个塔覆盖了的最小代价。转移可以选择让这个塔继续往后扩展一位，或者让后面一个塔往前一直扩展过来，并转移到这个塔范围内任何一个地方。用BiT维护 前缀对一个数取min(不是区间是因为前面的已经没有用了)，单点查询，复杂度\(O(nm\log m)\)。
9:47开冲。然后假了一会，以为不需要数据结构，然后摸了一会。下午回来了，1:58开冲，wa了两发之后2:06过了。
1473E
这好像是个经典题，甚至于被我胡过。最短路是很局部的，所以我们没法知道最短路上的最小值和最大值。所以需要把它变成一个能做的比较局部的问题。由于这是最短路，一个很好的性质是我们随便减去一个，随便加上一个，一定是减去最大值，加上最小值，得到的最短路最短，所以问题就变成有一条边没有代价，有一条边两倍代价的最短路。分层图即可。3:26开冲，39终于写完了。然后数组开小了挂了一发。
1422D
直接做。给每行每列建一个点，然后可能的操作是走到一行并走到那一行的一个快速移动位置，走到一列并走到那一列的一个快速移动位置，或者直接走到终点。4:29开冲，45一发T了，然后看了半天，是边数组开小了，50过了。
547A
看到是1A就知道来者不善（
爆力找到两个循环节，它们都不会超过\(m\)。然后用excrt合并同余方程。但是我不会写excrt啊?
由于循环节不超过\(m\)，可以枚举一边循环了多少次，看另一边是否满足。
56开冲。然后出了一车锅。这个循环是rho形的，我把它当成环了/fn
也就是说需要两边先都走到环上，然后再跑前面那个东西。wa了一年，5:15过了。
707D
做完下面的446C，并过了一个中午之后来做这个。
显然给每个架子开一个bitset，然后用一个指针数组索引这些bitset。8:05开冲。
草，然后发现1e8的指针数组空间会飞。换成int即可。下午3:51开冲。wa了一发之后，4:13终于过了。nm写反了。
446C
直接线段树冲就行了。容易想到预处理fib数的区间和，但是这个不可合并，所以我们需要打一个矩阵标记，这个正确性基于矩阵乘法对加法的分配律。一个等价的做法是，膜1e9+9存在5的平方根。
我还以为这是那个牛逼差分的出处，对着差分想了一年。
7:41开冲。8:02终于调过了样例，一发过了。
1334E
这一眼看上去不知道有没有营养（
最短路的话，我们希望走到的边权和尽可能小。容易想到两边都走到\(\gcd\)，或者都走到\(\mathrm{lcm}\)，看起来是前者更优(因为乘一个数增加的因数个数比除一个数减少的因数个数更少)，于是就做完了。
呃看起来我们需要给什么\(\frac{u}{\gcd(u,v)}\)这样的东西分解。它只可能包含\(d\)中的素因子，爆力即可。4:30开冲，居然40就冲完了，然后第一发预处理阶乘少了。40过了。
888G
看起来非常的经典。别乳卡，trie，每个点存子树里两个来自不同连通块的点，就结束了。44开冲。
然后这题原来不需要别乳卡，直接在trie上搞搞就行了，甚至有一个牛逼做法是直接排序，然后。不过我写了就写了吧（
调了一年，第二天7:33终于过了。上来先去重之后跑的飞快。重要教训是，trie的insert和query必须写成同样的形式，要么都递归要么都迭代，不然边界会很离奇。
1198D
看起来非常的困难啊!
注意到我们显然每次ban一个正方形。
注意到如果两个正方形挨着，那么把它们合起来显然更优。所以所有的正方形都是不相邻的。
然后可以考虑注意一些更离奇的事情。继续注意到一个更强的结论，如果一个正方形的范围内有多个正方形，并且这多个正方形的边长和不比这个大正方形的边长更小，那么我们可以把多个小的换成一个大的。这似乎可以很大程度上指导我们的爆搜。
然后就不会了。然后正解不是爆搜。
考虑如果我们不选整个，那么长边上必然有空着的，枚举这个空着的一行或者一列，然后就递归下去了，复杂度是\(O(n^5)\)。8:27开冲，38一发过了。
1198E
顺便看一下这个（
发现我们肯定是选若干行列。每个格子要么选所在的行，要么选所在的列，不能都不选。于是每行每列建一个点，每个格子连接它的行列，问题变成二分图最小点覆盖。做即可。
由于通过人数没那么多，所以我们放到后面写。不过为什么这也有2500啊?
1097D
1e15以内最大的因数个数是2.6e4，oeis一下，在第125个高合成数866421317361600处取得。
这形成了一个dag，不过每个点有一个自环。问题是走\(k\)步之后走到每个点的概率。这个是不是大家都会啊!爆力dp即可，复杂度是\(O(kd^2(n))\)。然后它过不了。使用矩阵快速幂之类的，复杂度是\(O(d^3(n)\log k)\)，更过不了。
考虑能不能用个牛逼方法算这个。你发现从\(n\)走到\(d\)的概率，就是枚举每一条\(n\)到\(d\)的路径，走出这条路径的概率看起来就是每个点的度数(包括自环)的倒数乘起来，啊当然一个点出现多次要乘多次。
发现直接从dag定长路径数入手是没有前途的。
正解还是比较的牛逼。注意到一个性质，答案是积性的，所以我们把\(n\)分解成极大素数幂，然后考虑\(n=p^k\)怎么做。诶等等，为什么是积性的?
注意到一次转移是各维上转移的复合，然后就可以理解了。好了考虑素数幂怎么做。发现此时图只有\(O(\log n)\)个点，直接做即可。然后就结束了，总复杂度是\(O(k\log n)\)，因为一共有\(\log n\)个素因数。3:48开冲。4:00写完了，然后wa on test 14。看起来少了一个取模。然后就4:01过了。
1384B1/B2
什么离谱长题面（
这个题看起来确实非常的离奇。我居然不会Div.2 B/ll
先考虑B1。直接dp即可，从当前位置自己转一圈实现 蹲一波 的操作，然后转移到下一位。
然后考虑B2。考虑我们刚才的dp是个啥dp，注意到可能的时间是一个前缀一个后缀，我们把它翻过来变成一个区间，直接这么做就不会影响答案。然后蹲一波蹲到的也是一个区间。考虑两个位置之间可能的转移只有，从当前位置第一个能走的时间转移过去，或者转移到下一个位置第一个能走的时间，这要看哪个更早一些。剩下的都可以蹲到。于是强行维护即可。
今天是3月14日。上午有模拟赛，然后我吃完饭就开始调昨天晚上写的，12:52过了。
1083E
为什么这个1E只有2400，并且我还不会（
先离散化。
考虑我们选的这些一定画出了一个单调的线，考虑对这条线dp，设\(dp(i)\)表示选了第\(i\)个，左边选了若干个更高的的答案，转移枚举左边选的第一个，设为\(j\)，那么新增的面积就是\(y_i(x_i-x_j)\)。
考虑如何优化，注意到从更低的转移过来一定不优，所以这就变成斜率优化了。\(x_j\)是单调的，所以我们可以用单调栈二分维护。复习一下斜率优化推式子，看起来是化成什么\(dp(i)=a_i+\min\limits_{j<i}(y_j-k_ix_j)\)。14:19开冲。
还是李超树好/fn
然后胡乱wa了两发，39 T了。不是很懂。然后发现正解不带\(\log\)，这是因为矩形之间互不包含，所以\(y_i\)也是单调的。然后T on test 6，原来是读入太慢了。换成cin就过了。
451E
看起来像是爆力容斥。
如果没有这个\(f\)，我们可以直接隔板法。但是现在它有，所以我们考虑对这个隔板法进行容斥，也就是我们减去有一个选多了的方案数，加上有两个选多了的方案数，减去有三个选多了的方案数……这样的。注意到我们需要给1e14级别的数求阶乘，但是由于\(n\)很小所以没关系的。2:52开冲，3:02一发过了。
1303E
也就是说我们选两个不交子序列拼成它。
考虑我们枚举中间断开的位置，把前后分别拿出来去dp，设\(dp(i,j,k)\)表示走到第\(i\)个字符，匹配了左边第\(j\)个和右边第\(k\)个是否可行。然后维度交换，设\(dp(i,j)\)表示匹配了左边第\(i\)个和右边第\(j\)个的最短前缀，转移考虑左边还是右边匹配下一个，胡乱预处理一下即可。复杂度\(O(n^3)\)。3:16开冲。26写完了，然后上不去cf了。尝试了codeforces.live，看起来非常的好啊!31一发过了。
1375E
怎么2500啊/xia
首先可以相信如果是排列那么也能做，所以可以强行钦点如果值相同，前面的比后面小。
考虑一个想法，我们先把和第一个相关的逆序对都换了，然后如果有这样的逆序对，那么和最小值构成的逆序对肯定在最后，于是我们最后把最小值换过来，然后递归下去即可。3:47开冲，写了一行发现不对劲。
我们不能递归下去。需要找一种方式，使得递归下去之后逆序对还是逆序对。画一画容易考虑到一个简单构造，也就是我们先和后面比这个小的最大的换，然后和次大的换，这样下去，这可以保证逆序对还是逆序对，并且不是逆序对的也还不是逆序对。做完了。4:23开冲。25写完了，然后一发过了。
825E
最小字典序拓扑序。
我们要首先最小化\(1\)的拓扑序，于是在\(1\)的后继都删掉之后，应该立刻删\(1\)。于是用pq当toposort的队列即可。27开冲，31写完了。然后wa了，去开班会了。
回来发现这是经典问题agc001F。做法是把图反过来跑最大字典序，然后把答案反过来。6:14过了。
590C
如果有两个州，那么可以直接找它们之间的最短路。
如果有三个州，如果答案不是两条最短路，那么必然是从一个点出发到每个州的最短路。从每个州出发多源bfs就可以搞定。6:33开冲。7:02终于调过了，拉了啊!
280C
非常离奇。答案是所有点深度的倒数之和。
考虑我们对每个点计算它被操作的期望次数，全加起来就得到答案。注意到一个点没了，是它到根链上一个点被操作的结果，而这个点是每个点的概率相同，所以有它的深度的倒数的概率是它自己。3min就写完了。
547C
考虑一个简单想法，我们维护这个东西和自己的gcd卷积。然后每个1会和自己多贡献一次，剩下的每一对会贡献两次。
那么如何维护gcd卷积呢?加入删除一个数只会影响它的因数们，爆力维护即可。
最后我们需要求1处的值，需要维护每个位置乘上mu的值。总复杂度\(O(nd(n))\)。今天是3-15，2:13开冲，随机调整了系数正负之后，26一发过了。
1238E
状压dp。设\(dp(S)\)表示已经放了\(S\)中的字符的最小代价，这个代价包括这些字符内部的，和这些字符和还没放的字符之间的代价，也就是说如果一个字符放了，旁边的某个字符还没放，那么这个字符贡献的系数加一个-1；如果一个字符现在放下了，旁边的字符已经放了，那么它的系数加一个1。2:30开冲，41写完了，然后一发过了。运气不错啊!
1556E
哦原来是多次查询两个区间能不能变成一样的啊（
考虑序列\(a-b\)，目标是把它搞成全0，然后每次可以选一个位置+1，后面一个位置-1，后面一个位置+1，后面一个位置-1，这样的。考虑它的前缀和，相当于每次给若干个不交区间+1，并且前缀和的最后一位永远不会受到影响，于是如果前缀和有位置>0或最后一位不是0则无解，否则答案是最小值的绝对值，做完了。3:11开冲，然后没开long long wa了一发，st表板子假了wa了一发。为什么st表min max写反还能跑到81啊?20过了。
1542D
这个题好像很经典。
强行给相同的元素钦点一个顺序。考虑一个元素贡献多少次，你发现它会贡献，当且仅当从加入它开始没有出现过比它小的元素不够弹的情况。dp即可。4:37开冲。55终于调过了样例，弹空堆那里考虑了一年，还把小根堆看成了大根堆。
1535E
我回来了/fn，今天是2022-03-18。
注意拿一个点是会改变这个点的金子数量的。看起来问题是我们要找到第一个还没拿完的祖先。倍增即可。7:12开冲，27写完了，忘了fflush。28过了。
1154G
值域只有1e7/jy
考虑枚举一个gcd，然后我们希望找到最小的包含这个gcd的两个数，直接法嘛塔维护最小值和次小值即可。31开冲。40wa了，写了一万个锅，46过了。
第一页做完了/se
429D
读错题/qd，没看见\(g\)上的平方。
反复想错。注意到这是\((i,pre_i)\)和\((j,pre_j)\)的距离，问题变成平面最近点对，做即可。10:52开冲，59 T了，然后是距离忘了开根了。03过了。
1494D
题意比较奇怪，是你要自己给内部结点标号。
考虑所有对的最小值就是根。如果两个点的lca不是根，那么它们必然在根的同一子树中，我们可以给每个子树钦点一个点，那么所有和它的lca不是根的点就和它在根的同一子树中，这样递归下去就好了，如果只剩一个点了就停下。11:37开冲，我怎么这么摸啊!51过了。
715B
看起来比较的牛逼。
一个简单想法是，把所有0边置为1，不停跑最短路，然后每次把最短路上的一条边调整成对的，也就是沿着这条最短路走得到的会是对的，然后再跑最短路。反复调整之后它确实会是对的，但是这太慢了，不过据说能过。
另一个简单想法是，如果我们把这些边权从0连续变化到1e9，最短路也是连续变化的，所以总有一个时刻最短路是对的。然后这给出一个牛逼做法，因为边权是整数，我们可以每次随便让一条边边权\(+1\)，这样也是连续变化的，总有一个时刻最短路是对的。
一个牛逼想法是，先求出s到t的最短路，然后跑一个dij，跑到0边的时候尝试把它改成正确的。这样看起来就非常正确。与之对应的一个简单想法是，分别从st跑最短路，然后每条边置为\(L-\mathrm{dis}(s,u)-\mathrm{dis}(t,v)\)这样的。这个问题出在我们需要处理完一个之后把所有的最短路都更新一下，而一边跑dij一边做这个方便了我们更新最短路。
实现了第一种做法。2:55开冲。少一句话卡了一万年样例，然后T on test 7。没有判不连通的情况。然后开始胡乱wa，33终于随机调过了。二分一定要写l=mid,r=mid-1或l=mid+1,r=mid这样的，不要写l=mid+1,r=mid-1的，容易出奇怪的边界。
1342E
每个格子都被覆盖，当且仅当每行都有一个或者每列都有一个，否则如果有一行一列都没有，那么那个交叉点就没有覆盖了。
如果\(k=0\)，那么必然每行每列都有一个，此时答案是\(n!\)。否则，要么每行有一个要么每列有一个，并且两种情况的方案数是相同的，只需要计算一个，我们这里计算每行有一个好了。然后问题就是每列有一个贡献，确定了每列选多少之后这就是一个多重集排列，看起来如果一列选了\(c\)个，那么会贡献\(c-1\)对互相攻击的，并给方案数贡献一个\(\frac{1}{c!}\)。最后总方案数要乘\(n!\)。
注意到一共有\(k\)对互相攻击的，从每列都是一个，一共有\(0\)对，每次少一列，这个对数都会增加\(1\)，于是我们知道有\(n-k\)列。考虑用gf来描述，设\([z^n]F=n!,[z^0]F=0\)，那么我们就要算\([z^n]F^{n-k}\)。设\(t=n-k\)。
注意到\(F\)比较的经典，它是\(e^z-1\)，二项式定理直接展就线性了。
1404C
今天是03-21。
进行一个结论的猜，最优策略是找到最后一个可以操作的把它杀了。
然后注意到后面少了啥不会影响前面，但是前面少东西会影响后面。所以我们现在可以\(O(n^2)\)地预处理了。要优化需要更多的结论。
考虑一个东西要想被删，前面需要有足够多的东西被删掉，并且只要前面删的够多，那么这个就可以被删掉。注意到前面的东西越多，前面删掉的东西也越多，于是我们可以求出一个数产生贡献的最小左端点，这可以通过从左往右扫，维护保留每个后缀可以删掉多少来实现，数据结构问题是lower_bound，前缀加，可以用BiT维护。总复杂度\(O(n\log n)\)，4:59开冲。8:07过了，写了一万年。
1404E
发现做了1404的CD了，干脆把E也做了。那个D真的是神题（
一看就是网络流。但是直接做是不可行的。需要考虑一些性质。
注意到可以钦点每个行连续段总是只有一个横着的块，因为横着的刺穿了竖着的不会让答案变大。这启发我们考虑横竖块的交点。在得到了一个交点会让答案增加\(1\)
1552F
看起来很有趣。考虑如果在一个位置被传送了，那么总要付出\(x_i-y_i\)的代价，并且不管怎么走这个代价都不会减少，所以我们只需要算每个门会进行多少次传送。呃实际上这一步转化是没有必要的。
这个看起来像是一个简单问题。注意到走到\(i\)之后前\(i\)个必然都是激活的，所以可以强行算出前\(i\)个都是激活的情况下走到\(i\)，下一次再走到\(i\)需要经过多长时间，然后直接模拟即可。没时间了，明天来写。
今天是03-22，7:00开冲。11交了一发，然后wa on test 10，看起来是取模出问题。确实出问题，13过了。
1175E
考虑这个看起来很容易贪心，我们只需要从要覆盖区间的左端点开始，不停选择左端点在当前位置左边，然后右端点最靠右的区间即可。
然后这个过程看起来很可以预处理每个位置选择的区间，然后倍增掉。一个牛逼做法是，按照右端点从左往右处理，那么每个查询只可能比上一个找的更往右，所以可以从上一个的结尾开始往后找，然后这个可以并查集维护。排序之后是线性的。2:34开冲并查集做法。然后wa了一发，是因为如果这一次查询冲过头了，那么冲过了的部分不能压缩掉。52过了。
1495C
看起来很有趣。
注意到 没有两个格子是八连通的 这个限制看起来非常牛逼。
59开始乱搞，19过了。做法就是每三行填满一行，然后中间尝试连起来。
1000F
3s 5e5显然是莫队数据范围（
考虑每个数的贡献，显然它贡献若干个矩形，然后问题就变成在矩形push_back，单点查随便一个元素。这里的矩形好像没什么可用的性质，所以好像就得每个点开个数据结构维护一下。每个点开一个hash table和一个vector好像就可以了，也就是插入的时候同时扔进vector里面，删除的时候只在hash table里面删，然后查询的时候在vector里面不停查末尾元素是否还存在于hash table中，如果不存在就pop_back。看起来常数很是不小。尝试一下pbds hash table，24开冲。
然后T飞了。考虑如何优化，发现我们只需要存最晚被删除的，然后13一发过了。
1630C
看起来很困难。
胡乱猜了一手，然后就假了。
考虑一个简单的结论，每种颜色只有第一次和最后一次出现是有用的，这个怎么感觉都很对。然后我们可以把它画成一条线段，被至少一条线段覆盖且不是端点的位置都必然会被置1，但是端点之间好像不是很好处理。
进行一个结论的猜。考虑每个线段的连通块，其中最左的端点和最右的端点必然不能被置1，尝试构造一个方案使得剩下的都会被置1。你发现我们失败了，在最简单的两条线段相交就会出问题。
进行一个更牛逼的结论的猜。猜测如果一个连通块左右端点同色，那么只有这两个端点不能被置1，否则还有另外恰好一个端点不能被置1。具体如何构造?发现构造不动。
考虑并不是几乎所有线段的两个端点都可以置为1。比如有三个线段，并且左边那个和右边那个不交的时候，看起来最多只能把两个端点搞成1。
进行一个更更牛逼的结论的猜。我们用尽可能少的区间覆盖一个连通块，那么只有这个覆盖的大小\(+1\)个端点不能被搞成1。构造是显然的，证明不会。结束了。
更简单的做法是强行dp，然后线段树优化。
一个线段覆盖写了我一年（
1371E2
今天已经03-29了。
考虑我们怎么算这个方案数，注意到每个敌人可以在一个位置的后缀\(p\)被干掉，看起来它是\(x+p-1\geq a_i\)，也就是\(p=\max(a_i-x+1,1)\)，这给出\(x\)的最小值是\(a_i-x+1\leq n\)也就是\(x\geq\max\limits_i(a_i-n+1)\)。然后这是一个经典问题，我们按\(a\)从大到小排序，因为填大的对小的的影响是确定的，容易知道答案就是\(\prod\limits_{i=1}^n(n-\max(a_i-x+1,1)+1-i+1)=\prod\limits_{i=1}^n(n+\min(x-a_i,0)-i+1)=\prod\limits_{i=1}^n\min(x-a_i+n-i+1,n-i+1)\)。
注意到\(p\)是素数，所以膜\(p\)为\(0\)当且仅当其中有一项膜\(p\)为\(0\)。如果这一项是个\(x-a_i+n-i+1\)，这会在\(x\leq a_i\)的时候发生，它会ban掉所有\(x-a_i+n-i+1\bmod{p}=0\)，也就是\(x\bmod{p}=a_i-n+i-1\)。如果这一项是个\(n-i+1\)，这会在\(x\geq a_i\)的时候发生，如果\(n-i+1\bmod{p}=0\)，它会ban掉所有\(x\geq a_i\)，否则啥事没有。我们可以求出对于每个\(\bmod{p}\)的值最小的被ban的\(x\)，然后就可以直接从小枚举到大了。写了一年过了。
444C
用平衡树维护连续段均摊。讲道理我不会写这东西啊（
没关系的，可以硬写!
然而实际上不需要。线段树和连续段均摊在这个问题上结合的非常好，我们可以直接在线段树上递归找到连续段的边界，然后每个连续段被拆成了\(\log\)个区间，总复杂度还是一个\(\log\)。我的写法是什么在push_up的时候强行合并连续段，感觉不是很好。
1526D
看起来还是挺骗的吧（
容易猜一个结论，答案中必然所有的A在一起，N在一起，O在一起，T在一起。枚举一个ANOT的排列，然后可以BiT算这个逆序对数，我们可以相信它很快。没开long long挂了一发，然后过了。
你发现它和样例输出不一样!但是没有关系，我们要相信这个题是简单的!
145E
直接线段树。
1220E
给\(s\)连一个自环，每次删一个一度点，然后让它的父亲可以选择 走向它并结束整个过程。删到没有点了之后，所有点的权值之和加上找一个点走到一个被删的子树的最大权值就是答案。
785D
考虑枚举中间那个左括号，然后就是两边点一点。考虑随着这个位置从左往右移动，左边的东西会越来越多，而右边会越来越少。具体地，如果扫过了一个左括号，那么长\(i\)的左括号数量会增加长\(i-1\)的左括号数量。想了想感觉这个没法做，但是实际上也不需要这么做，因为这个东西只和左边的左括号个数有关，如果一共有\(c\)个，那么就有\(\binom{c}{i}\)个长\(i\)的。然后我们问题变成要求一个看起来像\(\sum\limits_{i=1}^{\min(c_0,c_1)}\binom{c_0}{i-1}\binom{c_1}{i}\)这样的东西，看起来像是范德蒙德卷积但是下指标上是两个正的系数，于是对称一个下指标之后真的就是范德蒙德卷积了，答案就是\(\binom{c_0+c_1}{c_1-1}\)这样的。然后就结束了。
1182E
容易想到取\(\ln\)之后就变成线性递推了，看起来是\(\ln f_n=(2n-6)\ln c+\ln f_{n-1}+\ln f_{n-2}+\ln f_{n-3}\)。然后上个bsgs求离散对数就行了。
但是真的需要那么麻烦吗（
注意到答案必然是\(c,f_1,f_2,f_3\)的线性组合，然后直接跑四个线性递推算这四个的次数就行了。复杂度是一个\(\log\)。
为什么我会对矩阵快速幂有点恐惧啊?
1528C
最大团/jy
还是别最大团了，问题是选一个点集，在第一棵树上属于同一条祖先-后代链，而在第二棵树上没有祖先-后代关系。考虑一个爆力，我们先枚举第一棵树上的这条链，然后在第二棵树上问题就是选一个最大独立集，然后这个独立集显然有性质，也就是如果一个点是另一个点的后代，那么选后代一定不劣，也就是说我们会选所有 没有后代在这条链上 的点，或者说所有某种极小元。那么我们只需要在第一棵树上dfs一遍，同时维护第二棵树上所有的极小元即可。每走一步的变化量是\(O(1)\)的。容易想到用树剖维护，但是没有必要，可以直接跑个括号序，然后用set维护当前的极小元。
1156E
考虑卡笛尔树，我们找到全局max，然后考虑跨过这个全局max的区间，也就是把两边卷起来，然后显然在短的一边枚举，在长的一边需要一个值域桶，可以把长的一边的值域桶传下去，短的一边爆力重算，复杂度\(O(n\log n)\)，写起来看起来就是在笛卡尔树上静态链分治。
我以前写卡笛尔树写的是啥用st表查区间max，那个太拉了，从今天开始写真正的卡笛尔树。然而跑的很慢啊!
592D
古老trick。答案是斯坦呐树的边数的两倍减去它的直径，也就是我们在直径一端降落，然后走到另一端。斯坦呐树就不停删非关键叶子就行了。
1396C
注意到对boss造成1点伤害之后，如果再回到这关boss就只剩一张牌一滴血了，所以它就完全没了，我们就拿手枪把它秒了就行了。于是考虑我们以某种方式选择每个boss是被一次还是两次杀死，然后对于两次杀死的我们直接就能知道是激光还是手枪划算，接下来我们的策略必然是从左往右走，走到某个地方回去把所有还剩一滴血的boss干了，然后继续往右走，边上看起来需要特殊处理一下，也就是最后一关如果两次打完，需要额外付出\(2d\)的代价走到左边再走回来。然后对这个前缀和优化dp就行了。为什么这么复杂啊?
哦我智障了一下，注意到我们连续往回走的一段长度最多是\(1\)，也就是说最多往前走一步，往回走一步，再往前走一步，同时把这两关清掉，随便玩一玩可以发现这确实是最优的，于是只需要考虑往前转移一步或者两步。
1656E
看起来挺好玩的。当场被这题秒了，然后还被F骗了/xia
官方题解给的做法是黑白染色，黑点权值为正而白点为负，并且每个点权值是它的度数。实际上这个想法居然是自然的，至少是容易证明的，因为删掉一个点之后剩下的每个部分都是一棵树挂着一条边，而这个东西就让每条边贡献都是\(0\)，只有挂着的那条是\(\pm 1\)。
768D
看起来很有趣啊（
注意到概率不到\(\frac{1}{2}\)，于是根据某个经典结论答案在\(O(n)\)级别。我们可以二分答案，然后考虑如何直接计算这个概率。然后好像不是很行，我们需要递推，于是就递推就行了，复杂度\(O(n^2)\)。但是为什么我开到\(10n\)才过啊?
679B
看起来很有趣啊（
注意到一个方案是合法的，当且仅当对于每个\(i\)，所有边长\(<i\)的块大小之和要比\(i^3\)小，然后就使劲放就行了。
但是你发现这样求出来的\(x\)好像不一定是最大的/yun
考虑样例中\(23\)和\(42\)的区别，你发现就是把一个\(2^3\)换成了\(3^3\)，那么考虑这种交换是不是总是有效，然而这个看起来不是很好说明。
所以我们需要一些新的想法。往刚才的程序输入1e15，你发现选的是
1
2
3
4
5
6
7
8
9
10
11
1 7
2 2
3 1
4 1
6 1
10 1
21 1
59 1
268 1
2547 1
74257 1
，其中左边是值而右边是选的次数；而答案是\(18\)。答案非常小看起来就很有用，但是具体有啥用呢?考虑了dp，然后感觉并不行。
换一个表。我们求出1e7以内所有的非严格前缀max。发现这样的数非常多/yun
然后就不会了。然而做法很简单，考虑一个牛逼结论，我们选择的最大的数要么是\(a=\lfloor\sqrt[3]{m}\rfloor\)，要么是\(a-1\)。考虑如果选了\(t\)，那么\(x\)最多是\((t+1)^3-1\)，于是最多只剩下\((t+1)^3-t^3-1\)还可以用。
如果我们选了\(a\)，那么剩下\(m-a^3\)。
如果我们选了\(a-1\)，那么剩下\(\min(m-(a-1)^3,a^3-(a-1)^3-1)\)。
如果我们选了\(a-2\)，那么剩下\(\min(m-(a-2)^3,(a-1)^3-(a-2)^3-1)\)。
注意到\(m\geq a^3\)，于是对于后两个，\(\min\)总是在后者取得。所以如果选了\(a-2\)，得到的少，剩下的也少，所以选\(<a-1\)的必然不优。而可能选\(a-1\)是因为它和\(a\)的那个\(\min\)在不同的一边取到。于是由于答案不超过\(18\)，直接搜就行了。
另外这场的E比较套路，看起来就是把值域分成log段然后每一段开一个平衡树维护序列上值在这一段的所有连续段。是不是可以用线段树来实现这个啊?
505D
把要求当成边跑一个scc，然后每个scc内部用一个环穿起来，scc之间形成若干个单连通dag，每个dag内部可以按拓扑序用一条链穿起来。所以答案就是所有非平凡scc的大小之和，加上(可以是平凡的)scc的个数，减去单连通dag的数量再\(-1\)。
然后就wa on test8了。然后发现做法有大问题，压根不需要缩scc。一个单连通块如果没有环，那么可以直接用链串起来，否则可以直接上一个环，而不需要每个scc一个环。拉了啊!
675E
原来它说的是，卖了\(i\)的票可以到\(i+1,...,a_i\)，而不是可以从\(i+1\)到\(a_i\)/jy
固定左端点之后，往右的过程大概就是考虑从左端点出发能走到的这些位置，往右延申到最远的，然后走到那里。考虑dp，设\(dp(i)\)表示从\(i\)出发到右边所有点的距离和，转移就刚才那么转移。需要用什么东西支持查询区间max，然后注意到这个可以离线，所以就上个并查集就行了，总复杂度是线性的。感觉这个离线并查集的trick好像不是很普及（
1536E
注意到一个非零格子要严格大于至少一个相邻的格子，同时它和每个相邻格子的差最多是\(1\)，所以它必然是周围的最小值\(+1\)。
注意到这个看起来很眼熟，并且我们早就想拿图来解释这个问题了，你发现这个等价于钦点一些\(0\)，然后剩下的每个格子的数就是这个格子到某个\(0\)的最短路。于是答案就是\(2^{\text{\#个数}}\)。然后注意到必须有\(0\)，所以如果全是#需要给答案\(-1\)。想了一年?实际上早就感觉到会有这样的结论，但是没有试样例而是尝试硬想了（，如果是比赛中还是应该试一试样例，毕竟它还蛮大的，并且不给小样例看起来也是为了骗你。
1498D
注意到这个操作1一取整直接就取没了。
想了一年为什么只需要搞到\(m\)，仔细一看发现\(x>1\)?
依次处理每个操作，设\(f(i,j)\)表示用前\(i\)次操作把\(j\)搞定，所用第\(i\)次操作的最小次数，那么就可以直接转移了。如果你re on test 18，请注意乘的时候可以转移到的状态会爆int。
1187D
这个题这么眼熟/xia
哦看起来我并没有见过这个题。
注意到我们每次只需要排相邻两个，因为用这个可以进行任意长度的排序。
考虑一个简单模拟，我们从前往后找到第一个不对的位置，然后再往后找到第一个这个位置上应该是的数，如果找不到或者这个数并不是这里面最小的，那么就不可能，否则我们就把这个数一步一步换过来就行了。然后就平衡树支持区间min，区间max
考虑如何让它变得简单一点。想了很久没有想法，看一眼题解真的是线段树，这是Div.2 D啊同志/xia
贺一手zkw线段树。看了一眼比hyl的普通线段树更慢/hanx
154C
好像前几天vuq讨论过这个。也许并不是一个?
给每个点的邻接点排序之后hash一下，但是这个好像不能解决相邻的情况。可以每个点的前后缀hash拼起来!但是那真的能写吗/xia
然后就体现了我的拉。考虑使用集合hash而不是序列hash，直接xor hash就行了，枚举每条边统计的时候直接把这条边去掉。
1203F2
先考虑F1，我们应该以何种顺序完成?这是一个经典结论，我们应该先完成所有\(b\)为正的，再完成所有\(b\)为负的，对于\(b\)为正的显然应该按照\(a\)从小到大的顺序，对于负的则需要考虑一下，可以感觉到应该按照\(a+b\)从大到小的顺序，原因是\(a+b\)的含义是做完之后的最小血量，如果做完之后的最小血量至少是这个东西，那么做之前也是合法的。注意如果这个数是负的，这说明\(a\)的限制不够紧，理论上来讲我们需要把它置为\(0\)，但是实践上可能并不需要。
然后F2就是对这个背包就行了。
708C
以重心为根拎起来，那么每个点超过一半的子树都在上方，于是我们找到重心的最大子树，直接把它接到每个点上，对于最大子树内的点则只能接次大子树，容易发现接别的要么不痛不痒要么不如最大的优。
需要特判有两个重心的情况，此时答案是全1。
1295E
考虑最后左边是一个值域前缀，右边是一个值域后缀，那么问题变成找到一个值域前缀和一个序列前缀，使得它俩的对称差的权值和最小。
注意到每个元素贡献一个值域前缀和序列后缀的笛卡尔积，以及一个值域后缀和序列前缀的笛卡尔积。所以扫描线线段树就结束了!然后确实可以直接在序列上解释这个，于是它变得很简单。
543D
直接换根dp。我写法好像不是很清新。
1559D2
显然连通块里面具体是怎么连的没有什么意义。
考虑了一下，感觉可以拟阵交/xia，也就是把所有边都放在那里，把已经给出的多加一遍并收缩起来，然后拟阵交。但是我对拟阵的理论并不熟练，所以分析不出啥东西来，还是放弃这个好了。
考虑一个结论，我们最后必然可以把一张图变成连通的。考虑我们随便找到两个连通块，它们之间的边如果一条都不能加进去，说明这两个连通块在另一张图里包含于同一个连通块。于是如果不存在两个可以加边的连通块，说明另一张图就是连通的了。
于是我们知道不管怎么加边，只要不停地加，加出来的答案就是正确的。现在可以做D1了，那么怎么做D2呢?
考虑boruvka，我们在连通块数少的图上跑boruvka，每次给每个连通块找一条边连到别的连通块。找到这个连通块中的所有点在另一张图并查集中的所有代表元，如果这些代表元不是同一个，那么它可以连到任何一个别的点；如果是同一个的话，则把它挂到另一张图中的这个连通块上，然后把所有连通块都连向某个连通块。复杂度是\(O(n\log n)\)。
然后发现这个boruvka可以省略，考虑两个点之间能连当且仅当两个图上的连通块都不同，我们先给每个点尝试连到\(1\)，然后就不剩下在两个图上连通块都和\(1\)不同的点了，而只在第一张图不同的点和只在第二张图不同的点可以配对，最后会剩下恰好\(\vert m_1-m_2\vert\)个点。
1559E
看1559题解的时候看到了E的壮观式子（
考虑一个爆力dp，就是设\(dp(i,j,k)\)表示前\(i\)个，和为\(j\)，\(\gcd\)为\(k\)的方案数。为了优化，我们需要砍掉一维，考虑把\(\gcd\)反演掉，然后就枚举一个\(d\)，把所有东西都除一个\(d\)，然后跑只剩下前两维的这个dp就行了。然后还需要注意到这个dp是\(O(nm^2)\)啊?发现它可以前缀和优化，所以就结束了。
1616E
枚举一个极长的贴着的前缀，然后枚举下一个位置是什么，可以随便跑跑每个位置后面第一个每种字符，然后BiT维护换过来有多远就行了。复杂度\(O(n\Sigma)\)。
1537F
显然先给每个值减去目标值。
一个简单想法是保留一棵树直接在树上做，但是这个肯定不对。
考虑我们把图黑白染色，如果可以黑白染色的话，我们知道黑点和白点的权值和的差总是不变的，并且由于连通这些值是可以任意流动的，所以可能当且仅当黑点和白点权值和相同。如果不能黑白染色，一条端点同黑或同白的边可以让这个差改变\(2\)，所以可能当且仅当这个差是偶数，实际上它相当于总和是偶数。
调了一年，是二分图染色的时候，返回有奇环的时候把 if(dfs(v)) return 1; 写成了 dfs(v)。真有趣啊/fn
932E
看零眼就知道要用斯特林数把普通幂转成下降幂。
推一推答案就是
\[\sum_{j=0}^k {k\brace j}j!\binom{n}{j}2^{n-j}\]，算即可。
449C
模板 带花树。
考虑这玩意有什么性质。考虑每个数的素因数集合，容易想到把问题转化成每个数选择一个素因数，然后答案是每个素因数被选择次数除以\(2\)下取整的和。
注意到每个奇数会让我们损失\(1\)，所以实际上就是最小化奇数的个数。看了一眼，怎么是\(1,...,n\)啊?
考虑从大到小考虑每个素因数，尽可能把它搞成偶数，如果不能搞成偶数，则把一个具有更小素因数的留下来，如果没有这样的数那就没办法了。然后就结束了。
考虑有没有什么简单做法。发现这个具有更小素因数的数总可以是\(2p\)。
1398E
考虑没有修改怎么做，显然我们会希望在一个闪电之后使用强力的法术，于是把最小的法术放在第一个，如果它是闪电那么接下来接最大的法术，如果它是火那么继续放最小的。
然后发现其实没必要这么麻烦，考虑我们有\(c\)个闪电就希望进行\(c\)次翻倍，而翻倍肯定是希望喂给前\(c\)大的，它不能被全喂上去，考虑一下可以猜测当且仅当前\(c\)大全是闪电，如果不是的话我们可以放一个小的闪电，然后把前\(c\)大里面的闪电全都串起来，假设有\(k\)个好了，然后放一个火，此时剩下\(c-k-1\)个小闪电和\(c-k-1\)个火，所以必然可行。否则我们必须丢弃最小的闪电，但是如果有火我们可以把它换成最大的火。用平衡树维护即可。
但是这个是不是太恶心了?对顶set即可。
622E
经典。我来推一遍。
正整数\(k\)次幂的前缀和是一个\(k\)次多项式的前缀和，根据有限微积分的理论可以知道它是\(k+1\)次多项式，然后考虑在\(0,...,k+1\)处插值确定这个多项式。设\(l=k+1\)，这个多项式在\(i\)处值为\(f_i\)，可以写出这样的式子，式子具体是啥我懒得latex了。反正就做完了。
1100E
看起来是说，把一些边反转使图变成dag，最小化反转的边权值的最大值。
显然二分，然后问题变成判断一些边可以选择反转，能否把图变成dag。如果不能反转的部分出现了一个环，那就完蛋了，否则问题就是有一个dag，要加一些边，判断能否使得它还是一个dag。看起来简简单单，直接按拓扑序加就行了，也就是如果\(u\)比\(v\)删的早，那么连边\(u\rightarrow v\)不会有任何后果。
然后容易考虑我们是不是很需要二分，可以直接从大到小枚举，问题变成加入一条边判断有没有环，但是这个是动态图单连通性，看起来很难做。
484D
一个经典结论是，这个答案关于段数是凸的，但是这个没有用。
容易想到搞两个单调栈，然后用线段树支持查区间max，然后就是一个\(\log\)。但是这个太拉了!
考虑使用agm2022资格赛那个题的做法，min/max不够局部，我们改成随便选两个，而如果选的不是min/max则必然不优。所以就线性了。实际上设\(dp(i,0/1/2)\)而不是\(dp(i,0/1/2/3)\)更舒服一些。
487C
好像听过，但是我忘了（
考虑\(n\)肯定放在最后，而\(1\)肯定放在最前面。
考虑类似于某些奇怪题凑一个必要条件，可以发现\(n\)是偶数的时候，必然是后一半填偶数前一半填奇数，否则由于偶数膜偶数还是偶数，我们就会得到超过一半的偶数，其中必然有重复的，抽象一下就是某个因数被坍缩成\(0\)了。进一步可以知道，\(n\)是\(d\)的倍数时，必然是前\(\frac{d-1}{d}\)填\(d\)的非倍数，后\(\frac{1}{d}\)填\(d\)的倍数。
考虑\(n\)的所有因数，这些因数把\(n\)以内所有数分成若干组，按照上面的结论应该总是大的包含小的，所以想一想可以知道如果\(n\)不是素数幂则无解。
考虑如果\(n\)是素数怎么做。考虑直接证明\(\frac{i+1}{i}\)膜素数互不相同。如果\(\frac{i+1}{i}\equiv\frac{j+1}{j}\)，意味着\(ij+j\equiv ij+i\)，等价于\(i\equiv j\)，然后就结束了。
考虑如果\(n\)是素数幂\(p^k\)怎么做。我们需要在第一段放不包含\(p\)的，在第二段放包含\(p\)而不包含\(p^2\)的……这样下去，注意到每一段都是一个域，性质应该好到可以套用素数的做法。可以使用exgcd来求逆元。
然而不该这么复杂啊?注意到这个坍缩对一个素数的幂也是一起坍缩的，也就是说只有\(p^k\)以下所有数包含\(p\)的个数不到\(k\)个时才有解。只有\(4\)满足这个，所以有解当且仅当\(p\)是素数，\(1\)或\(4\)。
1228E
看起来是简单数数题。考虑交换两行或者交换两列结果不变，也就是说每行是平等的，每列是平等的，所以我们钦点若杠行列进行容斥，假设有\(i\)行\(j\)列不满足要求，那么容斥系数是\((-1)^{i+j}\)而方案数是\(\binom{n}{i}\binom{n}{j}(k-1)^{(i+j)n-ij}k^{n^2-((i+j)n-ij)}\)。做完了。
然后还可以更牛逼一点，我们枚举\(i+j\)，然后这个式子就可以硬合一下，就\(O(n\log n)\)了，具体可以见题解，并且确实是\(\log n\)而非\(\log v\)。
1399E2
考虑如果只有一种费用怎么做。注意到每条边是独立的，它的贡献是边权的减少乘上子树中的点数。然后这个东西看起来是上凸的，各操作之间的合并是闵和，所以我们只要贪心选择贡献最大的即可。总操作次数是\(O(n\log v)\)，所以总复杂度是\(O(n\log v\log n)\)。
如果有两种费用，对于两种费用各跑一遍，然后直接合并即可。
1234F
只有20个字母/jy
考虑答案不超过20。
考虑我们翻一次可以得到什么，发现翻一次之后得到的任何一个区间必然是原来的最多两个区间，所以就跑出所有区间然后找两个使得它们不交并且并最大就行了。简单做法是使用不交并卷积(子集卷积)，复杂做法是枚举一个，法嘛塔找它的补的子集中最大的。复杂度\(O((n+2^\Sigma)\Sigma)\)。
1168C
一个简单结论是，存在一个方案走不超过\(\log\)步，也就是在每一位上走一次(指的是相邻两项的and包含这一位)，因为如果走了两次的话，那么中间那一段可以省掉了。
另一个简单结论是，必然可以走到每一位上第一个和当前这个数有交的数。两个结论放在一起的话，就是存在一个方案走不超过\(\log\)段，每一段的交是相同的，并且每一步都是走到每一位上第一个和当前这个数有交的数。于是我们得到一个\(O(n\log^{\log n}n)\)的做法，实在是太牛逼啦!
然后发现可以直接bitset做到\(O(\frac{n^2\log n}{w})\)了!
考虑这个是经典不可做问题，所以我们需要更多的性质。
出去溜达了一下会了。考虑一个很牛逼的想法，我们搞一个看起来更牛逼的建图，序列每个位置每一位建一个点，然后每个数建一个点，从它包含的位连到它，然后再连回去，表示这些位之间可以走。这启发我们，每个数的作用是在它包含的位之间转移。所以我们可以使用dij，对于每一位求出最早在哪里到达它，在一个点确定了之后开\(\log^2\)个vector，进行\(\log\)次二分得到它的出边，总复杂度\(O(n\log^2 n+q\log^3 n)\)。
如果能做到俩\(\log\)就无敌了啊!注意到不需要vector二分，可以直接\(O(1)\)查，所以就结束了。
然后发现这个可以预处理掉，也就是求出\(f(i,j)\)表示从\(i\)出发最早在哪得到\(j\)这一位，转移只可能来自每一位上第一个和当前这个数有交的数。
1270E
好像听过，并且好像很有趣。
考虑我们进行某种黑白染色。直接黑白染色之后，注意到如果两个点不同色，那么它们的曼哈顿距离\(x+y\)是奇数，于是\(x,y\)一个是奇数另一个是偶数，于是\(x^2+y^2\)必然是奇数。如果两个点同色，那么它们的曼哈顿距离是偶数，于是\(x,y\)都是奇数或偶数，于是\(x^2+y^2\)必然是偶数。真的有这么简单吗（
没有这么简单。注意到如果所有点都是黑色，或者所有点都是白色，我们就完蛋了。不过没有关系，考虑一个简单想法，如果所有点某一维坐标都是偶数，那么我们可以把所有这一维坐标都除一个\(2\)，然后就会出现奇数。但是这个可能并不管用。考虑一个总是管用的做法，我们也许把它平移一格之后，转45度并除一个\(\sqrt{2}\)，也就是变成\(\frac{x+y}{2},\frac{x-y}{2}\)这样的。除\(\log\)次之后必然不能更除了，所以就无敌了。
27D
hnoi2010 平面图判定。我看这个题的时候好像直接把它胡掉了（
考虑如果一条边在环外，那么好像有两种可能，也就是它在环这边或者环那边。但是注意到不管它在哪边，该相交还是相交，所以就没关系了。
考虑如果两条边在同一侧会相交，那么它们不能在同侧，然后这就2-sat了。
然后发现甚至不需要2-sat，因为这个关系是 不能相同，可以直接跑二分图染色。但是我还是写了2-sat。
1070A
5000还是有点恐怖。
考虑了半天某个经典结论，然后死了。还是来点爆力做法，数位dp可以计算\(n\)以内是否存在一个这样的数，于是我们猜测一个位数，然后往下逐位确定即可。
然后这个看起来是经典套路。我们可以反过来，给每个膜\(d\)的值和各位和建一个点，从0开始dij，每次扩展一位，然后这里不需要dij，而是可以bfs。这样就不需要分析位数了。
那么位数到底是多少呢?注意到每次必然可以扩展到一个新的状态，或者无解，于是位数最多是\(O(ds)\)级别，总复杂度\(O(ds\Sigma)\)。
然后就出现了问题，我们没法每次往最高位扩展一位，因为如果扩展一个\(0\)，膜\(d\)的值和各数位之和是不会改变的，但是这个\(0\)并不是没有用。这导致我们需要枚举加了多少零来转移，复杂度变成\(O(d^2s^2)\)。
所以考虑往最低位塞一位，这样就避免了前导零。为什么这俩一个不对一个直接就对了呢?我感觉了一下，是因为往高位扩展会扩展出前导零，而往低位塞不会，而这个状态会在有前导零的时候挂掉。
908D
不知道pgf能不能做啊/yun
考虑可以把所有有前导b的序列都扔掉而对答案没有影响，因为存在前导b的情况相当于给每个没有前导b的序列的出现概率乘上了\(1+p_b+p_b^2+...\)这个东西，其中\(p_b\)是选b的概率。
考虑如果有超过\(k\)个a，那么接下来加一个b就直接结束了，感觉一下应该可以直接算出这个状态的贡献。所以我们就把状态数限制在\(O(k^2)\)了，可以直接dp，也就是设\(dp(i,j)\)表示放了\(i\)个a，目前有\(j\)个子序列是ab的概率。
考虑那个贡献怎么算。我们要求继续放直到得到一个\(b\)，期望会得到多少个\(a\)，也就是放出下一个\(b\)的期望次数\(-1\)，看起来这就是几何分布，答案是\(\frac{1}{p_b}-1\)。然后就结束了。
然后发现这个dp不是很好，考虑设\(dp(i,j)\)表示放了\(i\)个a，目前有\(j\)个子序列是ab的情况下的答案，然后就好写多了。注意由于一开始扔掉了所有前导b，我们的答案是\(dp(1,0)\)。
1477C
这是一个经典题。考虑找到相距最远的两个点\(p,q\)，那么画一画容易证明任何一个点\(v\)都可以连\(v\rightarrow p\rightarrow q\)，所以我们递归下去然后串起来就好了。
如何找到相距最远的两个点?我们可以先求出所有两点的距离，然后直接给它们排序。复杂度\(O(n^2\log n)\)，看起来很可过。
考虑能不能不用旋转卡壳做到严格\(n^2\)。题解说的非常好，我们可以从当前点出发找到最远点作为下一个点。
另一个牛逼做法是，考虑一个三角形最多只有一个钝角，所以如果发现三个点构成钝角，那么交换两个就可以消去这个钝角，但是可能在下一位产生新的钝角，于是只需要进行\(n\)轮即可。这个看起来就像冒泡排序，官方题解给了一个插入排序，看起来就是第\(i\)轮把第\(i\)个往前换。
626F
看起来是说，把\(n\)个数划分成若干个组，组之间是无序的，求各组极差之和\(\leq k\)的方案数。
考虑从小到大排序之后扫值域，加入一个人的时候，它可以选择当一组的最大值，或者当一个新的组的最小值，或者只是插进去。设\(dp(i,j,k)\)表示考虑前\(i\)个人，有\(j\)组已经确定了最小值而没有确定最大值，当前已经完全确定的组的极差之和是\(k\)的方案数，复杂度\(O(n^2\sum a_i)\)。考虑如何把\(\sum a_i\)变成\(k\)，可以用跟 摩天大楼 类似的费用提前计算，我们每走一步给总和加上\(j(a_{i+1}-a_i)\)这样的。
不要忘了有一个转移是自己和自己一组。
1461E
显然的策略是，能加就加。现在我们会模拟了。
考虑如何快速模拟这个过程。它是一个对\(k\)的变换，当\(k+y\leq r\)的时候变成\(k+y-x\)，否则变成\(k-x\)。考虑了一些想法，感觉不是很行。
注意到\(x\)只有1e6。
一个显然的事情是，如果\(y<x\)，那么除了第一天需要特判以外，每天都会加水。然后就简简单单了。
对于\(y>x\)的情况，想了很久都没有结果。然后实际上做法非常简单，我们倒过来做，改变策略为直到不能不加才加，并且每次跳到接下来第一次需要加水的位置来模拟，此时必然有\(l\leq k<l+x\)。那么看起来很快就会出现循环，于是模拟\(x\)轮，如果没出问题那就永远不会出问题了。
1540B
考虑枚举一对逆序对，计算它出现了多少次。如果起点在大的那个那边，那么必然是先经过大的；如果在小的那个那边，则必然先经过小的。如果在中间的话，这个概率和它到两个点的距离相关，具体一点就是到左右的距离是\(x,y\)的话，先走到左边的概率\(f(x,y)\)满足\(f(x,y)=\frac{f(x-1,y)+f(x,y-1)}{2}\)，从每个点出发dfs一遍求出距离，然后胡乱算就好了。讲道理不是很好写。
1051F
今天刚看了ckw在sdsc19讲的这个题（
不停地剥度数\(=1\)的点，然后剩下的点中度数\(>2\)的不超过\(2(m-n)\)个，而所有点度数\(=2\)的连通图是一个环，于是这张图是不超过\(20\)个环和环之间的一些边。如果两个点在同一个环上那么随便做，否则把每个环上度数\(>2\)的点连一圈，然后加上环之间的边跑一个floyd，查询的时候每个点往环上两个方向走遇到的第一个度数\(>2\)的点就是可能的中转点，在四种情况中取个min即可。复杂度\(O(n+(m-n)^3+q)\)。
现在问题是怎么找到这些环。发现不好办。不过没有关系，我们不需要找到所有环，只需要找到所有段。把剥完一度点之后剩下的度数\(>2\)的点扔了然后从一度点开始搜连通块就行了
注意有可能整张图是一个环。除此之外不可能有环。所以我们可以认为\(1\)的度数总是\(>2\)，感觉这个还是非常牛逼啊!
注意剥去的点是若干树，需要在这些树上使用四毛子lca做到\(O(1)\)查询。
然而我写的是好写做法，也就是找一棵生成树，然后从每条非树边出发dij。
653D
二分答案之后网络流。需要注意因为答案乘\(x\)，需要一直二分到1e-11(大概?)，然后算容量的时候需要跟x取min，不然会爆int，当然如果你网络流板子全是long long那就没事了。
246E
字符串/tuu
长剖，每个位置开一个set或者uset，然后启发式合并。我懒得写uset的hash函数了，所以还是set吧。
1476E
没看见 每个文本串都包含\(k\)个字符/jy
只有一个文本串可以匹配多个模式串的时候才会出问题。一个文本串最多可以匹配\(2^k\)个模式串，也就是选择每个位置是否变成通配符，那么这个限制就是其中某一个的编号比剩下的都要小，连一下边toposort即可。
555C
发现横的内部和竖的内部不会相互影响。
注意到，每个操作把当前这个分成了两部分，一边是一个三角形，而另一边是一个梯形，不过这个梯形方的那一块就再也不会受影响了。把所有操作按位置排序之后按时间建立小根卡笛尔树，在卡笛尔树上走即可。
616E
\(n\bmod{i}=n-i\lfloor\frac{n}{i}\rfloor\)。然后整除分块即可。
1562D2
看起来好像大家认为不是很牛逼，但是我不会。
考虑删一个数的贡献，它的贡献没了，它后面所有数的贡献都会取反。
考虑由于前缀和是连续的，我们考虑\(s_{l,i-1}-s_{i+1,r}\)这个东西，随着\(i\)从左往右移动它每一步要么不变要么增加或减少\(2\)，而\(i=l\)的时候它是\(s_{l+1,r}\)，最后它是\(-s_{l,r-1}\)。当区间长度\(r-l+1\)是奇数，这两个都是偶数，并且\(s_{l+1,r}\)和\(s_{l,r-1}\)相差不超过\(2\)，于是移动过程中必然经过\(0\)，我们选择这个位置，只需要一次操作。如果区间长度是偶数，那么要么不需要操作，要么随便删掉一个之后变成区间长度是奇数的情况。
那么怎么找到需要操作的位置呢?限制是这个位置之前到左端点的和是区间总和的一半下取整，这个位置之后到右端点的和也是总和的一半下取整，然后这个位置贡献是\(1\)；或者下取整变成上取整，这个位置贡献是\(-1\)。注意到如果和是正的，我们找到第一个满足这个位置之前到左端点的和是总和一半上取整的位置，这个位置必然是\(1\)；如果和是负的，我们改成总和一半下取整，这个位置必然是\(-1\)。所以就每个前缀和开个vector，在上面lower_bound第一个在区间中的位置就结束了。
请注意除法是向零取整，而右移1是向下(负无穷)取整。
1385F
发现有点就删必然不劣。然后模拟就行了。
为什么有2200啊?可能因为是Div.3 F得给点面子吧（
需要特判\(k=1\)的情况，因为最后会剩下两个点，这两个点都以为自己是叶子，但是实际上删了一个之后另一个不再是叶子。除了这种情况之外，一个点只要是叶子了，就会一直是叶子。
510E
感觉上素数在这里并没有什么好用的性质。
两个数加起来是素数，我们就连一条边，问题变成找一个非平凡哈密顿回路分解。听起来不是很npc吧?
容易想到网络流，但是怎么流是一个问题。考虑我们有什么方法可以流出一些环，发现流一个排列可以流一些环。于是直接拆成出入点跑二分图匹配即可，如果最大匹配不是\(n\)则无解。但是这样可能出现二元环。一个想法是给边中间塞两个虚点限制流量，但是这样又会自己流向自己。看起来我们失败了。
考虑素数是不是其实有什么好用的性质。注意到\(a_i\geq 2\)，所以得到的肯定是奇素数，那么也就是说只有奇数和偶数之间有边，于是这是一个二分图。考虑这有啥用，发现每个点要匹配左右两个点，于是直接匹配就好了。
八先生指出，一般图的非平凡哈密顿回路分解可以直接费用流。
1401E
这个题看起来非常经典，是joi final 2014 E. 裁剪线。
但是这个看起来要弱一些，因为这个线段比较特殊。
考虑欧拉公式，\(v-e+f=1\)，也就是\(f=1+e-v\)。考虑一个交点的影响，发现它会使得\(e\)增加\(2\)而\(v\)增加\(1\)，于是\(f\)增加\(1\)。一条线段如果同时顶到了两边，则\(e\)增加\(3\)而\(v\)增加\(2\)，于是\(f\)增加\(1\)；否则\(e\)增加\(2\)而\(v\)增加\(2\)，于是\(f\)不变。所以答案就是