4月

· · 个人记录

前半个月主要是模拟赛

4.13~4.26 做题记录

怎么做的都是水题啊，太水的就不写了（

AT3860 [AGC020F] Arcs on a Circle

在我任务计划里躺了一年的题

因为这个线段的坐标是实数，所以不好办，不过考虑到两个线段坐标小数部分相等的概率为零，我们又只关心它们小数部分的相对大小关系，那不妨 n! 枚举它们小数部分的相对大小，然后坐标就可以离散化成 nc 个，然后就 dp 一下算个方案数好了。

题解还有神奇拉格朗日插值 orz

稍微复习了一下 SAM。

CF802I Fake News (hard)

模板题

SP8093 JZPGYZ - Sevenk Love Oimaster

我直接 parent 树上 set 启发式合并，感觉是个很蠢的做法

P6640 [BJOI2020] 封印

直接把 s 在 t 的 SAM 上跑，对每个 i 求出最左面的 l_i 使 s[l_i\dots i] 在 t 中存在公共子串。区间询问就随便二维数点。

然后做了几个 CF *2400~2500 标签带 dp 的题（打 \sqrt{} 的是没看题解做的）

CF1661E Narrow Components \sqrt{}

CF1658E Gojou and Matrix Game \sqrt{}

CF1637F Towers

题解给了两个做法，只说其中一个

选 h 最大的点为根 rt，然后发现只需要它的两个子树里有 h_{rt}，其他点 x 的子树的话，就只需要存在一个叶子不小于 h_x 即可，所以 dfs 回溯到 x 我们看一下其子树中填的最大的值，如果小于 h_x，就把它改为 h_x。

CF1630D Flipping Range

设 $g=\gcd \{b_i\}$，我们就是可以翻转长度为 $g$ 的区间，设一个 $01$ 序列 $s_i$ 表示位置 $i$ 是否被翻转，然后按模 $g$ 分类，$f_x$ 表示所有模 $g$ 等于 $x$ 位置的 $s$ 的异或和。 然后 key observation 来了，一个状态可以达到的充要条件是所有 $f$ 都相等。必要性显然，充分性想一想也能证。之后随便 dp 即可，大概就是 $dp_{i,0/1}$ 表示到第 $i$ 个数，模 $g$ 和 $i$ 同余这些位置的 $s$ 的异或和为 $0/1$ 的最大权值。 **CF1628D Game on Sum** $\sqrt{}

方程写出来，然后经典的 [AGC043B] 123 Triangle 方式算一下贡献，发现就是一个杨辉三角。

CF1625E Cats on the Upgrade

不知道该不该打对号，因为瞄了一眼题解，不过只看到一个单词 subtree，然后立刻会了

括号序列建成树，然后随便做。

CF1620G Subsequences Galore \sqrt{}

忘了题是啥了

CF1609E William The Oblivious \sqrt{}

好像是转移写成矩阵，然后线段树维护

CF1598F RBS \sqrt{}

状压

CF1585G Poachers

用 vector 存子树中所有深度的 SG 值，然后启发式合并（好像也有点像长剖？），算 mex 就用链表，如果 x 只有一个儿子，算完儿子不清空链表，直接继承上来，否则算完儿子把链表清空，找到最浅的一个儿子的深度 d，再把 x 所有儿子深度到 d 这一段的 SG 值异或起来插到链表里算 mex，因为只遍历最浅的儿子，所以复杂度是对的。

必须吐槽的是，把 vector 赋给另一个 vector 的复杂度是 O(n) 的？？？太不健全了

CF1585F Non-equal Neighbours

容斥啊容斥啊怎么不会容斥

按连续相等的段数容斥，dp 即可，转移可以单调栈，于是 O(n)。

CF1582F2 Korney Korneevich and XOR

然后就是 vp 省选，发现啥也不会，严重打击信心。

day1 T1 写了两个小时，因为调不明白 vector 的指针/cy

T2 T3 反复横跳，最后都不会

day2 看到题发现总共会 72 分，过了一个多小时，发现还是只会 72 分。

然后感觉很自闭，发誓一定要把 T1 想出来，想了半天写完发现假了（我竟然认为一个数如果存在大于 \sqrt{n} 的质因子就没有小于 \sqrt{n} 的质因子了，乐），然后更加自闭，弃了。

第二天早上到学校又想了一会发现会了，然后就写，结果因为没判 43^2 挂了，等最后调完过了民间数据已经花了差不多三个小时，这要是在考场上肯定直接寄了。

现在剩的四道题还一道没补，先咕着

做了两道拉格朗日插值入门题，

P4593 [TJOI2018]教科书般的亵渎

P3270 [JLOI2016]成绩比较

说是拉格朗日插值，其实只是求了个自然数幂和......

第二个题主要是容斥然后推式子

P3700 [CQOI2017]小 Q 的表格

把题里那个条件变形成 \dfrac{f(a,b)}{a\times b}=\dfrac{f(a,a+b)}{a\times (a+b)} 这是个更相减损的形式，修改只会改变 \gcd(x,y)=\gcd(a,b) 的位置 (x,y)，我们考虑维护每个 f(i,i)。

然后询问就是求这个东西

\sum\limits_{d=1}^k f(d,d)\sum\limits_{i=1}^{k/d}\sum\limits_{j=1}^{k/d}[i\perp j]

别就知道莫反啊（流汗黄豆），我们有

\sum\limits_{i=1}^{n}i[i\perp n]=\dfrac{n\varphi(n)}{2} ,n\ge2

所以上边式子后面那一坨就是 \sum_{i=1}^ki^2\times \varphi(i)，线性筛 \varphi 即可。

考虑维护 f(d,d)，因为修改有 O(m) 次，而询问有 O(m\sqrt{n}) 次，搞一个 O(\sqrt{n}) 修改 O(1) 查询前缀和的东西平衡复杂度就好了。

CF 瞎做

CF1626F A Random Code Problem

CF1620F Bipartite Array

CF311E Biologist

网络流

P6054 [RC-02] 开门大吉

P4043 [AHOI2014/JSOI2014]支线剧情

CF1667

场切两题，C 题申必构造直接把我送走，F 也是构造

C

D

E

回文树（PAM）

P4762 [CERC2014]Virus synthesis

CF932G Palindrome Partition

神仙题

P4364 [九省联考 2018] IIIDX

省选紫题瞎做

P4363 [九省联考 2018] 一双木棋 chess \sqrt{}

P4460 [CQOI2018]解锁屏幕 \sqrt{}

P4436 [HNOI/AHOI2018]游戏

P4437 [HNOI/AHOI2018]排列

P4454 [CQOI2018]破解D-H协议 \sqrt{}

P4455 [CQOI2018]社交网络 \sqrt{}

P4456 [CQOI2018]交错序列

P4461 [CQOI2018]九连环 \sqrt{}

P4491 [HAOI2018]染色

P4492 [HAOI2018]苹果树

P4495 [HAOI2018]奇怪的背包 \sqrt{}

P4501 [ZJOI2018]胖

P4516 [JSOI2018] 潜入行动 \sqrt{}

P4559 [JSOI2018]列队

P4561 [JXOI2018]排序问题 \sqrt{}

P4563 [JXOI2018]守卫

P4589 [TJOI2018]智力竞赛 \sqrt{}

P4590 [TJOI2018]游园会 \sqrt{}

P4591 [TJOI2018]碱基序列 \sqrt{}

P4606 [SDOI2018]战略游戏 \sqrt{}

P4592 [TJOI2018]异或 \sqrt{}

P6109 [Ynoi2009] rprmq1

上个月模拟赛做的

P2048 [NOI2010] 超级钢琴

P4148 简单题

AT4353 [ARC101D] Robots and Exits

4.23 模拟赛

T2

T3