NOIP+省选真题
BaCO3
·
·
个人记录
可能会对当前节点 $x$ 产生贡献的路线有两种：
第一种是起点 $s$ 位于 $u$ 的子树内，此时当 $dep[s]=dep[x]+w[x]$ 时会产生贡献，所以我们需要维护 $dep[s[i]]
第二种是终点 t 位于 u 的子树内，此时当 w[x]=dis(s,t)-(dep[t]-dep[x])，即 dep[lca]\times 2-dep[s]-1=dep[x]-w[x] 时会产生贡献，所以我们需要维护 dep[lca]\times 2-dep[s]-1
这里的维护都使用 树上差分
不过还有一点就是我们需要避免重复计算，所以我们在维护第一种情况时只用在 son[lca]\rightarrow s 上打标记就行了，同时第二种情况维护的变为了 dep[lca]\times 2-dep[s]
可以用桶计算最终的答案，子树内的贡献 = 出去的的权值 - 进去的权值，统计答案时间复杂度 O(n)
$dp[s]$ 表示已经死了的猪的集合状态为 $s$ 时最少要发射的鸟数。
明显有 $dp[S∣line[i][j]]=min(dp[S]+1)$，$dp[S|(1<<(i-1)]=min(dp[S]+1)
若令 $x$ 为满足 $S\&(1<<(x-1))=0$ 的最小正整数，则由 $S$ 扩展的转移的所有线都要经过 $x$。因为先打 $1,4$，再打 $2,3$，和先打 $2,3$，再打 $1,4$ 是一样的，不然就会有多余的转移。因为经过 $x$ 的线数量是 $n$，所以时间复杂度 $O(Tn2^n)
很显然，最后道路的形态一定是一棵树。设 $f_{i,j}$ 表示打通到树的第 $i$ 层，已经选了的点集合为 $j
下面考虑时间复杂度，我们集合的枚举量显然是全集的子集的子集个数和。乍一看全集有 $2^n$ 个子集，每个子集有 $2^n$ 个子集，那么个数似乎是 $O(4^n)$ 的。但若 $A,B$ 交集为空，一个元素其实只有在 $A$ 中，在 $B$ 中，都不在三种情况，所以总个数应该是 $O(3^n)$ 的，总复杂度 $O(n^2\times 3^n)
观察发现每次变动有影响的点只有当前点，最后一行最后一列的点以及当前这一行的最后一个点。
所以可以用一个支持单点修改的线段树，建立 $n+1$ 棵，前 $n$ 棵代表第 $n$ 行前 $m-1$ 个答案，第 $n+1$ 棵表示最后一列。
每次操作将当前点 $(x,y)$ 记录输出并删除，然后加入第 $n+1$ 的最后一个位置，然后把第 $n+1$ 棵的 $x$ 位置记录加入到第 $x$ 行的最后一个位置，注意如果 $x$ 本身就在最后一列就不用管。
考虑 $q$ 的范围，即最多有 $q$ 个点加入，那么线段树的长度最长为 $\max(n,m)+q$，**动态开点** 即可
$5.$ [P5049 NOIP2018 提高组 旅行 加强版](https://www.luogu.com.cn/problem/P5049)
简单版是枚举要断开哪一条边，加强版可以把这个过程配合 **贪心** 放在 $\text{dfs}$ 上进行
在环上的点可以进行一次放弃子树反悔祖先的操作，只需要用栈记录回溯会经过的点，比较一下判断一下回溯是不是更优就行了
$6.$ [P5665 CSP-S2019 划分](https://www.luogu.com.cn/problem/P5665)
首先是一个 $O(n^3)$ 的 dp：$dp_{i,j}=\min\{dp_{k,j-1}+val(i,j)\}
设 dp_i 表示考虑到第 i 个数的最小值，g_i 表示 dp_i 从哪里转移来更优，则可以优化至 O(n^2)
发现最后一段尽量小，答案会最优，则 g_i 单调递增，用 单调队列优化 复杂度 O(n)
设 $f[i]$ 表示以 $i$ 为根的子树不同多叉堆的情况数，将 $v$ 合并 至 $u$ 时有：$f[u]=f[u]\times f[v]\times \binom{siz[u]+siz[v]-1}{siz_[v]}
[题解](https://wcsb.blog.luogu.org/solution-p7078)
$9.$ [P7114 NOIP2020 字符串匹配](https://www.luogu.com.cn/problem/P7114)
$84$ 分做法：考虑枚举 $AB$ 和 $i$。对于 $F(A)\le F(C)$ 这个限制，可以先预处理每个前缀后缀的出现奇数次的字符数量，对于 $C$ 用树状数组统计有多少个符合条件的 $A$ 即可。时间复杂度 $O(n\log n \log 26)
因为 $ABAB$ 中出现奇数次字符数肯定为 $0$，所以一种是当前后缀出现奇数次字符数，一种是全局出现奇数次字符数。通过 kmp 求出最小循环节后可以用树状数组算出答案。时间复杂度 $O(n\log 26)
前置知识：[拉格朗日插值](https://www.luogu.com.cn/blog/user11773/solution-p4781)，[CF622F The Sum of the k-th Powers](https://www.luogu.com.cn/problem/CF622F)
[题解](https://wcsb.blog.luogu.org/solution-p7116)
$11.$ [P7914 CSP-S 2021 括号序列](https://www.luogu.com.cn/problem/P7914)
设 $dp[i][j]$ 表示区间 $[i,j]$ 合法的方案数，但 $ASB$ 型的串会被 $A+SB$ 和 $AS+B$ 两种情况重复计算
故令 $dp[i][j][0/1]$ 表示区间 $[i,j]$ 合法的方案数，但是 $0$ 代表左括号开头右括号结尾的所有合法括号序列，而 $1$ 则不是。转移很好推，但 $ASB$ 型的需要枚举两个断点，考虑预处理出 $dp[i][j][2]$ 表示区间 $[i,j]$ 为 $SB$ 的方案数
复杂度 $O(n^3)
最后答案为 $n\times \sum a_i^2-(\sum a_i)^2
题目中的操作等价于交换差分数组相邻两项，最终的答案应满足差分数组先减后增
首先把差分重排，从小到大考虑，那么每个差分要么插在首要么插在尾。设 dp[i][j] 表示考虑到第 i 个数，目前还原出的 \sum a_i 为 j 最小的 \sum a_i^2，发现无论是插头上还是尾巴上都是可以快速算出新的 \sum a_i 和 \sum a_i^2
但现在复杂度是 O(n^2\max a_i) 的，因为 a_i 很小，所以其实差分数组中有很多数为 0，不用考虑，那么就可以优化至 O(n \max a_i^2)
考虑第一二个点和第三四个点的地位相同，只枚举一半。发现对于每一个点 $u$，只有与之距离 $\le k$ 中权值前三大的点可能会被计入答案。
预处理出 $mx[i][0/1/2]$ 之后，枚举 $b,c$，直接计算即可
$14.$ [P8867 NOIP2022 建造军营](https://www.luogu.com.cn/problem/P8867)
[题解](https://www.luogu.com.cn/blog/Sham-Devour/solution-p8867)
$15.$ [P8868 NOIP2022 比赛](https://www.luogu.com.cn/problem/P8868)
前置知识：[历史值问题](https://www.luogu.com.cn/blog/command-block/guan-yu-xian-duan-shu-shang-di-yi-suo-jin-jie-cao-zuo)
在这道题中，要维护的最终结果是 $a_i\times b_i$，考虑维护现在操作队列里有多少 $upd$ 操作，现在 $a,b$ 的加法标记，现在 $a,b,a\times b$ 的和，表示每次 upd 操作 $adda,addb,adda\times addb$ 的和，历史版本和，区间长度
$ans_1\leftarrow ans_1+s_1\times upd_2+sa_1\times hb_2+sb_1\times ha_2+hab_2\times len_1
$hab_1\leftarrow hab_1+adda_1\times adda_2\times upd_2+adda_1\times hb_2+adda_2\times hb_1+hab_2
$17.$ [P7516 省选联考 2021 A/B 卷 图函数](https://www.luogu.com.cn/problem/P7516)
$18.$ [P7520 省选联考 2021 A 卷 支配](https://www.luogu.com.cn/problem/P7520)
$19.$ [P7521 省选联考 2021 B 卷 取模](https://www.luogu.com.cn/problem/P7521)
$20.$ [P8292 省选联考 2022 卡牌](https://www.luogu.com.cn/problem/P8292)
$21.$ [P8338 AHOI2022 排列](https://www.luogu.com.cn/problem/P8338)
$22.$ [P8339 AHOI2022 钥匙](https://www.luogu.com.cn/problem/P8339)
$23.$ [P8360 SNOI2022 军队](https://www.luogu.com.cn/problem/P8360)