4月日记

26-4-1

SPOJ-MSKYCODE，就是一个容斥，设表示最大公约数的四元组数量。

答案就是。

P10504，简单概率 DP。

P10505，二分答案。

P10506，这个游戏相当于若干处理单堆珠子游戏的之和，游戏取和的 SG 值用异或算，然后一颗珠子拆分后，涉及决策，取接下来所有可能情况的 mex。

P10507，就是阶梯 Nim 游戏。

对于 SG 函数进行了一个学习，完成了蓝书数学专题。

现在水平好一点后理解 SG 函数要好一些了。

26-4-2

上午参与了 CF JMR Round 的 Test。

下午进行了数数。

AtCoder AGC012 D，用并查集维护可交换关系。

AtCoder ARC167 C，比较纯粹的数数题，首先由于是全排列所以原本 a 序列的顺序不重要，所以可以排序。

考虑每条边产生贡献的条件，若从小到大考虑每一个成为边权并产生贡献的条件，发现当其连边范围内有权值比它小的的点时就会产生贡献。

考虑产生贡献个数，发现只会是或次，如果更大就要求在的范围内放下大于个间距大于的点，显然不可能。

因为次贡献方案数的计算比较麻烦，难以确定什么样的方案会在生成树的贪心策略下产生贡献，所以我们先计算无贡献方案数和次贡献方案数，最后通过总方案数减去这两者来得到次贡献方案数。

而次贡献方案数的计算相对简单，只需要钦定有两个点权比小的点在的连边范围内，并且这两个点之间的间距大于，且这两个点之间没有其他点权比小的点，这样就能保证这会产生次贡献，不然不符合生成树的贪心策略。

所以我们可以（相对容易的）计算出固定当前位置，其余总方案数，无贡献方案数，次贡献方案数，然后通过总方案数减去无贡献方案数和次贡献方案数来得到次贡献方案数，最后乘以来得到的贡献，累加到答案中。

具体来说：

定义（当前考虑排序后第个点）：

：表示在考虑。
：表示总方案数。
：表示无贡献方案数。
：表示次贡献方案数。
：表示次贡献方案数。
：点的位置在时的连边范围长度。

然后的内层式子只跟有关，所以可以单独计算，优化掉两层循环，时间复杂度。

26-4-3

模拟赛攀登计划 - 2，得分 130/230 挂分 100 pts，原因是 Presentation Error，草。

警示：若有条件，使用 LemonLime 测大样例，避免因为神秘原因（例如：fc 处理超大单行太慢）导致错误。

还有就是 T3 没有骗到分，遗憾。

26-4-7

AtCoder ABC279 G，简单 DP，设表示长度为时的答案。

有转移方程。

26-4-8

CF2217D,E。

CF2217D，关键是发现不合法连续段跨关键点两两配对消除最优的性质，据此分析做题。

CF2217E 题解。

26-4-9

上午写双语卷子，下午体考耗费 4h，晚上改了昨天晚练。

：（

26-4-10

AT_codefestival_2016_final_f Road of the King。

分为三种点，未到过点，到过但不在 1 节点所在 SCC 的点，已在 1 节点所在 SCC 的点。

我们不在乎第二种点是否形成 SCC，因为最后若要合法，肯定全都在 1 节点所在 SCC。

根据这个设 DP 状态，然后转移也是简单的，就是考虑走到的是三种点中哪一种点转移方程就出来了。

P1450。

显然没有的限制就是简单完全背包。

考虑容斥去掉完全背包算出来的方案数中不合法的部分。

就是枚举有哪几种硬币用超限，超限硬币先用个，算出此时方案数（也是相同的完全背包，就是取的容积不同）然后乘个容斥系数加上即可。

CF Gym103428M 810975。

先考虑如何计算简单情况下的放置方案数，发现就是将 1 用 0 分割成若干个可空部分的方案数。

然后将答案转化成「每一个连续 1 段长度不大于的方案数」减去「每一个连续 1 段长度不大于的方案数」。

然后形似「每一个连续 1 段长度不大于的方案数」是可以容斥算的。

26-4-11

黑暗爆炸 - 4714 旋转排列，难点在于读题，事实上就是询问 $有大小为的置换环的错排个数$ ，简单题。

CF1821F Timber。

考虑在原序列上选出个长度的区间来放树，插板法选出这些区间后，树根有两种放置方式，方案数。

但是发现，有些方案会被重算，就是当一种方案的某棵树往左往右倒都可行是就会重算，而此时它相当于提前占了长度的区间。

答案式子如下：

26-4-13

P5339。

直接做啊，容斥有多少组人在讨论坤坤，然后算一下方案数即可。

设表示有组人在讨论坤坤时的方案数，则：

注意直接暴力是的，所以内层循环需要预处理优化至。

26-4-14

CF2220D。

CF2220D 设三次出现的数的位置分别为，注意到当且仅当查询集合同时包含时，返回结果才会与集合大小奇偶性不同，先用二分/倍增在内找（第一个满足查询返回结果与集合大小奇偶性不同的位置就是），然后再在中找（第一个满足查询返回结果与集合大小奇偶性不同的位置就是），然后再在中找（第一个满足查询返回结果与集合大小奇偶性不同的位置就是）。

26-4-15

CF2220E。

官方题解：

首先，我们以红节点为断点对树进行拆分。考虑所有只包含黑节点的连通分量，以及这些分量的邻接节点。这样我们得到若干棵独立的子树，其中红节点总是叶子节点。下面定义子树上的树形 DP（将树以黑节点为根）：

：在节点被染色时间早于其父节点的情况下，将节点的子树全部染成红色所需的最小期望操作次数。

：在节点被染色时间晚于其父节点的情况下，将节点的子树全部染成红色所需的最小期望操作次数。

边界条件：

若是红色叶子节点：，。

若是黑色叶子节点：，（它只有一个邻居，即父节点，因此只需一次操作）。

每个连通块的答案为。

转移：

将节点的所有子节点按照的值降序排序。

对于：考虑排序后子节点的所有非空前缀。对每个前缀，若子节点在前缀中，则将其子树染色成本记为；若不在前缀中，则记为。则此时节点邻接 $前缀大小$ 个红色节点，染色节点本身的成本为 $孩子个数前缀大小$ ，再加上各子节点子树的染色成本。

对于：与上述类似，但由于其父亲以被染成红色，所以此时允许考虑空前缀。染色节点本身的成本为 $孩子个数前缀大小$ ，再加上各子节点子树的染色成本。

AtCoder AGC058 D。

牛牛数数题。

注意到单纯对不合法子串容斥十分困难，因为不合法子串难以计数，但是不合法子串一定是若干个连续段，考虑对连续段的开头容斥。

发现一个不合法子串开头一定是如下情况之一：

发现若要在一个字母后插入一个不合法子串开头，必然只有两种选择，仅有在开头的不合法子串开头有三种选择。

设表示有个不合法子串开头时的方案数，则：

令。

表示先钦定一个字母到开头，其余字母分到个空隙中的方案数。

表示先钦定开头无字母，全部字母分到个空隙中的方案数。

答案就是。

26-4-16

生大病，寄掉了。

26-4-17

好了一点。

P3160，神秘状压 DP 加容斥，反正就是从小往大放，只能放在八连通没有未被填的 X 的格子上，直接状压维护 X 被填状态，但是可能出现不期望的 X 然后就要容斥干掉，容斥需要枚举具体那些格子为 X，用 DFS 实现。

P6478，设，即恰好局不平局的方案数，为钦定局不平局的方案数，有，然后二项式反演，又发现可以树形 DP 算。

细节略，总之就是注意考虑答案（恰好）与容易求得的东西（钦定）的容斥关系，引出 DP。

26-4-18

P4528，图腾，恐怖。

放张图片以示敬意。

题解。

模拟赛攀登计划 -3，T1 糖，T2 反射容斥板子但不会，T3 T4 没怎么骗到分。

主要遗憾是 T4 因为懒没打部分分，不然就能上 200 了。

26-4-20

改模拟赛。

T3 总结：关键是“完全替代”的思想减少计算量，如果 B 合法条件比 A 严格，而且 B 权值还不如 A，就显然可以抛弃 B。

T4 总结：关键观察是有效区间长度不大于 3，而由于，于是等价，这个还是太关键了，发现之后直接优化到，然后再发现凸性（感觉现在做不到），于是分治加闵可夫斯基和优化做掉，还需要考虑前后缀先空个共种情况不用以方便包含所有方案。

所以 T4 还是太困难了。

26-4-21

把反射容斥模板题做了，感觉对这个东西不是很熟。

今天干的事少因为上午实验操作考试下午拍照。

26-4-22

气笑了，fst 了说是。

早练 T1 是高维莫队板题，可惜我又不会。

T2 是个啥我还不会，fst 对心态有点打击。 /ll

26-4-23

早练 T2 需要先处理出每条边对应两端的两棵子树的直径，这玩意可以用两遍 DFS 求，然后发现断边重连最优解一定是连到两端子树的直径中点，基本上就做完了，码量稍大，因为需要：

给边定向，以将边断开后的两棵子树转化为一个点的子树和其子树外的部分。
第一遍 dfs 求各点子树内直径。
第二遍 dfs 求各点子树外直径。
遍历边，回答第一二问。
找一条合法边，断开，两边子树各 dfs 两遍找直径端点和两对直径端点到各自子树内的每个点的距离以找到直径中点。

所以确实很麻烦。~~鉴定完毕，屎题。~~

26-4-24

早练 T1，傻缺 nth_element，不会 STL 导致的。

早练 T2，简单题，被线段树常数做局了导致的。

早练 T3，不会。

26-4-25

上午糖糖模拟赛，下午凌云计划 - 10，T3 T4 一道随机化一道搜索，气笑了。

26-4-27

改模拟赛。

26-4-28

终于把 26-4-24 的早练 T3 改了，我好菜。 /ll

26-4-29

早练期望得分 100+17+40，实际得分 35+17+40，原因是 T1 少判了个条件挂飞了。

T1 是唐，发现连边是对区间内的奇数或偶数连边，可以 set 维护未到过的点。

T2 是神秘数数，首先是要注意到和的顺序不重要，简单理解，交换某两行不影响主视图，只交换左视图中的两行，即当前顺序下任意方案可以一一对应到交换中两个数后的一种方案，同理。归纳可得和的顺序不与答案无关。

然后是当且仅当中的最大值与中的最大值相等时有合法方案。

然后就是容斥和超绝数数。

放个网上的 Sol，内有详细数数过程。

今天晚练有且仅有我一个人过了，赢。