垃圾车（1） [随缘更新]

[集训队互测 2019] 绝目编诗

题本身是还好的，但是存在大量乱搞可以轻松通过此题，所以只能作为一个思路上的启发。

首先试着提出一个 poly 做法：爆搜每个环，一个长度为 $\ell$ 的环会被统计 $2\ell$ 次（每个环上的点顺逆各一次），于是我们经过的点数上界是 $\mathcal O(\sum\limits_{\ell \le n}\ell^2)=\mathcal O(n^3)$，注意搜索的过程中不能搜到一个不被任何可能环覆盖的边，于是每走一个点可以 $\mathcal O(n)$ 判断走到这个点之后，是否存在一个环，时间复杂度 $\mathcal O(n^4)$。

然后结论来了：$m>n+2\sqrt n$ 时必有解。

假设一张图有长度为 $3\sim n$ 的环各一个，每条边有 $\dfrac {1} {\sqrt{n}}$ 的概率被删除，那么长度为 $\ell$ 的环未被删的概率为 $P(\ell)=\left(1-\dfrac{1}{\sqrt{n}}\right)^\ell$，期望剩下的环个数为 $\sum\limits_{3\le \ell \le n}P(\ell)< \sqrt n$。因为是期望，所以我们一定能构造一组删去 $\sqrt n$ 条边的方案，使得剩下环数 $\le \sqrt n$，那么再删 $\sqrt n$ 条边就没有环了，于是得到了 $m$ 的上界。

剩下部分是容易的：对非树边建立虚树，这样点数降到了 $\sqrt n$，时间复杂度 $\mathcal O(n^2)$。注意新树是带权的，所以判定无解的时候要保证所有长度为 $\ell$ 的环上点数也一样，否则就是两个不同的环。

[NOI2024] 百万富翁

首先肯定是问一个团，然后如果我要求 $n$ 个元素减小到 $m$ 个元素，令 $w_i=\dfrac{i(i-1)}{2}$，$a_0=w_{\left\lfloor\frac n m\right\rfloor}$，$a_1=w_{\left\lfloor\frac n m\right\rfloor+1}-a_0$。有 $\text{cost}(n,m)=ma_0+(n\bmod m)a_1$。

先对 $m$ 做整除分块，固定了 $a_0,a_1$。把内部 $\bmod$ 拆开得到 $\text{cost}(n,m)=na_1+m(a_0-\left\lfloor\dfrac n m\right\rfloor a_1)$。因为第一次整除分块限定了 $m\in [l,r]$，再次对 $[l,r]$ 跑整除分块得到 $[L,R]$，此时确定了 $\left\lfloor\dfrac n m\right\rfloor$。又因为有 $f(d,n)=\min f(d-1,m)+\text{cost}(n,m)$。盲猜取 $L,R$ 就能得到最优解，的确跑出来了。

还有一些更方便的：一个是猜测前几次一定都选 $w_2$，还有一种是对 $\dfrac n m$ 做整除分块，并在相邻值域枚举几个就过了。

「Wdoi-1.5」旅人 1977

蠢蠢题。显然把线段树扔到状态里是不合适的，瓶颈在于要动态处理 pushdown。那你直接先 pushdown 后面就不用处理了。具体的，定义一个状态 $S$ 是由若干个线段树上区间左端点构成的集合，且这些区间恰好覆盖了 $[1,k]$。那么一条路径一定可以拆分成 $len$ 段，第 $i$ 段状态是 $S_i$，且有 $S_{i+1}\subseteq S_i$。每条路径上的区间操作一定恰好下放到了对应 $S$ 中的所有区间里。打表发现 $S$ 的量级 $T$ 约为 $1.6\times 10^4$，直接最短路是 $\mathcal O(nT\log mT)$ 的，但这其实是个分层图所以只要对每层 dij 就好了，dij 部分 $\mathcal O(nT\log m)$，其他部分复杂度看个人实现。

[eJOI 2018] 循环排序

某人推荐的，蠢蠢题。如果是一个排列，发现规则是先合并若干个置换环，最后每个置换环转一次。如果有相同的值，那么每个值建一个虚点，跑一遍欧拉回路就变成环了。

[USACO24FEB] Minimum Sum of Maximums P

如果一个序列固定了两端值为 $\ell, r$，且中间需要填入集合 $S$，令 $\ell \le r$，手玩一下发现最小代价为 $|\ell-\min S|+|r-\max S|+\max S-\min S$。于是可以按照值域从大到小填，但是固定数字之间填的个数是固定的，这很棘手。发现有一个性质：任意两段的 $[\min S, \max S]$ 要么包含要么相离，所以可以对值域做区间 dp，时间复杂度 $\mathcal O(n^23^k)$。

[POI 2014] RAJ-Rally

求出拓扑序 $a$，一条没有经过 $u$ 点的路径 $\ell$，一定存在一条边 $(x,y) \in \ell$，有 $a_u\in(a_x,a_y)$。算出每条边对 $u$ 的区间贡献，扫描线。

P14256 平局（draw）

我们需要给内层匹配刻画一个非常强力的匹配方式，这样才能做一个类似 dp of dp 的形式，如 AGC022E。这题很好的一点是相对关系可以唯一确定整个序列：令 $\texttt>,\texttt =,\texttt<$ 分别表示左侧的数能赢 / 平局 / 会输右侧的数，那么观察一下有以下消除方式：

• $\tt>>\ to\ <$。
• $\tt<<\ to\ >$。
• $\tt><\ to\ =$。
• $\tt<>\ to\ <or>$。

和上面那题差不多，我们动态维护一个栈，贪心匹配：最终形式一定是 $\tt(<)>>>...>>$，前面如果有 $\tt <<$ 合成 $\tt>$ 一定更优，于是直接列出自动机就容易 dp 了。

「LAOI-16」顽疾

入手有两种思路：从 $a$ 来计算 $b$ 的贡献，或者从 $b$ 计算 $a$ 的贡献。如果直接填 $b$，$a$ 的贡献是难以计算的，所以考虑前者，也就是对固定的 $a$ 设计一个填数策略，而且最好是连续填数，否则 $a$ 的贡献仍然难以计算。

对于一个 $a$，我们按照值域从两边往中间填。初始设置两个指针 $l,r$，表示已经填完了 $[1,l),(r,v]$ 的数，正在考虑填 $l/r$。如果 $lr\le w$，那么我们先填 $l$，而且后面填的所有数 $u\in [l,r]$ 必然满足 $lu\le w$，这一步很精巧的找到了一个无后效性的性质（也许思路切入点是找到一个决策顺序，线性结构永远是最好处理的）。同理的，如果 $lr>w$ 那么先填 $r$，后面填的数 $u\in [l,r]$ 必然满足 $ru\ge w$。系数的 $t$ 幂次非常经典，可以拆成组合意义。所以我们设计状态 $f_{i,j,l,r,x,y}$ 表示填了 $i$ 个数，有 $j$ 个空位可以填，当前在填值域 $[l,r]$，其中左右组合意义放的球数分别是 $x,y$ 个，复杂度 $\mathcal O(n^2k^2t^3)$。

但是实际上不用记录 $[l,r]$，任意两个数之间肯定有一个决策先后顺序，所以预处理这个顺序，$l,r$ 两维可以缩成一维，复杂度 $\mathcal O(n^2kt^3)$。

upd：上面这个填数结构在 [ARC148E] ≥ K 出现过，而且那题模型更加简单。

CF1007E Mini Metro

如果我操作到了 $i$，前 $i-1$ 个站台必定清空。换句话说，后面站台的状态和前面无关，所以按站台编号从大往小做：每次取出最大一个至少被接过一次人的站台 $x$，假设接 $x$ 站台的的最后一个时刻是 $t$，容易发现时间段 $[1,t],(t,n]$ 就变成了两个子问题：前者是初始是 $a_i$，最少的次数使得前 $x-1$ 个站台清空，后者是初始是 $b_i$，最少的次数使得在规定时间内站台不爆，对应设计两个状态直接转移至 $\mathcal O(nt^2)$ 的，有些细节。

【MX-S10-T3】『FeOI-4』寻宝游戏

没写，非常令人疑惑的题目。我盯着这个形式好久也没找出什么美丽的策略，最后告诉我只要让最大的不动就好了，想想也是对的，那为啥我不会。

考虑长度 $>2$ 的情况，我们假如让一个盒子 $x$ 不动，令剩下盒子里最多放了 $mx$ 个，操作次数显然是 $\max(\dfrac{s-x}{2},mx)$，其中如果 $s-x$ 是奇数要额外多一次操作，所以只要考虑 $x$ 是最大值或者次大值的情况，后者是因为可能最大值的 $s-x$ 是奇数，劣一点。然后对长度 $\le 2$ 特判，一些无解，一些可以规约到长度为 $3$ 的情况。

[THUPC 2023 决赛] 百合

瓶颈在于建边，考虑优化建图。新建点 $(u,i,j)$ 表示节点 $u'$ 的前 $i$ 位被修改了 $j$ 个，目前是 $u$ 的最小代价，最后再加一个 $(u,n,j)\rightarrow u$ 权值为 $a_j$ 的边，$\mathcal O(2^kk^3)$。观察到新加的有效边只有 $2^kk$ 条，其他的更新到直接 bfs 一遍，$\mathcal O(2^kk^2)$。

*【MX-S12-T4】Sea, you again

没写，口胡一下。令 $f_{i,j,k}$ 表示考虑最低 $i$ 位，目前合并到了第 $j$ 位，其中第 $j$ 位为 $k$ 的答案总和，还要记一维数位 dp 的限制。$g_{i,j,k}$ 表示对应的方案数，$j$ 这一维肯定要优化掉，开始想的从高到低 dp，但这样要记两个 $\mathcal O(B)$ 量级的东西。其实直接把 $B^j$ 这个系数摊到 $g$ 里面去就好了，然后转移可以差分优化掉。

*P14510 夜里亦始终想念着你

没写，之后补。看成 $0$ 每次可以移动两格。考虑判定 $S$ 的合法性：先把 $0$ 全部移到左边，按顺序填入 $S$ 内的 $1$，如果占到了 $0$ 的位置，把后面的 $0$ 整体向右移两格。对强制往后移动的次数计数（这里比较厉害），枚举次数 $i$，那么可以从 $0$ 里面钦定 $i$ 次移动，同时剩下的空位可以随便填，算出来是一个组合数求和，里面的变量单次修改变动是 $\mathcal O(1)$ 的，推一下式子就能得出来了。