2023.4

864 (Div. 2) - Codeforces

相似的代码段不要急着复制粘贴

A因为直接复制，但没改好，吃一发罚时

考虑数据的情况

B因为没考虑奇数情况，吃一发罚时

用set来增删边的代码实现不熟悉

赛时考虑了大半，一个写的过程中加的fa[]数组忘记更新了。

赛后改了，然后TLE，看了jls代码，set又短又高效。

性质建树，实现能力

E赛时没看到，赛后看了，一开始欧拉函数log的深度，然后建树没想到，后面的线段树维护是容易想到，但估计不敢写。。已补；

原本自己考虑的是需要lazy标记的线段树，但是因为$logw$次操作后，变成1，可以暴力维护LCA。

F，看别人思路是我没学过/不熟的知识点 已补；

点分治/重心剖分，待学；

Kruskal重构树，其实之前做过用到相关做法的题，但是没有点亮这个知识点（悲）。

Kruskal重构树 - OIerC - 博客园 (cnblogs.com)

RT（重构树）有些性质用到，Max-RT，一条链上的能满足浅层的和深层的点构成的路径中的最大值为浅层的点，Min-RT同理。

这样就把满足条件1和满足条件2的算出来了。

两者都满足的，考虑用dfs序和树状数组算出来，现在一棵重构树上跑出dfn，然后再另一棵重构树上树状数组标记在dfs栈里的点（实际上是标记从根出发的一条链上的点），然后每次问u点在Max-RT中的子树，有多少个是标记了的，也就是有多少个是在Min-RT中和u形成一条链的。子树以u为根节点，u和子树里的点的路径，最大都是u，在Min-RT一条链上，说明上面标记的点都是能作为小的端点的，即满足两个条件。

后面维护的话，因为加进来的index最大，它和所有原本的点的路径的最大的点都是他自己有n-1种（这里的n是加入点之后的总个数），而能作为最小的那端的有depMn[n]个（定义depMn[root] = 0）

AtCoder Beginner Contest 297 - AtCoder

卡在英语

这场A-E的简单题的速度挺满足的，就是B中因为英语单词卡了一分钟左右parity奇偶的意思。

容斥是所有减去不合法的，过程可能是递推

F容斥，自我感觉接近正解，没调出来，已补；

相比atc给出的题解，觉得自己的做法属于是把合法的表示出来相加，但合法的情况可能比较难不重不漏表示。

一个有示意图的清晰FAtCoder Beginner Contest 297 D - F - 知乎 (zhihu.com)，这篇题解是将小块做容斥，然后放在大矩形中，做累加。

把左右、上下变成一个，写法简洁。

做点容斥的题，待做；

看榜和看自己偏好跳题

G博弈论，赛时看到G比F过得多，但是对这两个都没有什么信心，就没跳题了，已补；

取石子[L, R]，SG就是A%(L+R)/L，找规律只不过把递归求SG优化了。

SG函数，打表找规律，待学；

H，好像是生成函数相关的，没学过，待补。

865 (Div. 2) - Codeforces

这场ABC和后面的题通过人数有些断层。

看好题目细节限制

A和B都WA了一发样例，写的时候放飞自我，题目细节的条件忘记考虑了。
大概就是太久没做题的见面礼。

不要急，考虑常见性质

C赛时很久才过，看到相邻两个同时变化，应该就要考虑到奇偶性的，然后判它奇数和偶数的和怎么样。

对特殊结构不太敏感

D，这个操作一其实有些花里胡哨（然后我就寄了），但其实还是容易发现，$x \le n+1$时，慢慢变大，1号点连接的点是一个一个移的，想到可以构造成一条链就简单了。

构造 ++

E，已补。

赛时是没看，看题解前，也想到了建图，判INF的情况，就是不受1的（直接/间接）约束，但构造却没想到很好的实现。

按照到1的最小深度来划分，因为浅层的约束更强（形象理解的话）。

最终的长度最大值就是$dep[1]+2dep[2]+...+mx \space dep[n] = \sum_{i=1}^{mx}i \space dep[i]$，其中mx为深度最大值。

把同一深度的放在一起，dep[mx], dep[mx-1] dep[mx], ... , dep[1] dep[2] ... dep[mx]

这种构造方式，能够让dep[mx]中间都有一个dep[mx-1]，且符合理论长度最大值。

F，已补。

分类讨论，分m=1，m=2，m=3，然后还有奇偶。

m=1, m=3容易分类证明。

m=2，运用到，a ^ b = (a>>1) ^ (b>>1) + (a&1) ^ (b&1)，将异或与2进制位联系起来，形成递推关系，再进行记忆化搜索。

Educational 147 (Rated for Div. 2)

B，找到了没有break退出

C，代码实现上瑕疵。

D，用优先队列模拟，也可以线性贪心，也考虑到了删1，但是只考虑到第一次超出的时候，没有想到前面可能很多1，然后让位置继续后移的情况。

E，待补。

F，待补。

867 (Div. 3)

D，观察构造

E，写得其实差不多了， 就是已经确定它是有解后，写得很烂。

CCCC 2023

L3-2，完美树，DP，f[u][i]，0-子树大小为偶数，1-0比1多1，2-1比0多1

然后，主要就是怎么让他以最小花费到达选x个a和选n-x个b的情况。（确实也比较典）

AtCoder Beginner Contest 299 - AtCoder

E，先默认全黑，把距离p为d的全部涂白，然后check下，距离是否满足，bfs看距离就行。（赛时忘记check）

F，先是处理字符串子序列的序列自动机，然后做dp，根据不同TT的中间分割点来做n次dp。

G，先保证合法，然后再在可取范围内取最小的。具体上，是用每个数字出现的最后位置中的最小值为判定是否最长任选区间，然后在区间中选择，用优先队列，维护数字大小和对应下标，选到未访问过的最小的数字后，把它所对应的最后出现的位置去掉，然后把可选区间中到这个位置的数从优先队列中删去，继续找下一个数。

H，未补。

XDU2023校赛

A，拿了一血，激动了几分钟（

B，数据范围估得不是很好，WA1发

C，前缀和+动态维护/再一遍前缀和，特判下n=2的有解和无解。WA两发

D，跳了，期望一直不太敢做。。待补

E，两个set模拟，luoyue的线段树让我大受震撼（，死于脑子不清晰，维护的东西不对WA了几发

F，自己的$O(n^2)$不会优化，不知道怎么做。待补

G，前面挺多人过了的，感觉也比较典，但是不会。。待补

H，群友说类似NOIP2017宝藏，但是没补过，然后luoyue说可以模拟退火乱搞（。待补，待学

I，网络流板子题，由于对题目是有向边还是无向边有疑惑，加上增加边/边的容量有疑惑WA了10发左右。。现在也就把这种操作更新到板子里了。

AtCoder Beginner Contest 300

操作数为0的枚举

A~C，都是直接模拟就好，B枚举的变化，忘记0了，WA了一发。

D，样例比较善良，知道了这样的数的最大数量，就放心的枚举了，不然可能不敢做。。

E，概率DP/记忆化搜索，和ABC298的E比较类似，这个做个移项也就行了。

F，赛时WA了6个点，看了SSRS的做法，应该是我考虑的先尽可能的整块整块取是有问题的，因为有可能少取一个整块，然后两边多一点这样的情况。虽然想类似的改自己原本的代码，但止步于wa4个点。。可能头脑也有点不清晰了。所以之后可以的话，也可能用取模去整段的移动，避免自己想当然的结论。

G，meet-in-the-middle，之前只接触过图论上的双向广搜，这回算是爆搜的双向了，值得注意的就是让两个的状态数尽可能接近。然后区间的选择注意是否切一半（？）

2023.5

872 (Div. 2)

A，跑完步回来急得很，直接狂wa两发，回文都不会了（痛失上大分）。

B，简单分类讨论，也比较快就过了；

C，也是枚举讨论，还有只有一边的情况，也比较顺利；

D1，k=2是用换根DP来做，已补。

D，题意没完全读懂，k=3理解错了，然后就一直想怎么优化枚举，就寄了。实际上，就像是树上的仓库选址，选重心类似的，贴一个群友的解答。

k为奇数答案=1，k为偶数答案=sum(C(L,k/2)*C(R,k/2))/C(n,k)+1，L和R分别代表每条边将树分割成的两个子树大小

dfs过程中记下size就行。

E，DP+启发式合并，已补

Mark一下由0x3f找到的简洁写法Submission #205112032 - Codeforces

启发式从小的合并到大的，考虑一个点，最多合并logn次，那么总的时间复杂度为nlogn，在完全二叉树时取得。

贴一下元元学长补的做法Submission #205285508 - Codeforces，这里的t数组，是一个lazytag，把从叶子到这里的异或值给记下来了。

元元：
我是这么理解的：
节点u上的map里的异或值再 xor 上 t[u] 是 u 节点可以选择的值，
所以交换map要交换t，t[u] 在子树遍历完也要 xor a[u]

CCPC Finals 2021

A纯纯签到题，但我其实还是犹豫了一下，过了几分钟才说我写A。。

树剖做了J和F

在途中，我缓慢地理清如何合理模拟L，一度感觉自己像个演员，还好一发过了（虽然比较迟。

这种corner case比较多，需要自己设计点的，类工程的不算大型模拟题，对代码能力较弱的我来说，确实该加强下。

后面大概剩一个小时，赛时榜是C和E偏多（后面还有K），树剖看C，我继续看E，然后想出了分四种的构造方式，确定这题很可做，但想得构造还是不好写。。如果是想出根据奇偶的可能就写过了。还有就是开始时我看到E，觉得时大模拟，就没看，但其实是构造，比大模拟好一点（确信）。

赛后略看题解，想法对上的题。

B，确实是换根DP+贪心，但是没有想打什么很好的策略。