最后的记录

但是做的题太少了根本算不上长征。

写这个是因为 NOIP2024 剩百日，这他妈是最后一次了，就让我拿个一等吧，别无所求了。

把之前做过的题都重新总结一遍，怎么说也都能吃透了。

P6880 JOI 2020 Final] オリンピックバス

给一个有向图，经过边有代价 \(C_i\)，可以反转某一条边，代价为 \(D_i\)。问从 \(1\) 到 \(n\) 再从 \(n\) 到 \(1\) 且最多反转一次边的最小代价和。

暴力想法是枚举翻转哪一条边然后重跑最短路。考虑翻转一条边产生的影响，令 \(f(s,t)\) 为原图上 \(s\) 到 \(t\) 的最短距离，翻转一条边之后 \(1\) 到 \(n\) 的最短路为 \(D1\)，\(n\) 到 \(1\) 为 \(D2\)。

容易得出：\(D1=\min(f(1,n),f(1,v)+w+f(u,n)),D2=\min(f(n,1),f(n,v)+w+f(u,1))\)

然后需要知道一个性质：在图 \(G\) 上构造根为 \(x\) 的最短路树 \(T\)，任意删除一条不在 \(T\) 上的边， \(x\) 到其他任意节点的距离不会发生变化。

那么也就是说对于不在最短路树上的边，反转这条边后的 \(1,n\) 到其两端点的最短路是不变的，也就不需要重新求最短路了。而在最短路树内的边最多只有 \(n-1\) 条，那么枚举到这些边时重跑最短路是完全没有问题的。

注意是稠密图考虑使用不加堆优化的dij；有重边所以判断一条边要记录编号；在求起点不是 \(1\) 或 \(n\) 的最短路时可以考虑在反图上以 \(1\) 或 \(n\) 为起点跑。

ABC264Ex Perfect Binary Tree

对于一棵树动态加点，求当前以 \(1\) 为根的满二叉树个数。

计数题考虑 dp。首先满二叉树树高最多 \(\log n\) ，所以只用考虑高度少于 \(\log n\) 的点。

设 \(dp_{x,dep}\) 表示以 \(x\) 为根，最大深度为 \(dep\) 的满二叉树个数。朴素转移即在两个层高为 \(dep-1\) 的满二叉树拼起来，即：\(dp[x][dep]=\sum\limits_{u<v,u,v\in son_x} dp[u][i-1]\times dp[v][i-1]\)

但因为是动态加点，所以这样转移复杂度会爆的。考虑将乘积式子拆开，根据完全平方公式可以化为：\(dp[x][dep]=\sum\limits_{u<v,u,v\in son_x} \frac{1}{2}((\sum\limits_{u\in son_x} dp[u][i-1])^2-(\sum\limits_{v\in son_x} dp[v][i-1])^2)\)

转移过程中维护和与平方和即可 \(O(1)\) 修改变化量，复杂度 \(O(n\log n)\)

CF452F Permutation

给你一个 \(1\) 到 \(n\) 的排列，你需要判断该排列内部是否存在一个 \(3\) 个元素的子序列(可以不连续)，使得这个子序列是等差序列。

正解是线段树维护哈希，但是有奇妙性质：存在 \(3\) 个元素的等差序列时一定有其中点和左右两端的距离不超过 \(12\)。当然这个值肯定是和 \(n\) 相关的，但那篇论文着实让我看不出来。然后能过。

ABC329F Colored Ball

基础的启发式合并。我们对每个盒子开个 set 就行了，合并的时候就启发式合并，小的合并到大的上保证复杂度。

CF1898D Absolute Beauty

考虑将 \((a_i,b_i)\) 看作是一段区间，我们想要在一次操作内增加尽量多的长度，考虑分讨两端线段的相交情况，最后得出结论：选择最大的 \(l_i\) 和最小的 \(r_j\) 进行操作，可以使收益最大。

trick：类似于 \(|a_i-b_i|\) 的式子可以考虑转化为区间来分讨考虑。

P8386 & P10375

给定 \(n\)，\(m\)，求满足以下限制的长度为 \(n\) 的序列数目：

1. 每个元素在 \([1,m]\) 之间；

2. 一次操作定义为删除一个长度至少为 \(2\) 且区间两端相等的区间，该序列需要在若干次操作内被删空。

答案对 \(10^9+7\) 取模。

计数题，考虑dp。对于这种合法序列计数题，可以从在末尾新增一个数的情况入手，放在这个题中，发现对于一个序列 \(S\) 的某一项 \(x\)，若其前缀是合法的，则 \(S+x\) 也是合法的（原因显然）。那么这样可以设出状态：\(dp[i][j][0/1]\) 表示填了前 \(i\) 个数的序列合法/不合法，\(i+1\) 位置填已经出现过的 \(j\) 种数的方案数。

根据状态设定，显然适合用填表法，转移要分讨一下，分当前是否合法，填的数是已经出现的 \(j\) 种还是其他 \(m-j\) 种：

(dp[i+1][j][1]+=dp[i][j][0]*j%mod)%=mod;
(dp[i+1][j][0]+=dp[i][j][0]*(m-j)%mod)%=mod;
(dp[i+1][j][1]+=dp[i][j][1]*j%mod)%=mod;
(dp[i+1][j+1][0]+=dp[i][j][1]*(m-j)%mod)%=mod;

P11013 「ALFR Round 4」C 粉碎

首先考虑记 \(las_i\) 为 \(a_i\) 上一次出现的位置。手玩可以发现最优方案一定是删除一段前缀，最后剩下来的一定都是单牌。那么也可以推断出我们只需要找到最后一个可被删掉的牌，并且这张牌一定是被匹配的一张牌。再思考一下，可以发现对于前 \(i\) 张牌，如果所有 \(las_i\) 前的所有 \(a_i\) 能被删完，那么 \([1,i]\) 就是能被删完的。

那么考虑设 \(dp[i]\) 表示是否能删完 \([1,i-1]\)，如果 \(dp[las[i]]=1\) 那么 \([1,i]\) 就是能删完的。考虑转移，\(las_i\) 能被删掉有两种可能，一是与 \(las_{las_i}\) 匹配，二是被某一个 \(j\in(las_i,i)\) 和 \(las_j\) 匹配删掉了，转移综合起来就是 \(dp_[i]|=dp_{las_j},j\in[las_i,i)\)。

这仍然是 \(O(n^2)\) 的。观察式子，容易想到可以前缀和优化，令 \(sum_i=sum_{i-1}+dp_{las_i}\) 就行，因为转移也是从 \(las_i\) 处转移的，转移部分变成 \(dp_i=[sum_{las_i-1}<sum_{i-1}]\)。

P2446 SDOI2010 大陆争霸

想法比较自然。会想到对于点 \(u\)，其解锁时间等于其前置节点的最大值 \(D\) 和自身的到达时间（不关心解锁）的较大值。那么可以直接跑一遍 dij 然后用拓扑排序的方式更新每个点的解锁时间，很简单。

然后你会发现只对了一个点，原因是你先直接跑 dij 可能会出现最短路上的点仍然未解锁的情况，感性理解容易发现这显然错了，所以要在跑 dij 的同时进行拓扑排序对解锁时间更新。注意更新解锁时间要多开一个数组。

UVA11987

直接无脑并查集是错的。有个trick：考虑对每个集合建一个虚点，每次合并时就把要合并的点连到对应集合的虚点上，虚点始终保持不动，这样子就对了。

[P1525 NOIP2010 提高组] 关押罪犯

带权并查集，判断关系时看两点权值差的奇偶性就行。

[P6061 加油武汉] 疫情调查

网络流会不了一点。

P11022

容易发现当图不联通或是一棵树时无解。考虑加入一条非树边形成一个环，一个简单的想法是将某个点染成白色其它点染成黑色。但是这样是能被hack掉的，考虑一条使得上述方案不合法的边 \((u,v)\)，如果要使其合法可以将包含 \(u,v\) 的一部分点全染成白色，这样就合法了。

[P8817 CSP-S 2022] 假期计划

首先 \(O(n^2)\) 预处理全源最短路方便后续操作，bfs即可。考虑暴力一点的想法，直接枚举要到达的点，但是数据明显只允许暴力枚举两个点的组合。容易发现，只需要枚举 \(B,C\) 点即可，因为 \(A,D\) 点都有一个距离 \(1\) 号点距离 \(\le k\) 的限制，所以在确定下来 \(B,C\) 之后就可以跟着确定 \(A,D\)。但是满足限制的 \(A,D\) 可能很多，解决这个可以只考虑每个点能到达的最优点，但是因为选择的点不能重复，所以要至少保留三个最优的点，可以用set或堆维护。然后枚举一下点的组合就做完了。注意 \(k\) 要加一和开 long long。

[P3537 POI2012] SZA-Cloakroom

数据范围看错了以为背包过不了（ 首先询问离线下来是好想的，离线下来可以按 \(m\) 升序排序，同时对物品也按 \(a\) 升序排序。然后考虑怎么满足后两个限制，如果没有 \(b>m+s\) 的话就可以直接对 \(c\) 背包求能否凑出 \(k\)。有个trick：考虑将设状态为 \(dp[i]\) 表示物品的 \(c\) 之和为 \(i\) 的方案中最大的 \(b\) 最小值，只要这个尽量大的最小值 \(>m+s\) 那么这个方案就是合法的，也就是有解。然后做完了。

[P8868 NOIP2022] 比赛

题意：给两个 \(1\sim n\) 的排列 \(a,b\)，定义一个区间 \([l,r]\) 的贡献为 \(\max\limits_{l\le i,j\le r} a_i\times b_j\)。多次询问，每次给定 \(l,r\) 求 \([l,r]\) 中所有子区间的贡献之和，答案对 \(2^{64}\) 取模，\(1\le n,Q\le 2.5\times 10^5\)。可以离线。

求所有子区间的贡献，一个简单的思路是分治，那么一个朴素的想法就是每次询问都做一遍分治。分治过程中处理跨过中点的贡献时可以考虑双指针来计算贡献，可以砍掉一个线段树的老哥，复杂度 \(O(qn\log n)\)，观察数据可以过 52pts（多个老哥会少12pts，除非数据水），对于NOIP T4已经很不错了。

如果要优化成正解，那么肯定要一遍分治做完才行。自然的想法是将询问离线下来，分治过程中提出包含当前区间的询问，把贡献给加到询问上。