2023.12.03
难绷了，ruarua 地厌学，救命。
Codeforces - 1086F - Forest Fires
(0)
以前的比赛原题，当时场切了。今天找到原题，觉得当时自己太牛逼了，反观现在自己真的是越学越菜。
2023.12.04
VP 了场 Edu，名副其实出题人〇神玩多了。
CF1902F - Trees and XOR Queries Again
(0)
线性基板题。不知道这场在干什么，就没一道好题吗？
2023.12.06
Codeforces - 1622F - Quadratic Set
(-3)
喔趣，好题。综合了不同的思路（主要是证明思路），切掉了这个题。
首先答案大于等于 \(n-3\)。
有构造法：
-
\(4|n\) 时，可以删去 \(\{\frac{n}{2}\}\)。
-
\(4|(n-2)\) 时，可以删去 \(\{2,\frac{n}{2}\}\)。
-
\(2|(n-1)\) 时，可以删去 \(\{2,\frac{n-1}{2}, n\}\)。
上述情况包含了所有非零自然数，故答案大于等于 \(n-3\)。
剩下的就是求具体方案，构造解并非最优解，所以去要另外想办法快速判断平方数。
于是可以 xor-hashing。很牛逼，给每个质因数随机赋值，再质因数分解 xor 去求每个数的 hash 值，再求阶乘，一扫障碍，甚至可以用一些 STL 和其他容器做到 \(O(n)\)，但是我太懒了。
2023.12.08
Codeforces - 1416D - Graph and Queries
(-)
很难崩，被卡常了，乐（大哭）。现在还没过这个题。
具体可以按时间做一遍最大生成树，当且仅当树边被删除时才会引发集合的分裂，然后倒着做一遍启发式合并，再按这种合并方式正着做一遍启发式分裂，用个 map 或者 set 就可以记录了。
时间复杂度 \(O(n\log_2^2n)\)，只能说是联赛能过了。
Codeforces - 1903F - Babysitting
(-3)
Div2 最后一道题整这出？搞笑了。
只能说是线段树优化建图的 2-SAT 板题了。
二分答案，跑点数 \(O(n\log_2)\) 的 Tarjan，就完了，时间复杂度 \(O(n\log_2^2n)\)，但是放最后一题根本来不及做吧。
Luogu - P4690 - [Ynoi2016]镜中的昆虫
(-17)
洛谷某管理员〇神玩多了，空间开成 64MB，卡了半个晚自习，66.8MB->63.67MB。关键有没有可能原题空间 512MB？卡分块你这样卡空间，评论区还有 \(O(n)\) 空间的分块，倒是一大堆 cdq 分治的被卡掉了。
这题是 CF848C 的困难版（做法类似）。会发现区间推平放在这里总的被修改的端点数仅仅是 \(O(n+m)\) 的。于是类似 ODT 地在 set 上维护区间以及颜色。不同于 ODT 在于其时间复杂度是确定的（因为只有区间推平操作）。
然后剩下的就和 CF848C 差不多了，cdq 分治计算贡献即可。
代码里有一个细节是
set < SQ > seq, sq[140005];
int cntdisc, disc[140005];
1.4e5 是为了卡空间设的，实际上应该设 2e5。
其他没啥了。只能说某出题人爱玩〇神。
2023.12.09
Atcoder - ARC059F - Unhappy hacking
(0)
神仙牛逼题，太牛逼了。
设一个长度为 \(m\) 的字符串 \(S\) 可以通过 \(n\) 步操作得到的方案数为 \(\mathrm{F}(S)\)。现在再同时考虑另一个等长的任意 01 字串 \(T\)。
会发现最终决定 \(S\) 形态的操作只有恰好 \(|S|\) 个（“输入 0”或“输入 1”），这 \(|S|\) 个操作顺次连接可以得到 \(S\)，当且仅当改变这 \(|S|\) 个的操作的加入字符才会改变 \(S\) 的最终形态。
所以实际上对于一种可以得到 \(S\) 的方案，将这 \(|S|\) 个操作构成的字串变为 \(T\) 只有唯一的方案，也就是说形成双射，即 \(\forall S,T, |S| = |T|,\{s, t|s \in S, t\in T\}\subseteq \{0,1\} : \mathrm{F}(S)=\mathrm{F}(T)\)。
很牛逼，所以 \(\forall S : \mathrm{F}(S)=\frac{\mathrm{f}(|S|, n)}{2^{|S|}}\)。其中 \(\mathrm{f}(|S|, n)\) 表示 \(n\) 次操作可以得到长度为 \(|S|\) 的字串的方案数。
然后动态规划求解即可。
2023.12.13
[THUPC2023初赛]速战速决
(0)
很有意思的贪心，一眼看过去以为是和喵了个喵类似的题，其实只需要尽量让公共牌堆底部的自己有另一张的牌尽量多就可以了。
2023.12.21
[UR #11] 元旦老人与丛林 & [北京省选集训2019] 图的难题
(0)
这题太牛了，必须记录一下。
首先有一个性质，如果一个图 \(G(V,E)\) 满足可以被划分成两个边集使各自构成的子图相同，那么一个必要条件是 \(P:2|V|-2\ge E\)。
会发现这个图的最坏情况是边集各自为生成树，否则一个边集内一定会出现环。显然其他情况的限制程度都小于这个。
但是可能会出现去掉一颗生成树后剩下一些单点和环。（所以这个只是必要条件）
而充要条件归纳则易知：如果一个图 \(G(V,E)\) 要满足题目给定的要求，那么它的子图和它都要满足 \(P\)。
而将 \(P\) 转化可知：\(P:2|V|-2\ge E \Leftrightarrow E - 2|V| \le - 2\)。所以实际上我们需要求到最大的 \(E'-2|V'|\) 来判断。其实这个很类似最大密度子图的最小割部分，可以通过求闭合子图最大权来解决。考虑选一个点贡献为 \(-2\)，选一条边贡献为 \(1\)，选边必须选两个端点。但是略有不同在于这次倒是不用很在意正负问题，反而是因为这个时候其实网络流会选择一张空图回给你（也就是全部割与 \(s\) 连接的边，返回 \(m\)），也就是什么都不选。这样确实是可以让 \(E'-2|V'|\) 最大，但是实际上不应该出现这种情况。所以每次应该强制选一个点选择。具体来说就是断开它和 \(t\) 的连边并让最终的最大权再减去 \(2\)。
实际上这样的时间是可以被卡掉的。时间复杂度上限为 \(O(Tn^3m)\)。但洛谷上数据范围很水，也就直接过了。
但是实际上应该在每次跑完最大流算法之后退流。这样可以保证复杂度过关。
于是就过了。时间复杂度不会算 qwq。