暑期模拟赛题解
CSP-J 模拟赛
2024.7.5 CSP-J 模拟赛1
T1
- 简单二分，判断即可。
T2
- \(60pts\) 的状压是好写的。
- 至于 \(100pts\)，考虑 dp 状态的合并，由于 \(m\) 的级别很小，考虑对后 \(m\) 个数状压，考察满足条件的情况。
- dp 难以优化的时候考察 本质相同的状态。
T3
- 数据范围显然想到区间 dp
- 区间 dp 的本质是合并。考察相交而不包含的子树，显然这样的情况对于答案一定有另外的贡献。
- 一般地，我们认为区间 dp 的转移式是 \(dp_{i,j}=\{dp_{i,k}+dp_{k+1,j}+w(l,r,k)\}\)，我们认为 \(w(l,r,k)\) 是 贯穿 \(k\) 的区间 所做出的贡献。
T4
- 考虑贪心，利用单调栈依次更新价值更大的点。
- 总而言之，我们不关心某一段路程是谁加的油，而关心 价格尽量低的油尽量加满。
2024.7.6 CSP-J 模拟赛2
T1
- 简单的送分模拟
T2
- 显然二分答案。考虑到 变换之前和变换之后 \(Y\) 的相对位置不变，于是列出关于数组下标和 \(Y\) 个数的表达式即可。
T3
- 对于 \(60pts\) 的部分分，bfs 有时也不失为一种爆搜的想法，求最优解/第 \(k\) 优解往往优于 dfs。核心原因是 bfs 到每种情况的时候保证当前步数是最优的，下次再遍历到可以使用 \(vis\) 数组不再遍历。
- 我们钦定所有点恒向前移动，核心关键点仍然是考虑到 变换之前和变换之后字母的相对位置不变，于是容易。转移。
- 由于只有 \(3\) 个字符，显然考虑设 \(dp_{i,j,k}\) 表示填了 \(i\) 个 \(K\)，\(j\) 个 \(E\)，\(k\) 个 \(Y\) 的方案数，转移是容易的。
T4
- 有 "前 \(K\) 大"，"第 \(K\) 大" 之类限制词的时候想到 枚举这个 \(K\) 大值。
- 于是枚举 \(K\) 大值与经过 \(>\) 这个值的数的个数即可。
2024.7.8 CSP-J 模拟赛3
T1
- 注意特殊情况的判断即可。
T2
- 考虑 \(>12\) 的比分与 \(<12\) 的得分本质相同，于是化简，一共只有 \(12\times 12=144\) 种情况了。
T3
- 考虑最优解
&一定尽量在前面。于是枚举每一个&的位置，计算能否与|交换即可。 - 具体的计算暴力只有 \(60pts\)，拆位计算每一位是可以通过的。
T4
- 暴力最好写状压，移位操作更好模拟。
- 看到数据范围仍然考虑区间 dp。考虑最终的情况总有一些大妈剩下，于是设 \(dp_i\) 表示前 \(i\) 个大妈中，留下第 \(i\) 个大妈后，最多能删去多少个。这样设状态的原因是方便转移。设 \(p_{i,j}\) 表示我们能否删去 \([i,j]\) 区间的大妈，显然这个数组是好转移的。我们认为 \(i-1,j+1\) 的大妈都留下，于是容易得出转移方程。
- 最后 \(dp_i\) 统计最终答案。
- 有些题目可以考虑 dp 套 dp，外层的 dp 用来统计答案，内层的 dp 用来具体计算某些值。
T5
- \(60pts\) 的做法可状压 dp，或是暴力枚举选了哪些歌，暴力推式子计算 \(k\) 首乐曲出现的概率。
- 背包！背包！背包！ 选物问题首选背包！！！
- 于是我们可以优化上文的第二种做法，用背包计算 \(k\) 首乐曲出现的概率。
- 对于 \(100pts\)，对于某一屏蔽值转移时，我们单独撤销其贡献即可。
2024.7.9 CSP-J 模拟赛4
T1
- 简单贪心即可。
T2
- 将每个人排序之后设 \(\textit{dp}_{i,j}\) 表示前 \(i\) 个人，最后一次在 \(j\) 处叫的最少次数，\(\textit{fp}_{i,j}\) 为其方案数。
- 对于 \(100pts\)， dp 转移的优化可以预处理出某一段的最小值或前缀和。
- 不要被繁琐的题意困扰！寻找关键点！不要读错题！
- 转化题意，将不可解的问题可解化。
T3
- 首先不要读错题。
- 考虑背包。具体地，由于值域较大，我们采取
bitset优化。
bitset<N> flg; flg[0] = 1; for (int i = 1; i <= n; i++) flg |= (flg << a[i]);
- bfs 或 dfs 搜出最终答案即可。
T4
- 考虑改变我们拿取的做法。
- 按照原题拿法难以 dp，于是考虑龙有时可以不选， 为后面的选择 "积攒次数"。
- 按照小明和龙的角色分类 dp 即可。
2024.7.10 CSP-J 模拟赛5
T1
- 根据数据范围基本来确定做法，注意 \(\boldsymbol{10^8}\) 小常数是可以过的！
- 于是化简式子，暴力代入即可。
T2
- 水题，送分。
T3
- 首先 \(n\le 200\) 的 \(70pts\) 是平凡的。暴力 dp 转移即可。
- 考虑方案数之间有无更为简单的转移。
- 显然我们可以通过当前的序列 整体 \(+1\) 的方式得到一个新的序列，于是我们考虑单个的转移和这样转移。
T4
- 假的 dfs 题，不再叙述。
T5
- 二分 + dp，老 \(\texttt{trick}\) 了。
- 对于 \(100pts\)，我们显然可以通过单调队列优化。
CSP-S 模拟赛
2024.7.11 CSP-S 模拟赛1
上来老老实实开T1！！不要闲的没事在后面的题目上耗很长时间！！
还拿到了 \(0\) pts.
T1
- 考虑 Floyd 的动态规划本质。于是先枚举中转点 \(k\) 即可。
T2
- 题目中奇怪的限制条件让我们知道矩阵中每个 \(\in [k,2k]\) 的元素可以直接输出，\(> 2k\) 的元素不合法。
- 于是我们只有一些 \(<k\) 的矩阵可选了。单调栈找到最大子矩阵，不断切割，分类讨论输出即可。
T3
- \(\varphi(n)=n\times \dfrac{a_i-1}{a_i}\) ，其中 \(a_i\) 为 \(n\) 的质因子。
- 考虑维护区间乘积以及区间中质因子存在与否。
- 考虑到 \(300\) 以内的质数只有 \(62\) 个，一般地， \(n\le 32\) 一般想状压 \(\texttt{int}\)，但 \(n\le 64\) 同样可以状压
long long。
T4
-
链的部分分提示了根号分治的正解。
-
显然对于 \(c\) 较大时可以暴跳， \(c\) 较小时可以预处理出 \(k\) 级祖先与 LCA 差分。
-
根号分治。
根号分治，对于一些题目，某些与 \(n\) 相关的操作在 \(n\) 很小时复杂度不优，但通过一些处理可以使得其复杂度正确，而 \(n\) 很大时的时候复杂度较优。此时我们设 \(B=\sqrt n\)，当 \(n\le B\) 和 \(n>B\) 时分别采取不同操作，使得复杂度为 \(\sqrt n\)。这两种操作一般一个是暴力，另一个是预处理。
根号分治的标志一般为时间复杂度直接与操作数值 \(n\) 相关，且 \(\sqrt n\) 的复杂度可以通过。
这种常见的按数值分治的 \(\texttt{trick}\) 要掌握。
-
将阈值 \(B=\sqrt n\) 即可。
2024.7.13 CSP-S 模拟赛2
T1
- 送分题，简单贪心即可。
T2
- 有时候奇怪的暴力时可以骗分的，甚至直接 \(\texttt{AC}\)。是吧 @zjyyyyy
- \(n\le 10^9\) 要想到根号做法。
- 若 \(A\) 的花费较小，显然 \(A\) 最多用 \(\dfrac{n}{A}\) 次，\(B\) 最多用 \(A\) 次，二者必有一个 \(<\sqrt n\)，根号分治即可。
T3
- 结论题要根据打表出来的数据猜结论。具体不多讲。
T4
- 树上问题若 \(A\) 是 \(B\) 做贡献的条件，考虑枚举每个 \(A\)，计算由于 \(A\)，\(B\) 对全局做出了什么贡献。
- 于是我们枚举这个 \(A\)，暴力跳他的所有祖先。由于没有撤销操作，每个祖先最多被跳一次即可。
2024.7.14 CSP-S 模拟赛3
T1
- 比较 simple 的换根 dp，貌似最短路也可做。
T2
- 异或最大值问题自然想到 \(01\) Trie 上贪心解决。
- 于是对于集合中每一个 \(v\)，考虑将 \(v\) 的质因子加入 Trie 树当中，查询时树上查询即可。
T3
- 二分 + \(\texttt{check}\)，暴力总可以出奇迹。
- 正解是 dp，然而没什么人这样做。
T4
- 考虑 \(a,b\) 两人移动的先后顺序受什么影响。
- 于是发现起终点与区间之间的限制。然后像网络流一样建出图。发现图是由点连向区间的。
- 图/树上区间问题想到 线段树优化建图。
线段树优化建图，就是将连至某个区间的边改为连至该区间线段树上对应的节点，同时在线段树建树时对线段树每一层之间的节点相连。这样连边的边数为 \(n\log n\) 级别。
2024.7.15 CSP-S 模拟赛4
T1
- 细节蛮多的其实，但是思路并不难。前缀和优化是好想到的。
T2
- 考虑裴蜀定理，方程 \(ax+by\equiv 1 \pmod p\) 有解当且仅当 \(\gcd(a,b)=1\)，同时容易扩展到 \(n\) 个方程的形式。
- 于是暴力计算 \(\gcd\) 即可。
T3
- 显然坐标 dp。考虑到 dp 的过程按照权值递增划分有阶段性，考虑维护每一个阶段的最大值优化转移即可。
T4
- 异或问题考虑可持久化 \(01\) Trie。
可持久化数据结构的本质是按照时间建立副本，副本之间建立联系，通过前缀和的形式维护区间信息。
2024.7.24 CSP-S 模拟赛5
T1
- 线段树维护树的直径板子题。
- 或者点分树暴力做。
T2
- \(50pts\ O(nkp)\) 的暴力 dp 是简单的。
- 于是考虑依照同余关系寻找最优状态转移。
T3
- 简单的题目，贪心计算答案即可。
T4
- 构造题先考虑满足难一些的限制，再向易一些的限制调整靠拢。
- 于是先构造 \([1,n]\) 的序列使序列严格递增，再通过前后缀的调整满足和为 \(0\) 的限制。
2024.7.25 CSP-S 模拟赛6
T1
- 构造题。显然没有 \(1\) 的序列一定不合法，于是最大化含 \(1\) 的序列的个数，于是 \(1\) 放在中间。
- 然后尽量使序列不含小质数，即 \(2,3\)。于是 \(2,3\) 放两边。
- 当然也可以打表找规律。
T2
- 首先显然二分 \(npy\) 最小的不满意度 \(k\)。
- 然后贪心地按照深度由深入浅枚举节点，找到其 \(k\) 级祖先并以此为起点染色。最后判断是否还有未被染色的节点。
- 复杂度最坏是 \(O(n^2)\) 的，加上剪枝跑得飞快。
T3
- 二选一的题考虑建图。
- 显然如果连成基环树有 \(n\) 的贡献，连成树有 \(n-1\) 的贡献。
- 然后用启发式合并的可撤销并查集维护一下贡献的情况即可。
- 细节比较多，要注意。
T4
- 考虑对于 \((i,j)\)，何时选 \(j\) 比选 \(i\) 更优。
- 则 \(s_i>s_j\)。设 \(p_i\) 为前 \(i\) 个数正数之和，\(q_i\) 为前 \(i\) 个数负数之和。
- 则 \(s_i=\dfrac{p_i}{P}-\dfrac{q_i}{Q},s_j=\dfrac{p_j}{P}-\dfrac{q_j}{Q}\)。
- 则 \(\dfrac{p_i}{P}-\dfrac{q_i}{Q}>\dfrac{p_j}{P}-\dfrac{q_j}{Q}\)。
- 则 \(\dfrac{p_i-p_j}{P}>\dfrac{q_i-q_j}{Q}\)。
- 则 \(\dfrac{p_i-p_j}{q_i-q_j}>\dfrac{P}{Q}\)。
- 于是我们把 \(p,q\) 看做横纵坐标建系。可以再凸包上二分斜率。
- 由于有修改操作，考虑分块。整块打标记，散的暴力重构。
- 不过这样一来似乎刚刚拆的那个斜率式子没用了？代码还在实现中。
2024.7.26 CSP-S 模拟赛7
T1
- 简单贪心后排序即可。
T2
- 先推出使序列满足条件的性质，再暴力组合意义推出式子。
- 几乎不可做。
T3
- 就是 7.24 T1 的加强版，只不过必须维护直径，点分树做不了了。
T4
-
"至少有两碗面含有" 的条件就很二项式反演。
-
于是设 \(f(i)\) 表示 \(i\) 种配料出现次数 \(\le 1\) 次的方案数，则 \(ans=\sum_{i=0}^n(-i)^i{n\choose i}f(i)\)
-
现在考虑 \(f(i)\) 的求法。显然对于 \(i\) 以外的调料有 \(2^{n-i}\) 个集合，每个集合可以选或不选，也就是有 \(2^{n^{n-i}}\) 种选法，用欧拉定理优化其实就是 \(2^{2^{n-i}\mod \varphi(p)}\mod p\)。由于 \(p\) 为质数，\(\varphi(p)=p-1\)。
-
考虑 \(i\) 种配料的求法，考虑枚举 \(k\) 表示配料放入的集合数，即放入几碗面中。
-
然后发现这个东西就是第二类斯特林数，设 \(s_{i,j}\) 表示 \(i\) 个元素放入 \(j\) 个集合的方案数，有
\[s_{i,j}=s_{i - 1,j - 1}+s_{i - 1,j}\times (j + 1) \] -
然后合并式子求出答案即可。
2024.7.27 CSP-S 模拟赛8
T1
- 首先 \(50pts\) \(O(mod^2 m)\) 的 dp 是简单的。
- \(80pts\) 考虑矩阵优化。
- \(100pts\) 的话，选物、背包问题，可以考虑二进制优化。预处理 \(2^m\) 次操作 \(x\) 的期望，就好转移了。
- 原根也可以做，然而我不会。
T2
- 首先 \(t=0\) 的树形 dp 是显然的。
- \(t=1\) 有高斯消元的部分分。
- 从 \(b\) 得到 \(a\) 对于 dp 式子变形即可。
T3
- 首先 \(\text{typ=0}\) 是好做的。按照组合意义列出式子即可。
- 然后暴力 \(O(n^2)\) dp 可以过剩下的 \(55pts\)。
- 至于最后的 \(20pts\)，考虑卡特兰数。\(\text{typ=1}\) 是典型的卡特兰数形式，\(\text{typ=3}\) 是对卡特兰数的一个变形。
- 然后 \(H(n)={2n\choose n}-{2n\choose n-1}\)，计算即可。
T4
- 我们认为放数是由 \(1\sim n\) 依次放置的过程。
- 于是令 \(dp_{i,j,k}\) 表示正在放 \(i\) 这个数，有 \(j\) 个可放数的空段，当前和为 \(k\) 的方案数。
- 考虑空段与贡献的情况，分类讨论转移即可。
- 但是细节特别多。
2024.7.29 CSP-S 模拟赛9
T1
- 考虑模数为 \(2\) 时，答案最大为 \(2\)。于是我们只需要计算何时答案为 \(1\)。
- 记 \(k_i=a_i-a_{i-1}\)。考虑计算 \(x=\gcd(k_1,k_2,\cdots,k_{n-1})\)。显然若 \(x\neq 1\)，当模数为 \(x\) 时取最优答案 \(1\)。否则取模数为 \(2\) 最优。
T2
- 显然计数题无序问题有序化，考虑 dp。设 \(dp_{i,j}\) 表示放置前 \(i\) 个，元素和为 \(j\) 的方案数。
- 于是考虑转移的来源。设放置的最后一个数为 \(x\)。
- 若 \(x=1\)，显然 \(dp_{i,j}\rightarrow dp_{i-1,j-1}\)
- 若 \(x\neq 1\)，考虑所有元素和为 \(j\) 的方案必有整体 \(\times \dfrac{1}{2}\) 的同构方案和原方案一致。于是 \(dp_{i,j}\rightarrow dp_{i,2j}\)。倒序转移即可。
- 有分数，不好转移，于是想到整体同构的转移。
T3
- 移动波特是不优的，考虑移动原点。
- 注意到 "原点对称性质"，于是复杂度降为 \(O(n)\)。
T4
- 奇怪的图形计数题。首先只考虑计算正的三角形的贡献，倒着的把图倒过来即可。
- 仍然考虑枚举每一个右下角的点计算贡献。计算每个点朝左边最多拓展到的距离 \(l(i)\)，向左上最多拓展到的距离 \(t(i)\)，则贡献区间为 \(\min(l(i),t(i))\)。
- 考虑计算该点正左方点正向右的贡献 \(s(i)\)。于是对于每一行上的每一个点，开一个树状数组差分计算即可。
2024.7.30 CSP-S 模拟赛10
T1
- 显然 \(x\) 的取值最多有 \(n\) 种。枚举即可。
T2
- 和2024.7.6 的题很像。加了颜色相同的球不能相邻的条件，所以加一维表示最后一个球求的颜色转移即可。
T3
- 神仙题。
- 首先容易考虑到对于这个价值，等价于一定有 \(b_i=0\) 时的价值。于是考虑计算 \(b_i\in [0,a_i]\) 的贡献减去 \(b_i\in [1,a_i]\) 的贡献得到答案。
- 考虑 \(b_i\) 的实际意义是最终局面下每个人从自己的球中选出一个的方案数，于是考虑计算这个方案数。
- 分类讨论选出的球是来自自己还是上一个人，dp 即可。
T4
- 思路还没搞清楚，搞清楚了再更。
2024.7.31 CSP-S 模拟赛11
T1
- 显然 \(x,y\) 较小，于是可以枚举最终的结果，计算即可。
T2
- 显然交换具有传递性，于是并查集维护即可，答案为每个并查集大小的阶乘。
T3
- \(45pts\) 的状压概率 dp 是好想的。
- 考虑 拆期望。利用期望的线性性质求每个水管漏水的概率。
- 显然每个水管漏水的概率和前面漏水水管的个数有关系。于是设 \(dp_{i,j}\) 表示前 \(i\) 个水管，共漏了 \(j\) 次水的方案数。转移方程是好得到的，然后容易得到每个水管漏水的概率。
T4
- 显然用数据结构不好维护。
- \(n\le 10^5\)，考虑分块。块内部用
std::deque维护，两边的块暴力重构即可。
2024.8.1 CSP-S 模拟赛12
T1
- 利用概率的定义用组合式子来推即可。
T2
- 做法很多，见 题解
T3
- 注意到颜色相同的点等价。
- 观察到每个点覆盖的区间总形成一棵二叉树，于是只在左右侧寻找权值最大的节点转移即可。
- 转移的过程可以用
std::bitset优化。
T4
- 题意很复杂。
- 首先显然想到贪心，但贪心一定是假的。
- 于是想到 dp。设 \(dp_{i,j}\) 表示前 \(i\) 局游戏把 \(j\) 个
?变为1，转移方程易得。 - 注意最终的特判。
2024.8.3 CSP-S 模拟赛13
T1
- 序列最大值不好维护，考虑由小到大来维护。
- 显然权值较小的节点会挪到两侧，于是求每个节点左右的逆序对数取 \(\min\) 相加即可。树状数组维护。
T2
- 考虑最优策略一定在端点上。
- 直接维护决策是困难的。考虑维护 最优决策区间。贪心地维护即可。
T3
- 设 \(b_i=\text{sgn}(a_i-k)\)，显然只有 \([0,-1,1],[0,1,-1]\) 的情况会额外增加 \(1\) 的贡献。
- 于是线段树维护 \(-1,1\) 交叉出现的个数即可。
- 代码较难实现，实现ing...
T4
- 朴素 dp 有 \(60pts\)。
- 考虑每个人的行动都是连续的几段。两个人我们不好维护，我们只维护一个人的行动，同时计算另一个人的贡献。
- 具体地，设 \(dp_i\) 表示前 \(i\) 个快递之后的最优决策。转移方程是容易的：
- 将 \(i,j\) 分离，是一个线段树优化的形式，开两棵线段树即可。
2024.8.5 CSP-S 模拟赛14
T1
- 口胡结论博弈题。
- 注意到每次操作的本质是让逆序对 \(ans\) 个数 \(-1\) 或 \(-2\)，于是按照 \(ans\mod 3\) 分类输出即可。
- 或者根据样例猜结论也不是不行。
T2
- 注意到没有被操作的数是相邻的。
- 于是采用线段树维护数列情况，按照两端端点是否被选择分类讨论即可。
T3
- 考虑显然的贪心。由两端到中间两两配对，根据固定的左端点选择右端点即可。
- 考虑对于每个左端点选择右端点的过程，这是具有单调性的，二分不好做，采用倍增处理。
倍增核心代码：
int l = 1, r = 1, p = 1;
while (r <= n) {
if (!p) {
++cnt;
++r;
l = r;
p = 1;
}
if (r + p <= n && chk(l, r + 1, r + p))
r += p, p <<= 1;
else
p >>= 1;
}
- 注意
chk函数里要用归并排序优化。
T4
- 首先建出最短路图。
- 然后是一个单调栈维护凸包状的东西，改完了再来填坑。
2024.8.6 CSP-S 模拟赛15
T1
- 考虑将每一块饼拆成 \(m\) 块面。这样一来答案就是 \(\dfrac{\sum a_i}{n}\)。
- 加上饼不能拆开的限制，答案对于 \(\max a_i\) 取 \(\max\) 即可。
T2
- 考虑答案只与最终点的分布形态有关。于是 不考虑敌我限制地 计算收益即可。
T3 & T4
- 神奇数论题 + 神奇 dp，补上之后再说吧。
2024.8.7 CSP-S 模拟赛16
T1
- 考虑反转串操作的传递性，于是从后往前枚举可翻转的段即可。
- 字符串判等用 \(\text{Hash}\) 实现。
T2
- 清新分讨题。
- 若原数列有序，需要 \(0\) 次达成。
- 若 \(a_1=n\) 且 \(a_n=1\)，则需要 \(3\) 次达成。
- 枚举每一个数，判断若可以成为 \(k\)，则可以 \(1\) 次达成。
- 否则 \(2\) 次达成。
T3
- 多次区间询问考虑离线，区间内所有 点对之间的询问 考虑离线分治处理。
- 于是采用类似 CDQ 分治的算法，递归处理 \([l,mid]\) 和 \([mid+1,r]\) 的贡献，当前处理所有 \([x\in[l,mid]\rightarrow y\in[mid+1,r]]\)。
- 于是降序枚举 \(x\)，考虑到答案的贡献会分为全在左边，一左一右，全在右边三类，分别列出式子，线段树维护这三坨东西即可。
- 时间复杂度 \(O(n\log ^2n)\)。
T4
- 图上问题没有好的多项式时间复杂度解法。看到 \(n\le 5\times 10^4\)，考虑操作分块。
- 具体地，令块长为 \(S\)，则每 \(S\) 个操作进行一次处理，将操作按照重量降序排序，用并查集维护连通性。
- 对于 本块内 没有修改的边直接加入。枚举操作中的询问操作，对于修改过的边注意时间要求，若重量满足要求且时间在其之前，注意撤销操作，因此使用可撤销并查集维护。
2024.8.8 CSP-S 模拟赛17
T1
- 注意到 \(1\sim n\) 范围内所有数的因数总和是 \(n\log n\) 级别，于是我们可以暴力枚举每一段关系。
- 具体地，固定 \(a_i\)，枚举它的每一级倍数 \(b_j\)，树状数组优化转移即可。
T2
- 分析题意得出是求区间众数。
- 然后跑莫队/回滚莫队/分块即可。
T3
- \(22\) 种字符可以状压成
int表示状态。 - "子树内所有路径" 这种子树内统计信息的东西想到枚举根节点进行统计，同时继承子树信息。
- 对于经过根节点的路径，枚举状态和每一个儿子，合并统计信息即可。
- 统计的时候注意使用启发式合并优化复杂度。时间复杂度是 \(O(23n\log n)\)。
T4
- 显然差分序列单调，且关于某一最小点/某一最小段对称。于是考虑计算这个差分数组和最小点的方案数。
- 显然我们只需要 dp 其中一边的情况即可。对于单调的序列，有经典的 dp，设 \(dp_{i,j}\) 表示长度为 \(i\)，和为 \(j\) 的方案数。
- 对于差分序列，由于有 \(A\ge 0\) 的限制，使差分序列最长就是全为 \(-1\)， 简单计算得到差分序列最长为 \(\sqrt m\)。于是这样 dp 的复杂度是 \(O(m\sqrt m)\) 的。
- dp 式子是套路的，整体 \(+1\) 求和增加 \(\dfrac{i(i+1)}{2}\)，末尾 \(+1\) 求和增加 \(i\)，转移即可。注意记录副本 \(fp=dp\)。
- 对于答案的统计，对于最小值的枚举，当最小值为 \(0\) 时，最小值的个数无关紧要，于是对于 \(dp_{i}\) 求前缀和。
- 当最小值的个数 \(\neq 0\) 时，显然最小值的 \(+1\Leftrightarrow\) 总和 \(+n\)，于是对于 \(dp_{j}\) 做完全背包。
- 输出时注意我们认为上面两条的套路是确定最小值的情况的，对于对称点的一边答案是处理后的 \(dp\) 数组，而另一边相当于最小值个数与大小已经确定，于是采用未处理的 \(fp\) 数组。
2024.8.10 CSP-S 模拟赛18
T1
- 注意到原命题等价于去掉两条边后图有欧拉回路。于是考虑到自环不影响答案。
- 注意到两条不相邻边去掉后难以形成欧拉回路。于是枚举自环使用个数，组合意义计算答案即可。
T2
-
列出式子得到
\[\sum_{i=1}^nD\lceil \frac{a_i}{D}\rceil\le k+\sum_{i=1}^n a_i \] -
考虑到 \(\lceil \dfrac{a_i}{D}\rceil\) 的取值范围只有 \(O(\sqrt{a_i})\) 种，于是暴力枚举每种 \(\lceil \dfrac{a_i}{D}\rceil\)，口胡得出此时 \(D\) 的最大取值同样是 \(\lceil \dfrac{a_i}{D}\rceil\)，代入判断即可。
T3
- \(k\le 300\)，考虑 \(O(n^3)\) 的 dp。
- 显然每个层数相同的子树等价，于是考虑第一维设为层数。显然不论怎么设状态，每个根节点的状态总有左右子树合并转移而来，这启示我们将子树里的某些东西设为状态。
- 注意到经过根节点的路径本质是与子树内原有的路径连接而来。于是考虑将子树内 不相交合法路径 设为一维状态。具体地，设 \(dp_{i,j}\) 表示第 \(i\) 层，子树内有 \(j\) 条不相交路径的方案数，转移是容易的。
- 对于 \(j\) 的范围，考虑到每层转移最多减少 \(1\) 条路径，实质上还是 \(O(k)\) 级别。时间复杂度 \(O(k^3)\)。
T4
- 显然考虑区间 dp。朴素的想法是设 \(dp_{l, r}\) 表示 \([l,r]\) 之间全部分发的最小价值。但是由于 \(\max\) 和 \(\min\) 的限制，直接转移是困难的。
- 考虑到 \(n\le 50\)，支持再设两维状态。考虑选物的过程，是先在中间拿出一块，再整合之后继续拿走。改变思路，考虑关注 拿走的一块的状态。
- 具体地，设 \(fp_{l,r,mx,mn}\) 表示 \([l,r]\)，部分成绩单未拿走，这部分的 \(\max,\min\) 分别为 \(mx,mn\)，其余成绩单拿走的最小价值。这样的转移是好刷表的，对于 \(r+1\)，我们只需要关心它拿走了还是没有拿走，当拿走时枚举拿走的右端点即可。
- 时间复杂度是 \(O(n^5)\) 的。