做题

P4159 [SCOI2009] 迷路

矩阵快速幂优化递推。

首先最暴力的想法，设 $ f_{i,j} $ 在 $ j $ 时刻，到达点 $ i $ 的种类数。

枚举时间和 $ i $，然后 $ f_{i,j} = \sum\limits_{k=1}^n {f_{k,j-w[i][k]}} $。

时间很大，所以肯定行不通。

这样显然是不能用矩阵来优化的。

考虑拆点，每个点拆成九个点，对于一条边 $ u,v,w $，从 $ f_{u,0} $ 向 $ f_{v,w} $ 连一条边权为 1 的边，然后对于每个点，从 $ f_{u,i} $ 向 $ f_{u,i-1} $ 连一条边。

然后矩阵快速幂即可。

CF446C DZY Loves Fibonacci Numbers

分块板子题，区间加斐波那契数列。

其实和区间加等差数列差不多，每个块维护块头的 $ f_1 $ 和 $ f_2 $。

查询的时候直接下传递推即可。

P3265 [JLOI2015] 装备购买

实数线性基板子题。

AT_abc223_h [ABC223H] Xor Query

区间线性基。

有一个显然的做法是线段树上维护线性基，但是是 $ O(n\log^3n) $ 的，我不想卡常，所以没写。

考虑一点智慧的做法，给线性基做一个前缀和。

第 $ i $ 个线性基表示前 $ i $ 个数组成的线性基，并且记录一下这个位置是原序列上的哪个数。

由于我们到时候要删掉 $ [1,l-1] $ 的数，所以每一次插入的时候贪心的保留后面的。

查询的时候把记录的 $ idx \le l-1 $ 的数删掉就好了。

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

并非题单内的题，但是突然看到了就写一下吧。

预处理第 $ i $ 个块的众数，前 $ i $ 个块中 \(j\) 出现了多少次。

查询的时候答案只可能是散块内出现的数和整块众数，这个量级是 $ \sqrt{n} $ 的。

暴力枚举个数统计答案即可。

woc 怎么要卡空间？

对每个数开个 vector，然后预处理出 $ [l,r] $ 块的答案。

拿着答案的个数对着左边散块扫，扫到合法的就把答案向后推。

P4458 [BJOI2018] 链上二次求和

简单推式子题 并非简单。

简单推下式子，记 $ S_n = \sum\limits_{i=1}^n a_i ,SS_n = \sum\limits_{i=1}^n S_i ,SSS_n = \sum\limits_{i=1}^n SS_i $：

$ \sum\limits_{len=l}^r \sum\limits_{i=len}^n \sum\limits_{j=i-len+1}^i a_j$

$ = \sum\limits_{len=l}^r \sum\limits_{i=len}^n S_i - S_{i-len} $

$ = \sum\limits_{len=l}^r (\sum\limits_{i=len}^n S_i - \sum\limits_{i=0}^{n-len} S_i) $

$ = \sum\limits_{len=l}^r {SS_n - SS_{len-1} - SS_{n-len}} $

$ = \sum\limits_{len=l}^r {SS_n} - \sum\limits_{len=l-1}^{r-1} SS_{len} - \sum\limits_{len=n-r}^{n-l} SS_{len} $

$ = (r-l+1) {SS_n} - SSS_{r-1} + SSS_{l-2} - SSS_{n-l} + SSS_{n-r-1} $

然后维护 $ SS,SSS $ 就可以了。

再记 $ sum_0(n) = \sum\limits_{i=1}^n a_i,sum_1(n) = \sum\limits_{i=1}^n a_i \times i , sum_2(n) = \sum\limits_{i=1}^n a_i \times i^2 $。

那么 $ SS_n = \sum\limits_{i=1}^n \sum\limits_{j=1}^i a_j = \sum\limits_{j=1}^n a_j \times (n-j+1) = (n+1) \times sum_0(n) - sum_1(n) $。

$ SSS_n = \sum\limits_{i=1}^n \sum\limits_{j=1}^i \sum\limits_{k=1}^j a_k = \sum\limits_{i=1}^n \sum\limits_{j=1}^i a_j \times (i+1-j) $

$ = \sum\limits_{j=1}^n a_j \sum\limits_{i=j}^n (i+1-j) $

$ = \sum\limits_{j=1}^n a_j \sum\limits_{i=1}^{n-j+1} i $

$ = \sum\limits_{j=1}^n a_j \times \dfrac{(n-j+1)(n-j+2)}{2} $

$ = \dfrac{1}{2} \sum\limits_{i=1}^n a_i \times (i^2 - (2n+3)i + (n+1)(n+2)) $

$ = \dfrac{1}{2} (sum_2(n) - (2n+3) sum_1(n) + sum_0(n) (n+1)(n+2)) $

那么在线段树上维护 $ sum_0,sum_1,sum_2 $ 就可以了。

P4389 付公主的背包

前面忘了，中间忘了，后面忘了，反正这题要多项式。

把每个体积的生成函数的封闭形式乘起来，得到 $ res = \prod\limits_{i=1}^n \dfrac{1}{1 - x^{a_i}} $。

后面好像两边 $ \ln $ 再 $ \exp $ 之后就可以了，但是我不会，数学功底不够，后面再来补。

CF995F Cowmpany Cowmpensation

非常牛的一道 DP 题。

首先有一个很显然的树形 DP。

设 $ f_{u,i} $ 为节点 $ u $ 及儿子权值不超过 $ i $ 的方案数。

转移方程为 $ f_{u,i} = \prod\limits_{v \in son_u} f_{v,i} $ 。

这样转移就是 $ O(nd) $ 了，无法接受。

记子树大小为 $ siz_u $，那么 $ f(u,x) $ 为关于 $ x $ 的 $ siz_u $ 次函数。

证明我不会。

反正 $ d $ 的上界缩减到了 $ n $，时间复杂度 $ O(n^2) $。

最后用拉格朗日插值算一下答案就好了。

AT_yahoo_procon2019_qual_e Odd Subrectangles

01 矩阵权值和为奇数等价于异或和为 1。

假定现在已经选出了要选哪些行，那么我们挑一列异或和为 1 的出来，若其它列的异或和为 0，那就选这一列，若其它列的异或和为 1，就不选这一列。这样一共有 $ 2^{m-1} $ 种方案。

但要是选一些行出来它们的异或和为 0 就无法挑选出一列异或和为 1 的了，所以要减去异或和为 0 的子集的方案数。

考虑线性基，把每行看成一个数插入线性基，记线性记的大小为 $ siz $，那么根据线性基的性质异或和为 0 的方案数就有 $ 2^{n-siz} $ 种。

那么总方案数即为 $ 2^{m-1} \times (2^n - 2^{n-siz}) $。

P11364 [NOIP2024] 树上查询

也不是题单内的题，但是惦记这题好久了，也该写一下了。

非常套路的，计算出每一个 $ LCA $ 的支配对，每个支配对形如 $ [L,R,LCA] $。

然后可以转化为三维数点，记询问区间为 $ [l,r,k] $，分为三种相交的情况讨论：左边相交，右边相交，包含。

\[R-l+1 \ge k \]

\[r-L+1 \ge k \]

\[R-L+1 \ge k \]

然后对答案的贡献就是 $ dep_{LCA} $。

时间复杂度 $ O(n \log^2 n) $ 的。

P8082 [COCI 2011/2012 #4] KEKS

很显然的思路肯定是要把大的放在前面。

那我们肯定是考虑第 \(i\) 位，把它前面的小于它的都删掉。

用单调栈维护即可。

P8898 [USACO22DEC] Feeding the Cows B

从左往右扫，考虑记录一个 $ maxh $ 和一个 $ maxg $，表示这两种牛能够到达的最远的地方。

然后每一次超出最大的范围了，就从 $ i+m $ 向前找第一个可以放的位置。

从后先前找是因为要最大的满足后面的。

P6243 [USACO06OPEN] The Milk Queue G

若 1 奶牛比 2 奶牛更优：

\(a_1 + \max(b_1,a_2) + b_2 < a_2 + \max(b_2,a_1) + b_1\)

由 \(\max(a,b) = a + b - \min(a,b)\),则有

\(a_1 + b_1 + a_2 + b_2 - \min(b_1,a_2) < a_1 + a_2 + b_1 + b_2 - \min(b_2,a_1)\)

即 \(\min(b_1,a_2) > \min(b_2,a_1)\)

然后依据这个来排序即可，但是不可以直接丢到 $ sort $ 的那个比较函数里面，因为不满足传递性。

所以考虑另外一种排序方法，当 $ A<B $ 时，按 $ A $ 从小到大排序，当 $ A \ge B $ 按 $ B $ 从大到小排序。

P2255 [USACO14JAN] Recording the Moolympics S

以前感觉做过一个这种题，反正看上去就是用右端点排序，然后能填就填。

P2945 [USACO09MAR] Sand Castle S

直觉告诉我两个分别排一遍，然后直接算是对的。

CF3D Least Cost Bracket Sequence

神仙！！！

首先你先考虑把所有的 '?' 全部变成 ')'

从前往后匹配，当你的右括号多了的时候就想办法从前面找一个 '?' 来变成左括号

贪心的找，考虑把前面每一个问号的位置用优先队列存下来，然后里面的排序就用左括号的贡献减去右括号的贡献

这个就是右括号变成左括号的差值，你要让这个东西最小，贪心的选即可。

CF525D Arthur and Walls

不知道为什么是蓝题？？？

你直接扫一遍，碰到一个 $ * $ 就判断一下不是不被三个 $ . $ 夹着的，如果是就直接把它变成 $ . $，然后更新一下周围的就可以了。

P8896 「DPOI-1」道路规划

你发现这个东西的是一个竞赛图的 DAG

那么竞赛图的 DAG 的出度序列肯定是一个排列，证明如下

首先肯定有且仅有一个入度为 0 的点，否则就不满足是竞赛图或 DAG 了。

然后删掉之后还有且仅有一个入度为 0 的点，这个和上面同理。

所以这个东西的拓扑出度就是一个排列。

那么原问题就转化为重排一个排列，问是否可以满足对于每个 $ a_i $ 都有 $ l_i \le a_i \le r_i $。

这个贪心就可以了。

CF1208G Polygons

这个东西也非常牛！！！

首先假设你现在已经选了 $ n $ 边形，那么你就可以选它所有的因数了，因为选它的因数这个是不会增加新的贡献的。

所以说一个数的贡献其实就是 $ \varphi(n) $。

你要求最小的点数那你直接按 $ \varphi $ 排一遍然后取前 $ m $ 个即可。

P4765 [CERC2014] The Imp

首先你要知道这个东西的转移顺序是什么。

设现在有两个物品 $ v_1,c_1 $ 和 $ v_2,c_2 $。

令 $ v_1 < v_2 $。

若按升序排列，$ ans=min(v_1 - c_1,v_2 - c_1 - c_2) $。

若按降序排列，$ ans=min(v_2 - c_2,v_1 - c_1 - c_2) $。

后面那个显然是不优的，所以应该按升序来转移。

然后 DP 即可，DP 的时候要注意顺着不好转移所以要倒着 DP。

CF1685C Bring Balance

自己想到了可以把左括号看成 $ 1 $，把右括号看成 $ -1 $，然后前缀和一遍，剩下就不知道怎么做了。

看题解发现答案的上界肯定是 $ 2 $，且方案为找到前缀和数组最大的那个位置，然后反转前面，反转后面。

证明可以自己画个图理解一下。

然后考虑什么时候答案可能是 $ 1 $。

你找到前缀和数组的第一个小于 $ 0 $ 的位置 $ fst $ 和最后一个小于 $ 0 $ 的位置 $ lst $。

再在 $ [1,fst] $ 中找最大值 $ max1 $ 和位置，在 $ [lst,n] $ 中找最大值 $ max2 $ 和位置。

如果可以翻转一次就成功，那么肯定是反转 $ [maxpos1+1,maxpos2] $ 这段区间。

和上面一样，反转过后区间加上了最大值，如果还小于 $ 0 $ 那就只能翻转两次了。

CF1085E Vasya and Templates

你直接用 $ dfs $ 暴力找，然后看一下有没有贴着上界或下界，然后直接像数位 DP 那样爆搜即可。

不知道为什么要放在贪心题单里面。

P1650 田忌赛马

又没秒掉，为什么数据范围还误导啊？？？我还以为是 $ n^2 $ 级别的算法？？？

你先给两个序列都排一遍序，然后直接双指针扫一遍，开头和结尾可以就直接统计，然后不能的话就用田忌的最小值去抵消齐王的最大值。

P4823 [TJOI2013] 拯救小矮人

好像做了好几道这种贪心确定 DP 转移顺序的了，还是不会。

你考虑高的小矮人如果早点出去了就不能对后面的造成贡献了，影响较大，矮的小矮人出去了影响较小，所以贪心地按照 $ A_i + B_i $ 进行从小到大的排序。

然后你考虑做一个背包，设 $ f_{i,j} $ 表示前 $ i $ 个小矮人走掉了 $ j $ 个，留下的小矮人垫高的最高值。

然后直接做就好了，背包可以优化一维。

UVA1747 Swap Space

调整法 + 分类讨论，当 $ a \le b $ 和 $ a > b $ 时的贪心策略是不同的。

当 $ a \le b $ 时：

现在有两对点 $ (a_1,b_1) $ 和 $ (a_2,b_2) $，令 $ a_1<a_2 $。

若 $ b_1 > a_2 $ 此时按 $ a $ 升序排序造成的贡献为 $ a_1 $，按 $ a $ 降序排序的贡献为 $ a_2 $，升序更优。

若 $ b_1 < a_2 $ 此时按 $ a $ 升序排序造成的贡献为 $ a_1 + a_2 - b_1 $，按 $ a $ 降序排序的贡献为 $ a_2 $，由于 $ a_1 < b_1 $，所以升序更优。

所以当 $ a \le b $ 时按 $ a $ 升序排序更优。

当 $ a > b $ 时：

现在有两对点 $ (a_1,b_1) $ 和 $ (a_2,b_2) $，令 $ b_1>b_2 $。

若 $ b_1 > a_2 $ 此时按 $ b $ 降序排序造成的贡献为 $ a_1 $，按 $ b $ 升序排序的贡献为 $ a_2 + b_2 - a_1 $，降序更优。

若 $ b_1 < a_2 $ 此时按 $ b $ 降序排序造成的贡献为 $ a_1+a_2-b_1 $，按 $ b $ 升序排序的贡献为 $ a_2 + a_1 - b_2 $，降序更优。

所以当 $ a > b $ 时按 $ b $ 降序排序更优。

AT_agc023_f [AGC023F] 01 on Tree

妙妙题。

你考虑每一次合并一个点和它的父亲所在的连通块。

令 $ cnt_{u,0/1} $ 表示 $ u $ 所在的连通块 $ 0/1 $ 的个数。那么这个时候造成的贡献即为 $ cnt_{fa_u,1} * cnt_{u,0} $。

现在的问题是以什么顺序来合并连通块才能使得这个总贡献最小。

其实刚刚算贡献的方式已经告诉我们该怎么做了。

如果要合并两个连通块 $ a,b $，那么当 $ cnt_{a,1} * cnt_{b,0} < cnt_{a,0} * cnt_{b,1} $ 的时候把 $ a $ 排在 $ b $ 前面是更优的。

所以直接这样排序即可。

P7287 「EZEC-5」魔法

比较智慧，反正我没秒。

你注意到乘法至多乘 $ \log $ 次就肯定可以了，所以这个的次数可以暴力枚举。

然后发现加法如果加 $ i $ 次就可以满足，那么加 $ i+1 $ 次也肯定可以满足，所以这个东西是有单调性的。

于是你直接二分加法的次数，暴力枚举乘法的次数就是对的，总时间复杂度是 $ \log^2 $ 级别的。

AT_agc029_c [AGC029C] Lexicographic constraints

本来以为贪心可以直接做的，调了两个小时发现不能直接贪心找答案。

注意到这个东西的答案有单调性，所以考虑二分答案。

考虑怎么检查答案。

如果下一位的字符串长度比这一位大，那么直接往后面填 1 就是对的。

否则就用线段树二分从后往前找第一个可以填的位置，给那个值加 1，然后把后面全部推平成 1。

如果找不到就说明这个答案是不合法的。

AT_arc103_d [ARC103F] Distance Sums

题解说的每一个条件都考虑到了，为什么没有做出来呢？

首先观察样例并结合直觉易得：\(D\) 最小的是整棵树的重心，\(D\) 最大的那几个是叶子节点。

然后根据典型的换根可以推导出换根之后 \(D\) 数组的变化公式，并且可以找到叶子节点的父亲。

剩下的就不会了

我好像有点蠢，找到叶子节点的父亲之后直接把叶子删掉，然后继续找下一个 \(D\) 最大的点即可。

如果找到的下一个点的 D 和推导出来的 D 不匹配那就说明不合法。

但这样找出来的树也不一定对，你最后还要 \(dfs\) 一遍判断构建出来的树是否合法。

然后就做完了。

CF1311E Construct the Binary Tree

还是没有自己想出来。

首先一个很显然的东西：最小深度和是完全二叉树，最大深度和是一条链。

然后可以根据这个东西去判无解。

然后考虑从一棵完全二叉树上去向链调整。

先扒出来一条最长的链，然后从大到小去枚举，试着将这个点尽量地向下放，每一次向下放 $ dep $ 都会多 1，所以如果合法的话那一定是可以构造出来的。

AT_hitachi2020_c ThREE

又是只想了一半的题。

你考虑一下要是不满足条件长什么样？

设 $ i,j $ 两点之间的距离为 \(3\)，那么若它们不合法，一定是 $ a_i \equiv 1 \ (\bmod \ 3) $ 且 $ a_j \equiv 1 \ (\bmod \ 3)$ 或者 $ a_i \equiv 2 \ (\bmod \ 3) $ 且 $ a_j \equiv 2 \ (\bmod \ 3)$ 这两者中的其中一种。

你先给树黑白染色，然后分类讨论一下，令 $ x $ 为黑点数量，$ y $ 为白点数量，$ up $ 为 $ \lfloor \dfrac{n}{3} \rfloor $。

若 $ x > up $ 且 $ y > up $，这个时候黑点白点恰好可以覆盖所有的 $ a_i \equiv 1 \ (\bmod \ 3) $ 和 $ a_i \equiv 2 \ (\bmod \ 3) $ 的情况，所以给黑点变成 $ a_i \equiv 1 \ (\bmod \ 3) $，给白点变成 $ a_i \equiv 2 \ (\bmod \ 3) $，剩下的自由安排即可。

若 $ x \le up $ 这个时候覆盖不完，所以给原来黑点的地方放 $ a_i \equiv 0 \ (\bmod \ 3) $，白点和原来一样。

若 $ y \le up $，和上面一样，就不再赘述了。

P9755 [CSP-S 2023] 种树

有点妙。

首先你注意到这个答案是有单调性的，所以直接考虑二分答案。

二分出来一个答案 $ x $，考虑如何检查它是否可行。

写一个函数 $ calc(i,l,r) $ 表示第 $ i $ 个数在 $ [l,r] $ 天生长了多少米。

先预处理一个数组 $ up_i $ 表示第 $ i $ 个数在第 $ up_i $ 天的时候生长的长度小于等于 \(1\) 了。

那么 $ calc $ 函数分讨一下就写成这样：

inline int calc(int i,int l,int r) {if (r<up[i]) return ((l+r)*(r-l+1)*c[i]/2+b[i]*(r-l+1));if (l>up[i]) return (r-l+1);return (r-up[i])+((l+up[i])*(up[i]-l+1)*c[i]/2+b[i]*(up[i]-l+1));
}

然后现在要检查 $ x $ 是否可行。

对于每一个数 \(i\)，检查若 $ calc(i,1,x) < a_i $，那么 $ x $ 就一定不行。

否则你再二分出对于一个数 $ i $，它最晚在多少天种下，到第 $ x $ 天能够满足要求。

然后你按这个东西排一下，从小到大处理每一个数。

要种下第 $ i $ 棵树，你首先要把它的祖先全部种下来。

模拟这个过程即可，若过程中有一个不满足要求了，这个 $ x $ 都是不合法的。

记得要开 __int128，然后就做完了。

P3423 [POI 2005] BAN-Bank Notes

可以直接多重背包，不知道为什么能过，反正就是过了。

正解的话可以直接用二进制分组优化，输出方案就直接拿个 \(bitset\) 记录一下每个 $ f_{j} $ 是否被选过。

P4563 [JXOI2018] 守卫

直接想歪了，本来以为可以单调栈，然后后面可以用线段树维护，结果其实并不能单调栈。

然后又想用 $ bitset $ 暴力维护它可以观测到的亭子，正确性和复杂度都不对。

正解其实是区间 $ DP $，考虑一段区间 $ [l,r] $，显然 $ r $ 是一定要放的，然后设 $ L_i $ 为 $ i $ 最左观测点。

那么 $ L_i $ 和 $ L_{i-1} $ 也是至少要放一个的。

然后后面区间 $ DP $ 即可。

P5504 [JSOI2011] 柠檬

\(DP\) 是显然的，$ f_i = max(f_j + cnt_{x,i}^2 \times x) $，这里显然要 $ a_i = a_j $ 不然肯定不优。

然后把那个拆开。

$ f_i = f_{j-1} + (cnt_{x,j} - 1)^2 \times x - 2\times cnt_{x,i} \times cnt_{x,j} \times x + cnt_{x,i}^2 \times x $

然后斜率优化板子题直接做即可。

P2890 [USACO07OPEN] Cheapest Palindrome G

看上去很简单的样子，但是我不会。

考虑一下区间 \(DP\)，设 $ f_{l,r} $ 为 $ [l,r] $ 变为回文串的最小代价。

那么考虑一段区间向外扩张，$ f_{l,r} $ 可以由 $ f_{l+1,r} $ 和 $ f_{l,r-1} $ 转移过来。

然后若 $ s_l = s_r $ 那么也可以从 $ f_{l+1,r-1} $ 转移过来。

CF997E Good Subsegments

析合树。

首先建出析合树，然后将每个询问挂到对应的 LCA 上。

容易发现，儿子里面是有可能不包含在区间里面的。

所以总方案数容斥一下就是：子树总贡献 - 子树中左端点在 $ l $ 左边的贡献 - 子树中右端点在 $ r $ 右边的贡献 + 左端点在 $ l $ 左边且右端点在 $ r $ 右边的贡献。

然后这个东西你可以用树状数组维护。

P3177 [HAOI2015] 树上染色

挺好的树上背包。

设 $ f_{u,j} $ 为 $ u $ 子树内放了 $ j $ 个黑点的最大值。

考虑一下贡献的形式。

对于一条边 $ u,v $，将它断开分为了两颗子树 $ a,b $，那么经过这条边的黑白路径条数即为 $ a_0 * b_0 + a_1 * b_1 \(（\) a_0,a_1 $ 分别为黑点和白点的数量）。

那么这样就可以 $ DP $ 了。

$ f_{u,j} = f_{u,j-k} + f_{v,k} + (k(m-k)+(siz_v - k)(n-m-siz_v+k)) * w $

然后注意一下转移的上下界即可。

CF2143D1 Inversion Graph Coloring (Easy Version)

好困难。

首先赛时很容易观察到一个事实，不能出现形如 $ i>j>k $ 且 $ a_i > a_j > a_k $ 这样的序列是一个好的序列。

那么最长严格下降子序列的长度小于等于 $ 2 $ 的序列即是好的。

考虑用 \(DP\) 维护这个东西。

设 $ f_{i,x,y} $ 为前 \(i\) 个数，最长严格下降子序列为 $ x,y $ 的方案数。

那么可以枚举 $ i,x,y $ 然后转移即可。

然后这个东西好像和 \(Dilworth\) 定理有关来着。