[合集]简单题选做
皎月半洒花
2020-05-01 07:57:36
大家有什么有趣的题目欢迎推荐给我啊！
洛谷博客如果不支持某些 Latex 的渲染我也没治啊。
# [Luogu4318]完全平方数
> 小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
>
> 这天是小 X 的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数，然后选取了第 K 个数送给了小 X。小 X 很开心地收下了。
>
> 然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗？
>
> $K\leq 10^9$
考察 $\mu$ 的容斥意义的神题 orz
## Sol 1
发现 $\mu$ 函数的性质，$\mu (x) = (-1)^k$，当且仅当 $x$ 不含平方因子，且 $x$ 的不同素因子个数为 $k$。
所以就考虑先二分，二分完了求一下 $1\sim x$ 中不是完全平方数倍数的数的数量是否 `>mid`。考虑这个东西怎么求。发现根据容斥，可以知道应该是「有 $0$ 个不同质因子的平方的倍数数量」-「有 $1$ 个不同质因子的平方的倍数数量」+「有 $2$ 个不同质因子的平方的倍数数量」。
另一方面，考虑对着每个**不含平方因子**的数 $x$ 计数，计包含 $x^2$ 的数的个数。根据容斥可以得到答案应该是：
$$
\sum _{i=1}^{\sqrt n} \mu(i)\lfloor \dfrac{n}{i^2}\rfloor
$$
原理是，根据 $\mu$ 的性质，具有平方因子的数不会被统计，同时容器系数恰好就是 $\mu$。
这东西可以直接 $\sqrt n$ 求。复杂度 $T \cdot \sqrt n \log n$
顺便记录一个很绝的 `idea:`
## Sol 2
根据 $\mu$ 的性质，发现似乎只有 $\mu(x) = 0$ 时，$x$ 才会被讨厌。所以其实二分求的就是
$$
\sum _{i=1}^{x}\mu^2(x)\leq K
$$
然后这东西可以直接杜教筛。于是复杂度就变成了 $T\cdot n^{\frac{2}{3}} \log n$。然而实际记忆化了会更快。
## 总结
其实这个东西一定程度上证明了
$$
\sum_{i=1}^{n} \mu(i)^{2}=\sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \mu(i)\left\lfloor\frac{n}{i^{2}}\right\rfloor
$$
这其实是可以反演出来的。考虑对左边进行变形，令 $\zeta(x)$ 表示 $x$ 最大的平方因子。那么有
$$
\begin{aligned}
&\sum_{i=1}^n\mu^2(i)\\
=&\sum_{i=1}^n [\zeta(i)=1]\\
=&\sum_{i=1}^n\sum_{d|\zeta(i)}\mu(d)\\
=&\sum_{i=1}^n\sum_{d^2|\zeta(i)}\mu(d)\\
=&\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d^2}\rfloor\\
=&\sum_{d=1}^{\lfloor\sqrt n\rfloor}\mu(d)\lfloor\frac{n}{d^2}\rfloor
\end{aligned}
$$
其中第三个等号是借助了 $\mu$ 的性质：因为 $\zeta(i)$ 根据定义本身是一个完全平方数，所以如果 $d|\zeta(i)$ 但是 $d$ 不包含平方因子，说明 $d^2|\zeta(i)$ ；包含平方因子会被 $\mu(d)=0$ 直接干掉。最后一个等号是因为可以知道 $d>\lfloor\sqrt n\rfloor$ 时最后一个因式恒为 $0$ 。
这似乎是某次听课听来的内容…但是当时并没有整理这个。想来已经是远古时期的回忆了。
# [UVA1614]Hell on the Markets
> 给出一个数列 $\{a_n\}$，保证 $\forall i, 1\leq a_i\leq i$。求是否可以分成相等的两半，并给出方案。
>
> $n\leq 10^5$。
>
考虑一个引理。如果 $\forall i, 1\leq a_i\leq i$ 的话，那么 $\forall v\in[1,\sum_{j=1}^ia_j]\cap \mathbb{Z_+}$ 都可以被凑出来。 证明的话考虑数学归纳。即现在只需要证明 $[s_{i-1}+1,s_{i-1}+a_i]$ 可以被凑出来即可。发现对于一个 $s_{i-1}+k$ 而言，因为根据归纳 $[1,s_{i-1}]$ 都可以被 $a_1\sim a_{i-1}$凑出来且有 $s_i+k-a_i\leq s_{i-1}$ ，所以证毕。
那么综上，在判断 $v=\frac{\sum_{i=1}^na_i}{2}$ 是否可以被凑出来时，根据上面的贪心特性，要从后向前推，每次选择一个当前小于 $v$ 的最大值减掉即可。
# [HNOI2011]数学作业
> 给定正整数 $n,m$，要求计算 $\text{Concatenate}(n) \bmod \ m$ 的值，其中 $\text{Concatenate}(n)$ 是将 $1 \sim n$ 所有正整数 顺序连接起来得到的数。
>
> $1\le n \le 10^{18}$，$1\le m \le 10^9$。
…考虑递推，那自然是 $f_{i}=(f_{i-1}\cdot T+i)\bmod m$ 。其中 T 是根据不同的数字位数而变的这么一个计数器。于是就是分段矩乘即可。
# [Luogu5110]块速递推
> $$a_{n}=233a_{n-1}+666a_{n-2},a_{0}=0,a_{1}=1$$ 。
>
> 求这个数列第 $n$ 项模 $10^9+7$ 的值，一共有 $T$ 组询问。
>
> $1\leq T\leq 5\times 10^7,1\leq n\leq 10^{18}$ 。
朴素的矩乘是 $8\cdot \log n$ 的样子。这样算出来复杂度是 $O(8\cdot T\cdot \log n)$ ，好像很慢的样子。
于是考虑预处理一点东西。比较常见的方法当然就是分块来做，预处理 $a^{1},a^{2},a^{3}\cdots a^{\sqrt n},a^{2\cdot \sqrt n},a^{3\cdot \sqrt n}\cdots$ 这些。那么复杂度度转化成了 $O(\sqrt n\log\sqrt n+8\cdot T)$。
注意到可以借助扩展欧拉定理 $a^b\equiv a^{b\bmod \varphi(m)+\varphi(m)}\pmod{m}$ 使得复杂度变成 $O(\sqrt{Mod}\log\sqrt{Mod}+8\cdot T)$ 。信仰一波就过了。
# [USACO13JAN]Seating G
> 有一排 $n$ 个座位，$m$ 次操作。
>
> A操作：将 $a$ 名客人安置到最左的连续 $a$ 个空位中，没有则不操作。
>
> L操作：$[a,b]$ 的客人离开。
>
> 求A操作的失败次数。
>
> $n,m,10^5$ 。
这…大概就是维护区间最长连续和然后再直接线段树上二分吧…发现自从领悟了线段树上二分之后，好多奇怪的线段树题也就都这么回事了…
# [UVA1620] Lazy Susan
> 现在有一个大转盘，上面有 $n$ 个珠子，分别写有 $1\sim n$ 之间的正整数。
>
> 给出这些珠子的排列方式，现在你可以每次翻转连续的四个珠子。问你至少要进行几次操作，才能将这个转盘上的珠子变成 $1,2,…,n-1,n$ 的排列方式。
>
> $4\leq n\leq 10^6$ 。
感觉还是比较有意思的题目？虽然是个结论题 233
首先考虑考虑序列中某段长度为 $x$ ，内部含有 $y$ 个逆序对的子段 $[l,r]$ 的性质：
(1) 该子段无论怎么重排，对 $[1,l-1]$ 的贡献不变，对 $[r+1,n]$ 的贡献不变。
(2) 该子段内部，顺序与逆序两种排布的逆序对数量之和为 $\frac{x^2+x}{2}$。
(3) 根据 $(1)$ 和 $(2)$ 可以得知，每次操作后，逆序对数量的变化量一定是 $(\frac{x^2+x}{2}-y)-y$ 。
回归到本题，可以知道每次逆序对的变化量肯定是 $6-2\cdot y$ 的形式。注意到序列翻转时，其他的指标都没有变，只有逆序对变了，所以可以用逆序对数量来衡量可达性。注意到每次增多/减少的数量都会是偶数，所以如果这个环不存在一个断裂使得逆序对数量为偶数，那么就不可以被变换成 $1,2,3,4\cdots n$ 。
这题原本的数据范围是 $10^3$ ，当然可以暴力枚举每个断裂。注意到，如果 $n$ 是奇数，且存在某个断裂的逆序对数也是奇数，那么这个环的所有断裂逆序对数都会是奇数。证明可以考虑，每次断裂的变化相当于把开头的元素移到结尾。那么假设当前开头元素是第 $k$ 大，那么可以知道这个元素会贡献 $n-k$ 个逆序对，移动到尾部后则会贡献 $k-1$ 个逆序对，$\Delta = k - 1 - n + k=2\cdot k - n - 1$ ，可知 $\Delta$ 本身一定是偶数。于是证毕，不可能出现偶数个逆序对的情况。
# [APIO2012]派遣
> 在这个帮派里，有一名忍者被称之为 Master。除了Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。
>
> 现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，你就不需要支付管理者的薪水。
>
> 你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。
>
> 写一个程序，给定每一个忍者 $i$ 的上级 $B_i$ ，薪水 $C_i$，领导力 $L_i$，以及支付给忍者们的薪水总预算 $M$ ，输出在预算内满足上述要求时顾客满意度的最大值。
>
> **简化版题面：给定一棵树，求**
> $$
> \max_{u\in T}\{L_u\cdot t_u\}
> $$
> **其中设** $s$ **是以** $u$ **为根的子树中的某个点集，**$\mathrm{card}$ **表示集合的元素个数， 则**
> $$
> t_u=\max_s\{\mathrm{card}(s)\cdot [ \sum_{i\in s} c_i\leq m]\}
> $$
>
> $1\leq n\leq 10^6$ 。
读题读半天系列x
…发现是暴力，暴力选每个点当根，然后拿一个支持快速合并的数据结构对子树内的点进行合并，选出重量最小的那几个即可。注意到暴力合并的话似乎是要二分…这样一般而言复杂度就变成两个 $\log$ 了。但是如果每次插入完之后，统计答案时选择不断删掉当前 $c_i$ 最大的元素，这样就可以在保证正确性的同时降低询问的复杂度。发现可以直接拿左偏树来维护。复杂度 $O(n\log n)$ 。
# [Luogu1858]多人背包
> 01背包的前 $k$ 优解。
>
> $k\le 50,m\le 5000,n\le 200$ .
考虑暴力做并不简单，一个直观的想法就是再记一维 $k$ ，即 $f_{i,v,k}$ 表示考虑了前 $i$ 个物品，总体积为 $v$ 的 $k$ 优解是多少。考虑转移。通过观察单调性，可以发现当 $p>q$ 时， $i-1,v$ 时的 $p$ 优解是不会对 $i,v+w_i$ 时的 $q$ 优解产生贡献的，也就是说对于一个状态 $f_{i,v,k}$ ，都是从某个 $f_{i-1,v,j}$ 或者 $f_{i-1,v-w_i,j}+v_i$ 转移过来的。于是考虑直接把这两个状态集归并排序一下即可。复杂度 $O(n\cdot m\cdot k)$ 。
# [SCOI2016]萌萌哒
> 一个长度为 $n$ 的大数，用 $s_1s_2s_3 \cdots s_n$表示，其中 $s_i$ 表示数的第 $i$ 位， $s_1$ 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$s_{l_1}s_{l_1+1}s_{l_1+2} \cdots s_{r_1}$与$s_{l_2}s_{l_2+1}s_{l_2+2} \cdots s_{r_2}$完全相同。
>
> 求本质不同的大数个数。
>
> $1\le n\le 10^5$，$1\le m\le 10^5$ 。
（以下默认并查集的复杂度是 $O(\log n)$ ，实际上这是一个很松的上界）
考虑暴力做当然是对每个位置开一个并查集，然后对于每个修改暴力 `for` 过去，这样最后答案就是 $9\cdot 10^{cnt-1}$ ，其中 $cnt$ 是不同的集合数量。这样做是 $O(nm\log n)$ 修改、$O(n\log n)$ 查询的。发现这样做的复杂度十分不平衡。考虑将复杂度向查询倾斜，即优化修改操作的复杂度。
考虑二进制拆分。对每个位置 $i$ 维护 $i\sim i+2^k-1$ 的连通状态，这样每次修改就是 $\log ^2n$ 的了。之后考虑对于一个长为 $2^k$ 的区间，可以push_down成两个长为 $2^{k-1}$ 的子区间再分别连边。于是查询的时候就可以直接查询了。
总复杂度 $O(m\log ^2n+n\log ^2 n)$ 。
#[SCOI2010]生成字符串
> lxhgww 最近接到了一个生成字符串的任务，任务需要他把 $n$ 个 $1$ 和 $m$ 个 $0$ 组成字符串，但是任务还要求在组成的字符串中，在任意的前 $k$ 个字符中，$1$ 的个数不能少于 $0$ 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
>
> $1\leq m,n\leq 10^6$ 。
这…理论上如果没有个数限制的话就是卡特兰数了吧。
考虑一个转化，从 $(0,0)$ 开始出发，设当前点为 $(x,y)$ 每次如果遇到 $1$ 就走到 $(x+1,y-1)$ ，每次遇到 $0$ 就走到 $(x+1,y+1)$，那么最终就是走到 $(n+m,m-n)$ 的、不跨过直线 $x=0$ 方案数。这…似乎是一个十分经典的组合问题了。大概就是考虑把走到 $y=1$ 这条直线以下的那些路径全都翻转到 $y=1$ 以下（做镜像对称），那么就可以看做是从 $(0,2)$ 走到 $(n+m,m-n)$ 的方案数。所以答案就是两者相减。
考虑怎么算这两部分。发现本质上从 $(0,0)$ 走到 $(n+m,m-n)$ 、每次向右下或者右上走的方案数。一种比较简单的理解就是从 $n+m$ 步里面选出 $n$ 步向右下走的方案数，所以答案是 $\binom{n+m}{m}-\binom{n+m}{m-1}$ ，因为从 $(0,2)$ 开始走相当于把其中向上走的某一步魔改成了成了向下走的，所以 $m$ 要减一。
# [SP19148]Kill them All
> $n$ 只怪兽，每一次可让 Digo 杀或 Sharry 杀。求在每杀掉一只怪物后，Digo 的击杀数都比 Sharry 的击杀数多的方案数。
>
> $1\leq n\leq 10^6$ 。
回顾历史的时候顺便发现了这道题…
大概就是上个题把 $\geq $ 换成了 $>$ 。考虑首先让 $1$ 号怪兽必须被 `Digo` 干掉，那么就变成了从 $(1,0)$ 出发，走 $n-1$ 步，途中不能碰到 $y=0$ 的方案数。考虑最后走到的地方只会是 $(n,\lceil\frac{n}{2}\rceil),(n,\lceil\frac{n}{2}\rceil+1)\cdots (n,n)$，那么不妨对这些东西分别计数，那么答案就是
$$
1+\sum_{i=1}^{\lceil\frac{n}{2}\rceil-1}\left(\binom{n-1}{i}-\binom{n-1}{i-1}\right)
$$
其中第一个 $1$ 是全部被 `Digo` 干掉的方案数。那么可以知道…这个式子里面前面的都被消掉了，最后只剩一个 $1+\binom{n-1}{\lceil\frac{n}{2}\rceil-1}-\binom{n-1}{0}=\binom{n-1}{\lceil\frac{n}{2}\rceil-1}$ 。 然后就没有然后了。
# [UVA11149]Power of Matrix
> 给定整数 $k$ 和一个 $n$ 阶矩阵 $A$ ，求
> $$
> A+A^2+A^3+A^4+\cdots+A^k
> $$
> $n\leq 100,k\leq 10^6$ 。
这题其实有两种做法。一种做法是 $O(n^3\log k)$ 的，另一种也是 $O(n^3\log k)$ 的，只不过会多一个 $8$ 的常数。
## Sol 1
考虑对着这个找规律（雾），大概是考虑分块做，发现原来的式子可以写成：
$$
A+A^2+A^3+\cdots +A^{\sqrt k}+A^{\sqrt k}\times (A+A^2+A^3+\cdots +A^{\sqrt k})+A^{2\cdot\sqrt k}\times (A+A^2+A^3+\cdots +A^{\sqrt k})\cdots
$$
那么就可以预处理再做了。这样复杂度是 $O(n^3\sqrt k)$ 的，好像大概是 $10^9$ 的复杂度…过不去。
不过既然分块可以，那倍增应该也可以。具体的，可以这么化：
$$
A^1+A^1\cdot A^1 + A^2\times (A^1+A^2)+A^4\times(A^1+A^2+A^3+A^4)
$$
那么这样就可以先预处理出 $n^3\log k$ 个 $A,A^2,A^4\cdots$ ，然后就可以再用 $n^3\log k$ 的时间预处理出 $s_1,s_2,s_4\cdots$ 其中 $s_i=\sum{A^i}$ 。之后就可以直接二进制拆分了。总复杂度 $n^3\log k$ 。
## Sol 2
考虑直接对所有矩阵的和进行递推。计 $A^u$ 为当前矩阵的 $u$ 次幂，那么不妨构造一个复合矩阵
$$
\begin{bmatrix} A^k\\ s_k \end{bmatrix}
$$
其中
$$
s_i = \sum \limits_{j = 1}^{i}A^i
$$
发现它可以这么转移：
$$
\begin{bmatrix} A^k\\ s_k \end{bmatrix} = \begin{bmatrix}A^{k-1}\\s_{k-1}\end{bmatrix}\cdot \begin{bmatrix}A &0\\I_n&I_n\end{bmatrix}
$$
其中 $I_n$ 表示 $n$ 阶单位矩阵。然后就没有然后了。注意到这样做矩阵其实是升阶了，所以会带一个常数。
# [SDOI2011]打地鼠
> 打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。
>
> 游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了，所以你改装了锤子，增加了锤子与地面的接触面积，使其每次可以击打一片区域。如果我们把地面看做 $m\times n$ 的方阵，其每个元素都代表一个地鼠洞，那么锤子可以覆盖 $r\times c$ 区域内的所有地鼠洞。但是改装后的锤子有一个缺点：每次挥舞锤子时，对于这的区域中的所有地洞，锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中，每个地洞必须至少有 $1$ 只地鼠，且如果某个地洞中地鼠的个数大于 $1$，那么这个地洞只会有 $1$ 只地鼠被打掉，因此每次挥舞锤子时，恰好有$r\times c$ 只地鼠被打掉。由于锤子的内部结构过于精密，因此在游戏过程中你不能旋转锤子（即不能互换 $r$ 和 $c$）。
>
> 你可以任意更改锤子的规格(即你可以任意规定 $r$ 和 $c$ 的大小)，但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后，再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠，至少需要挥舞锤子的次数。
>
> Hint：由于你可以把锤子的大小设置为 $1\times 1$，因此本题总是有解的。
>
> $1\leq m,n\leq 100$。
以下是翻车现场，这题根本没有「行列无关」的性质：
> 一道十分经典的行列无关技巧普及题目。但这题行列无？关比较的深刻。
> 考虑如果暴力枚举的话，复杂度大概是枚举 $r\times c$ 之后再一个一个打，这样复杂度是 $O(n^6)$，实现的好一点就可以 $O(n^4\log^2 n)$ 。但是，如果这题满足行列无关的话，就可以 $r$ 和 $c$ 分别枚举。准确来说，对于另一维设为 $1$，那么可以只去找这一维的最大值。考虑这么做判断的复杂度就是 $O(n^3)$，枚举的复杂度是 $O(n)$ 。那么最后总复杂度就是 $O(n^4)$ 。
> 那么唯一的问题在于如何证明行列无关在这题里面是对的。考虑对于所枚举的锤子大小所覆盖的某个区域，其中有两个点 $(a,b)$ 和 $(c,d)$ ，不同行也不同列，但是可以知道 $(a,b)$ 和 $(c,b)$ 的确定关系，$(c,d)$ 和 $(c,b)$ 的确定关系。即我断言，如果 $(a,b)$ 和 $(c,b)$ 满足同时合法，$(c,d)$ 和 $(c,b)$ 也同时合法，那么这三个点就可以同时合法，反之则不可以。
> 考虑这个断言为什么合理。发现每次如果以 $(c,b)$ 为量度去砸，那么 $(c,d)$ 和 $(a,b)$ 被砸的次数都只会与 $(c,b)$ 的地鼠数量有关，因为 $(c,b)$ 必须被精确砸完……
> ~~编不下去了，就当记结论了~~
然后就是一个二维差分，然后就没了。
# [Luogu1357]花园
> 小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1 \sim n$。花园 $1$ 和 $n$ 是相邻的。
>
> 他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则：任意相邻 $m$ 个花圃中都只有不超过 $k$ 个 C 形的花圃，其余花圃均为 P 形的花圃。
>
> 请帮小 L 求出符合规则的花园种数对 $10^9+7$ 取模的结果。
>
> $1\leq n\leq 10^{15},2\leq m\leq 5$。
发现一共只有两种方格，并且转移只跟 $m$ 有关，于是考虑状压。考虑 $g(s, t)$ 表示从状态 $s$ 转移到 $t$ 的方案数。其中转移指的是向右扩展一格。
那么显然这东西可以 `dfs` 预处理出来。然后发现这东西类似于 `floyd` 的转移矩阵，就可以快速幂了。考虑由于花圃是个环，那么合法的方案就是 $1...m$ 和 $n+1....n+m$ 要相同。所以就直接把开头结尾相同的累加一波即可。
```cpp
void dfs(int x, int u, int s){
if (x == m + 1){
ok[s] = 1 ;
ans.ma[s >> 1][s] = 1 ;
if (u == k && ~s & 1) return ;
ans.ma[(s >> 1)|st[m]][s] = 1 ; return ;
}
dfs(x + 1, u, s) ;
if (u >= k) return ;
dfs(x + 1, u + 1, s | st[x]) ;
}
int main(){
cin >> n >> m >> k ;
for (int i = 1 ; i <= m ; ++ i)
st[i] = (1 << i) >> 1 ;
dfs(1, 0, 0) ; ans = expow(ans, n) ;
for (int i = 0 ; i <= 1 << m ; ++ i)
if (ok[i]) add(res, 1ll * ans.ma[i][i], P) ;
cout << res << '\n' ; return 0 ;
}
```
# [UVA11134]Fabled Rooks
> 在一个 $n\times n$（$1\leq n\leq 5000$）的棋盘上放置 $n$ 个车，每个车都只能在给定的一个矩形( $x_{l_i},x_{r_i},y_{l_i},y_{r_i}$) 里放置，使其 $n$ 个车两两不在同一行和同一列，判断并给出解决方案。
一道(真正)考察了行列无关知识的题目。
考虑放每个车时行与列显然是无关的，所以就可以分开做。那就是给定一堆区间，每个区间内选一个点使之不被放在同一个位置。贪一波就完了。
# [NOI2005]瑰丽华尔兹
> 舞厅是一个 $N$ 行 $M$ 列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。
>
> 艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长，这样 1900 会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。
>
> $1\leq N$, $M \leq 200$，$K \leq 200$，$T\leq 40000$。K是时间段的数量，T 是总时间。
考虑最朴素的 $dp$ 就是 $f_{t,i,j}$ 表示时刻 $t$ 时在位置 $(i,j)$ 结尾的最长路径。转移时 $O(1)$ 的。但由于状态数太高导致不得不放弃。发现本质上每段时间内，转移的方向唯一。所以可以按段来 $dp$ ，$f_{k,i,j}$ 表示经过了 $k$ 段之后，结尾于位置 $(i,j)$ 的最长路径。这样状态数就是 $O(nmk)$ 的、转移是 $O(\max\{n,m\})$ 的了。发现由于每一段决策区间单调，且决策点彼此之间存在单调性，于是可以拿单调队列优化到均摊 $O(1)$ 转移。
# [BalticOI2008]Elect
> $n$ 个政党要组成一个联合内阁，每个党都有自己的席位数。
>
> 现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好。
>
> 对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的。
>
> 求最大席位并构造一组解。
>
> $1\leq n\leq 300,1\leq m\leq 10^5$ 。
大概是长个经验？
发现倒着贪心并不是对的…虽然观察数据范围发现 $O(nm)$ 可过，但是一般情况下很难想到要去背包，因为有一个「多余」的限制…
但是发现如果从大到小排完序之后再背包，当前加进去的东西一定是最小的。此时如果出现把这个东西拿出来，剩下的都一定比这个大。所以不难理解这么更新的正确性。
考虑如何记录方案。可以对于每种权值都开一个 `bitset`，对于每种权值，第一次更新的时候顺便更新 `bitset`（根据单调性这样一定是最合法的那个）。那么最后的复杂度就是 $O(nm+\frac{nm}{w})$。注意到这么写的意义在于，通过聚和分析可以得知，对于每个权值 $m$ 至多会与其他的价值 $or$ 一次，所以本质上是 $O(\frac{nm}{w})$ 而不是 $O(\frac{n^2m}{w})$（虽然也能过就是了）。
```cpp
int f[MAXM] ;
int half, sum ;
int i, v, ans, n ;
bitset <MAXN> b[MAXM] ;
pair<int,int> base[MAXN] ;
inline bool cmp(pair<int,int> a, pair<int,int> b){ return a.fr > b.fr ;}
int main(){
cin >> n ; f[0] = 1 ;
for(i = 1; i <= n ; i ++){
scanf("%d", &base[i].fr) ;
sum += base[i].fr, base[i].sc = i ;
}
sort(base + 1, base + n + 1, cmp) ; half = sum >> 1 ;
for(i = 1; i <= n ; i ++){
for (v = sum ; v >= base[i].fr ; v --){
if (!f[v] && f[v - base[i].fr])
b[v] = b[v - base[i].fr], b[v].set(base[i].sc), f[v] = 1 ;
if (v > half && f[v] && v - base[i].fr <= half) ans = max(ans, v) ;
}
}
cout << b[ans].count() << '\n' ;
for (int i = 1 ; i <= n ; ++ i)
if (b[ans][i]) cout << i << ' ' ;
}
```
# [LuoguP1531]鬼子进村
> 县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：
>
> 1. 若消息为 ```D x```：鬼子将 $x$ 号房子摧毁了，地道被堵上。
>
> 1. 若消息为 ```R``` ：村民们将鬼子上一个摧毁的房子修复了。
>
> 2. 若消息为 ```Q x```：有一名士兵被围堵在 $x$ 号房子中。
>
> 李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
>
> $1\leq n,m\leq 5\times 10^4$。
~~降智题，说实话我第一眼觉得那必然是 LCT；又觉得可达性不好统计，然后就懵了 1min~~
其实是有两种方法的：
## Sol 1
考虑暴力线段树维护，修复和拆毁都是单点修改。查询的话自然是查询一个点左边第一个 $0$ 的位置、右边第一个 $0$ 的位置。首先这显然是可以外层二分，内层区间查询来做到 $\log ^2$ 的（其实也可以不线段树维护，用分块技巧，$O(1)$ 查询区间和、 $O(\sqrt n)$ 单点加的分块，也可以通过本题，同时虽然插入删除都是 $O(\sqrt n)$ 的，但是询问变成了 $\log$ 的）；或者直接在线段树上二分，做到一个 $\log$ 。
## Sol 2
发下有一个性质并没有很好利用起来~~(虽然本身就是一个很没用的性质)~~。每次删除的点一定是之前插入的点。所以考虑对于所有炸毁的点维护一棵平衡树，以 $pos$ 作为键值，那么每次查询本质上就是询问前驱和后继。
……还有要注意可能本身就被炸了，判一下就好了。这种方法也是 $1$ 个 $\log$ 的。
# [AT3741] String Problem
> 给出两个字符串S和T. 通过执行以下操作，判断是否可以将字符串S转换为字符串T.
>
> - 操作 A：删除S中任意位置的字母 A .
> - 操作 B：在S的任意位置插入一个字母 B .
>
> S 和 T 的字符都为大写字母，并且 S 和 T 的长度 $\le 1000$ 。
……其实是水题，不过发生了一些奇妙的事情，然后就打算整理一下我的做法？感觉其他人的做法都一毛一样…
大概就是首先根据样例解释的提示，可以想出一个「先加 B 再删 A」的思路，然后发现前半部分就是一个魔改的 LCS，后半部分就只需要记录一下最少要用多少个 B，看看 s 比 t 多的那些字符是否全是 A 就好了。
# [Contest Hunter5105] Cookies
> 圣诞老人共有 $m$ 个饼干，准备全部分给 $n$ 个孩子。每个孩子有一个贪婪度，第 $i$ 个孩子的贪婪度为 $g_i$。如果有 $a_i$ 个孩子拿到的饼干数比第 $i$ 个孩子多，那么第 $i$ 个孩子会产生 $g_i\times a_i$ 的怨气。给定 $n$、$m$ 和序列 $g$，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
>
> $1≤n≤30, n≤m≤5000, 1\leq g_i\leq 10^7$。
首先不难想到要按照 $g_i$ 从大到小排个序，因为肯定要让 $g_i$ 大的人分到更多的饼干。之后设 $f_{i,j}$ 为前 $i$ 个人分了 $j$ 块饼干的最小怨气总和。发现并不好转移。因为要考虑有多少个人和 $i$ 获得的饼干数量相同。此时当然可以考虑多记一维，但是发现其实我们不关心饼干的具体数量，只关心彼此之间的相对关系。
考虑对于一个状态 $f_{i,j}$ ，如果让第 $i$ 个人只拿到 $1$ 个饼干，则考虑枚举前面有多少人同样拿了 $1$ 个饼干，此时有
$$
f_{i,j}=\min_{k=1}^i\{f_{i-k-1,j-k}+(i-k-1)\cdot \sum_{o=i-k}^ig_o\}
$$
注意到次数由于钦定了后 $k$ 个人都拿 $1$ 个饼干，所以前后就无关了，需要重新计算这 $k$ 个人的贡献。
如果让第 $i$ 个人拿到 $>1$ 块饼干，那么考虑由于不关心具体数量，所以这种情况等价于让所有人都少拿一块饼干，即 $f_{i,j}=f_{i,j-i}$ 。于是最后就对这两种情况取一个 $\min$ 即可。
# [UVA1621] Jumping Around
> 一条 $[0,n]$ 数轴，一开始在 $0$ 处。每次可以选择向左/右以步长为 $1/2/3$ 跳到对应位置，分别只能最多跳 $a,b,c$ 次，保证 $a+b+c=n,a>3,b>3,c>3$ 。求构造一种跳的方案，使得跳到 $1\sim n$ 每个位置恰好 $1$ 次。
>
> $1\leq n\leq 10^6$ 。
比较有趣的构造题吧…也是化归子问题的构造技巧。
考虑如果 $c=0$，如果此时 $a>1$ ，那么可以先不断向右以步长为 $1$ 走，直到 $a=1$，然后考虑以步长为 $2$ 向右跳，跳到不能继续跳的时候考虑向左或者向右用一个 $a$，之后再以步长为 $2$ 向左跳回来。可以知道这样一定是合法的。
如果 $c>0$ ，那么考虑化归到上一种情况。自然是想到，用完全部的 $c$ 跳到某个位置 $p$ 后，$1\sim p$ 都被覆盖了。这个地方有点神：
（1）如果 $3|c$，大概是考虑先用 $c/3$ 次跳到 $c$ ，然后向右用一个 $a$ ，再向左跳到 $1$ ，再向右用一个 $a$，再向右跳到 $c+2$ 。之后就变成了第一个问题。注意到由于 $a>3$，所以这种方法总是可行的。
（2）如果 $3|(c+1)$ ，考虑向右用一个 $a$ 转化到 $(1)$ 的情况。发现 $(1)$ 最多需要用到 $3$ 个 $1$ 且 $a>3$ ，这样做总是可行的。
（3）如果 $3|(c+2)$，考虑先向右一个 $c$ ，再向左一个 $b$，再向右一个 $a$。那么现在的 $c$ 的数量可以被 $3$ 整除。但是考虑由于(1)中的等价位置 $1$ 已经在第一次被跳了，所以最后一步要用 $b$ 。可以知道这样最多用 $2$ 个 $b$ ，也是合法的。
# [Luogu3795]钟式映射
> 设集合 $N=M=\left\{x|x\in N_+,x\leq k,k\in N_+\right\}$ 。设 $f$ 为 $N$ 到 $M$ 的映射。求满足 $f[f(x)]=x$ 的不同的映射 $f$ 的个数。
>
> $k\leq 10^{8}$ 。
说实话…我遇到这种题就会战术后仰然后不会…类似于什么置换啊、复合映射啊，我就蒙圈的很。
考虑新加入一个元素。对于一个 $x$，要么 $f(x)=x$，要么就会有一个 $y$ 和 $x$ 配对。所以有
$$
g_i=g_{i-1}+g_{i-2}\cdot (i-1)
$$
然后就递推即可。
感觉这个式子本质上和错排可能会有点类似。考虑一个 $n-$完全错位排列 的方案数。假设 $n$ 号元素排到了 $k$ 号位置上，$k$ 号元素恰好也排在了 $n$ 号位置上，那么就是 $(n-1)\cdot g_{n-2}$ ；否则 $k$ 号元素随便错排，那么就是 $(n-1)\cdot g_{n-1}$。那么就是
$$
g_{i}=(i - 1)\cdot(g_{n-1}+g_{n-2})
$$
感觉递推思想方面是有类似的吧…自己还是…太不聪明了啊
别找那些理由，就是泥萌的不努力！
# [UVA1451]Average
> 给定一个长度为 $n$ 的 $01$ 串，选一个长度至少为 $L$ 的连续子串，使得子串中数字的平均值最大。如果有多解，子串长度应尽量小；如果仍有多解，起点编号尽量小。序列中的字符编号为 $1$ ~ $n$，因此 $[1,n]$ 就是完整的字符串。
>
> $1\le n\le 100000,1\le L\le 1000$。
~~又到了复习斜率优化的时间了，斜率优化，常读常新。~~
考虑前缀和一下就转化成了对每个 $i$ 找到一个 $j<i$ 使得 $\frac{s_i-s_j}{i-j}$ 最大。发现这就是在求最大的斜率。考虑本质上 $x$ 坐标和 $y$ 坐标都是不降的，所以为了斜率单增，要维护一个下凸壳。于是拿一个单调栈维护斜率就好了。复杂度线性。
# [HNOI2008]玩具装箱
> P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
>
> P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。
>
> 为了方便整理，P教授要求：
>
> - 在一个一维容器中的玩具编号是连续的。
>
> - 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。
>
> 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望所有容器的总费用最小。
>
> 对于全部的测试点，$1 \leq n \leq 5 \times 10^4$，$1 \leq L \leq 10^7$，$1 \leq C_i \leq 10^7$
大概是斜率优化板板题？考虑方程：
$$
f_{i}=\min_{j=1}^{i-1}\{f_{j}+(i-j+s(i)-s(j)-L)^2\}
$$
然后考虑拆一下，并且令 $p(i)=s(i)+i,q(i)=s(i)+i+L$ ，那么：
$$
f_{i}=f_{j-1}+(p(i)-q(j))^2=f_{j-1}+p(i)^2-2\cdot p(i)\cdot q(j)+q(j)^2
$$
那么证明斜率优化可行的基本讨论就是找一个 $j$ 和一个 $k$ 来比大小：
若 $j>k$ 且 $j$ 比 $k$ 优，那么有
$$
\begin{aligned}
f_{j-1}-2\cdot p(i)\cdot q(j)+q(j)^2&<f_{k-1}-2\cdot p(i)\cdot q(k)+q(k)^2\\
2\cdot p(i)\cdot q(k)-2\cdot p(i)\cdot q(j)&<f_{k-1}-f_{j-1}+q(k)^2-q(j)^2
\end{aligned}
$$
设 $X_i=q(i),Y_i=f_{i-1}-q(i)^2$，那么有
$$
2\cdot p(i)>\frac{Y_{k}-Y_{j}}{X_{k}-X_{j}}
$$
也就说当这个式子满足的时候，存在 $j>k$ 且 $j$ 比 $k$ 优。
所以对此可以直接采用斜率优化。注意到 $X$ 单增的同时，斜率本身不降；同时据此可以知道应该维护一个上凸壳，所以可以直接取到队首进行转移的元素。复杂度线性。
# [HAOI2008]硬币购物
> 共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。
>
> 某人去商店买东西，去了 $n$ 次，对于每次购买，他带了 $d_i$ 枚 $i$ 种硬币，想购买 $s$ 的价值的东西。请问每次有多少种付款方法。
>
> $1 \leq c_i, d_i, s \leq 10^5$，$1 \leq n \leq 1000$。
比较常规的容斥题目。考虑由于硬币个数的限制，大概是要做一个多重背包计数，这样复杂度是 $O(4\cdot n\cdot s)$，大概是 $4e8$ 的级别，如果常数小的话没准信仰一波也是可以过的。
考虑更加正经一点的做法。发现虽然硬币个数很多，但是种类很少，同时发现不限制使用次数的方案数是很好计算的，于是考虑容斥。$f_v$ 表示不考虑硬币个数，用四种面值凑出 $v$ 的方案数。那么考虑如何统计不合法的方案数。考虑对于一种硬币 $(c_i,d_i)$，看上去，所有他的不合法方案应该是
$$
\sum_{j=d_i+1}^{+\infty} f_{s-c_i\cdot j}
$$
但是发现背包模型在计算方案时，状态本身具有简并性。 也就是对于任何一个状态 $f_{i,k}$ 都是被更小的 $f_{i,k-t\cdot c_i}$ 给拼插起来的。所以方案数应该为
$$
f_{s-c_i\cdot (d_i+1)}
$$
于是容斥一下即可。复杂度 $O(4\cdot s+16\cdot n)$ 。
# [CF933A]A Twisty Movement
> 给定一个序列 A，你可以翻转其中的一个区间内的数，求翻转后的序列的最长不下降子序列的长度。（$|A|\le 2000,1\le a_i \le 2$ ）
>
> $1\leq n\leq 10^3$。
自己想了一个暴力做法。大概是对于每个位置 $s$ ，可以比较方便地维护出 $s$ 之前以 $0/1$ 结尾的最长上升子序列，同时也可以维护出 $s$ 之后以 $0/1$ 开头结尾的最长上升子序列，这一部分不是那么直观，但是考虑对于一个位置 $p$ ，一定是有某个位置 $q>p$ 使得 $p+1\sim q$ 之间只选 $0$，$q+1\sim n$ 之间只选 $1$ 。这个东西倒着预处理似乎可以 $poly(\log)$ 或者线性，但是由于数据范围所以可以直接暴力。然后每次枚举两个端点暴力即可。中间可能要进行一下玄学的 dp。
……但其实是可以直接暴力 $dp$ 的。考虑最后选取的一定是一个形如 $1...2....1...2...$ 的子序列，于是就可以设状态 $f_{i,0/1/2/3/4}$ 表示分成了 $0/1/2/3/4$ 后的、形如这样的子序列。转移的话就是相邻状态转移即可。复杂度线性。
当然这题也存在一个闲的胃疼的高级做法，就是线段树上分别维护 $1 \rightarrow 1,1 \rightarrow 2,2 \rightarrow 1,2 \rightarrow 2$ 的最长上升子序列，然后暴力枚举每个区间，复杂度 $O(n^2\log n)$ 。
emmm 启发了一个 Idea 但是自己不会做，惨惨。
# [LuoguP6435] 「EZEC-1」数列
> 给你一个正整数 $n$，有数列 $\{a_n\}:1,2,3,...,n$。
>
> 分别求相邻两项中左边一项的 $a$ 倍与右边一项的 $b$ 倍的和再加上 $c$，得到一个有 $n-1$ 项的新数列：
>
> $1\times a+2\times b+c,2\times a+3\times b +c,...,(n-1)\times a+n\times b+c$。
>
> 对这个新数列重复上述操作得到若干数列，最后的数列只有一项，求最后这个项对 $p$ 取模的值。
>
> $1\le n\le 10^{18}$，$1\le p \le 10^{14}$，$1 \le a,b\le 10^9$，$0\le c \le 10^9$ 。
…比较有意思的题目？本质上数学题。
考虑直接递推。设 $f_k$ 表示经历完 $k$ 次操作之后的第一项。那么考虑最开始 $a_2-a_1$ 的值是 $1$ ，之后每次会变成原来的 $(a+b)$ 倍，那么也就是有：
$$
f_{i}=a\cdot f_{i-1}+b\cdot (f_{i-1}+(a+b)^{i-2})+c
$$
那么也就是
$$
f_i=(a+b)\cdot f_{i-1}+b\cdot(a+b)^{i-2}+c
$$
考虑高中数学技巧
$$
\frac{f_i}{(a+b)^i}=\frac{f_{i-1}}{(a+b)^{i-1}}+\frac{b}{(a+b)^2}+\frac{c}{(a+b)^i}
$$
那么可以通过差分得到
$$
f_i=(i-1)\cdot b\cdot (a+b)^{i-2}+(a+b)^{i-1}+c\cdot \sum_{j=0}^{i-2}(a+b)^j
$$
发现前面很好算，后面是一个等比数列的形式。由于不保证 $p$ 是素数，所以不能直接求逆元。于是考虑分治乘法。具体的，对于一个 $\sum_{i=1}^n(a+b)^i$ 可以这么算：
$$
\sum_{i=1}^n(a+b)^i=
\begin{cases}(a+b)^{\frac{n}{2}}\cdot \sum_{i=1}^{\frac{n}{2}}(a+b)^i+\sum_{i=1}^{\frac{n}{2}-1}(a+b)^i&\mathrm{if}~(n~\mathrm{is~even}) \\
(a+b)^{\lfloor \frac{n}{2}\rfloor }\cdot \sum_{i=1}^{\lfloor \frac{n}{2}\rfloor }(a+b)^i+\sum_{i=1}^{\lfloor \frac{n}{2}\rfloor -1}(a+b)^i + (a+b)^n &\mathrm{otherwise}\end{cases}
$$
然后就可以分治做下去了。复杂度 $\rm poly(\log )$ 。
# [UVA1611] Crane
> 输入 $n$ 个数，要求把它变成升序排列，每次操作都可以交换一个长度为偶数的区间的左右两半。要求操作数 $\leq 2n$ 。
>
> $n\leq 10^6$ 。
大概是一道降智题…
考虑一个逐步缩小问题规模的思想。元素从小到大考虑，每次把当前未考虑的数列中最小元素 $x$ 移动到他该在的位置 $x$。考虑 $pos_x-x$ 与$\frac{n-x+1}{2}$ 的大小关系，如果 $2\cdot(pos_x-x)+1\leq n-x+1 $，那么就可以直接对区间 $[x,2\cdot pos_x-x]$ 进行操作，否则要先对 $[x,pos_x]$ 进行操作使其不会越界，因为此时 $pos_x-x$ 的长度会缩短为原来的 $\frac{1}{2}$，而由于最长时 $pos_x-x=n-x$ ，所以可知这样一定不会越界。
# [LuoguP5007] DDOSvoid 的疑惑
> 给定一棵以 1 为根的有根树，定义树的一个毒瘤集为一个集合，并且集合中任意两个元素之间不存在祖先与后代关系。
>
> 定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和
>
> 要求给定树的所有毒瘤集的毒瘤指数之和，答案对 $10^8+7$ 取模。
>
> 但这个问题太难了，所以我们考虑化简。
>
> 因为点的编号跟它毒瘤指数密切相关，所以我们将会再给出一个整数 T，T = 1 表示 i 号点的毒瘤指数为 i，T = 0，表示所有点的毒瘤指数都是 1。
>
> $1\leq n\leq 10^6$ 。
懵了半天还是不会做……
不难发现这个可以以子树为状态来转移。然后考虑如何将孩子的贡献转移到根，发现需要处理的本质上是合并两棵树的所有毒瘤集。假设两棵树的毒瘤集权值和分别为 $F_1,F_2$，那么发现合并得到的 $F$ 应该至少为 $F_1+F_2$，并且还需要考虑两棵树对彼此的贡献。即将一棵树中的所有元素都分批合并进另一棵树的集合里产生的贡献。
那么不难知道要记录一下各自树中毒瘤集的个数。于是考虑从下向上 $dp$。设 $g_u$ 表示以 $u$ 为根的子树中毒瘤集的个数，$f_u$ 表示权值和。那么每次考虑将一棵新的子树 $v$ 并进来，所以有转移：
$$
g_u=g_v\times g_u+g_v+g_u
$$
$$
f_u=f_u\times g_v+f_v\times g_u+f_u+f_v
$$
复杂度 $O(n)$ 。
# [UVA1407 Caves](https://uva.onlinejudge.org/external/14/p1407.pdf)
> 给定一棵 $n$ 个节点、边带权的树。$q$ 次询问，每次给定一个 $x$ ，询问从根出发走多少个点，满足走过的边权和 $<x$ 且经过的点最多。点可以重复经过，但只会被计算一次。
>
> $n\leq 500,q\leq 10^5,x\leq 5\cdot 10^8$ 。
一个比较基础的思想是背包，但这时空显然不是背包能做的。这个地方考虑，点数只有 $500$，也就是至多只能走 $500$ 个点。于是就考虑把状态定义到点上，即 $f_{x,j}$ 表示以 $x$ 为根走了 $j$ 个不同的点的最小代价。注意到由于可以重复经过，所以多记一维 $0/1$ ，即 $f_{x,j,0/1}$ 表示以 $x$ 为根走了 $j$ 个不同的点，最终没回到/回到了 $i$ 的最小代价。考虑转移：
$$
\begin{aligned}
f_{x,j,1}&=\min_{y\in son(x),1\leq k\leq size(y)}\{f_{x,k,1}+f_{y,j-k,1}+w\times 2\} \\
f_{x,j,0}&=\min_{y\in son(x),1\leq k\leq size(y)}\{f_{x,k,1}+f_{y,j-k,0}+w,f_{x,k,0}+f_{y,j-k,1}+w\times 2\}
\end{aligned}
$$
其中第二个转移表达的是这条路径的终点是否在以 $y$ 为根的子树内。注意转移的时候要倒序枚举 $j$ ，保证当前转移不重复。
发现 $f_{root}$ 显然是单调的，于是回答询问时二分即可。复杂度 $O(n^2+q\log n)$ 。因为好像有证明，这种东西的复杂度是 $O(n^2)$ 的…
# [BZOJ4160 Exclusive Access 2](https://darkbzoj.tk/problem/4160)
> 给出 $n$ 个点 $m$ 条边的无向图，定向得到有向无环图，使得最长路最短。
>
> $1\leq n ≤ 15, 1\leq m ≤ 100$ .
大概是 $\rm dilworth$ 定理的应用，考虑 $\rm dilworth$ 定理：
> 令 $(X,≤)$ 是一个有限偏序集，并令 $m$ 是反链的最大长度。则 $X$ 可以被划分成 $m$ 个但不能再少的链。 即：链的最少划分数 $=$ 反链的最长长度.。
同时也存在对偶定理：
> 令 $(X,≤)$ 是一个有限偏序集，并令 $r$ 是其最长链的大小。则 $X$ 可以被划分成 $r$ 个但不能再少的反链。
也就是：
> **偏序集能划分成的最少的全序集个数等于最大反链的元素个数** 。
其中「全序集」指的是这样的一个偏序集 $(Y,\leq )$ ，改偏序集内部所有元素两两**均可比**。反链则指的是这样一个偏序集 $(Z,\leq )$ ，改偏序集内部所有元素两两均**不可比**。
换言之，假设给原图定向，那么根据 dilworth 定理，最长链的长度就是最小的独立集的大小，其中「独立集」的定义为原无向图中距离大于 $1$ 的两个点可以组成一个独立集(不考虑连通性)，因为只要两者没有边相连，两者的关系就是「不可比」。
于是这东西就可以状压了。$f_{s}$ 表示 $s$ 集合中最少有多少个独立集。这东西就可以先预处理一下每个 $s$ 是否是独立集，然后 $3^n$ 暴力 $dp$ 即可。
# [POJ3735 Training little cats](http://poj.org/problem?id=3735)
> 现在给你一个长度为 $n$ 的序列，开始这个序列都是 0。对这个序列一共有三种操作：
>
> 操作 1：输入一个 $x$，把 $x$ 位置上的值 $+1$ 。
>
> 操作 2：输入一个 $x$ 一个 $y$，交换 $x$，$y$ 位置上的值。
>
> 操作 3：输入一个 $x$，把 $x$ 位置上的值变成 $0$ 。
>
> 我们接着对这个序列进行 $k$ 次操作。
>
> 我们把这 $k$ 次操作叫做一轮，现在这个 $k$ 个操作进行了 $m$ 轮。
>
> 输出最后的序列。
>
> $1\leq n\leq 100,1\leq k\le 10^4,1\leq m\leq 10^9$ 。
…矩阵快速幂神题 sto
考虑一开始把这个空的序列记作一个 $n+1$ 维向量 $A:[1,0,0\cdots,0]$ 。其中第一维留空赋值为 $1$ ，$2\sim n+1$ 分别代表序列的第 $1\sim n$ 号元素。
那么考虑由于 $m$ 比较大，但是每次操作都是一样的，于是启发要用矩阵快速幂。
考虑三个操作，以下默认右乘转移矩阵 $T$ 、位置 $p,q$ 都是原序列右移一位的位置。
1、位置 $p$ 的数 $+1$ 。
考虑对于 $n+1$ 阶单位矩阵
$$
\begin{bmatrix}1&0&0&\cdots &0\\ 0&1&0&\cdots&0 \\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\end{bmatrix}
$$
考虑如何使得乘上这个矩阵的某个变形之后，位置 $p$ 实现 $+1$ 。考虑矩阵运算的本质是 $c_{i,j}=\sum_{k}a_{i,k}\cdot b_{k,j}$ ，那么 $A'_{1,p}=\sum _{i=1}^{n+1}A_{1,i}\cdot T_{i,p}$ ，因为 $A_{1,1}$ 恒定为 $1$ ，所以可知应该让 $T_{1,p}=1$ 实现 $+1$ 的功能。比如 $p=2$ ：
$$
\begin{bmatrix}1&0&1&\cdots &0\\ 0&1&0&\cdots&0 \\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\end{bmatrix}
$$
2、交换位置 $p,q$ 的数。
还是考虑 $n+1$ 阶单位矩阵。观察矩阵乘法本质，$A'_{1,q}=\sum_{i=1}^{n+1}A_{1,i}T_{i,q}$ ，那么一方面要让之前 $q$ 位置的数消失，一方面又要让 $A'_{1,q}=A_{1,p}$ ，于是应该让 $T_{q,q}=0,T_{p,q}=1$ 。 即如果 $p=1,q=2$ ，则应该是：
$$
\begin{bmatrix}1&0&0&\cdots &0\\ 0&0&1&\cdots&0 \\ 0&1&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\end{bmatrix}
$$
3、位置 $p$ 的数清零。
…$T_{p,p}=0$ 就好了。
注意到上面都是单独进行一个操作的情况。如果出现多个操作冗杂在一起，那么一方面可以建 $k$ 个转移矩阵，每次新的转移矩阵要乘上之前的矩阵，这样复杂度就是 $O(n^3k+n^3\log m)$ 。有点爆炸。
注意到可以把这 $k$ 次操作都放到一个转移矩阵里面，第 $2,3$ 操作就要相应发生改变，$2$ 操作就需要对换 $T$ 的 $p$ 列和 $q$ 列，$3$ 操作则需要把 $p$ 这一列全部清零。这样复杂度就是 $O(nk+n^3\log m)$ 了， 可以通过本题。
但其实 $n$ 可以出到 $2000$。注意到本题中最多只有 $O(n)$ 个不为零的位置。所以只需要对这些位置做矩阵乘法即可。复杂度变成了 $O(nk+n^2\log m)$ 。
哦，poj 上多组数据，那没事了（
# [UVA1437 String painter](https://www.luogu.com.cn/problem/UVA1437)
> 给定一个串 $s$ 和一个目标串 $t$。每次可以将 $s$ 的连续一段刷成一个同一个字符。求最少多少次操作使得 $s$ 变成 $t$ 。
>
> $1\leq |s|,|t|\leq 500$ 。
一开始的错误思路：考虑如果两个对应位置的字符相同，那么就可以把这对字符删掉不需要管，剩下的 $s$ 就可以看做空串。对这个进行 $dp$ ，$f_{i,j}$ 表示刷好了区间 $[i,j]$ 内字符的最小代价，每次转移考虑如果 $i$ 和 $j$ 相同就从 $f_{i+1,j}$ 或者 $f_{i,j-1}$ 转移过来之类的…反正很乱很乱很乱…
写了一发之后发现挂了。理了理思路，发现首先有个错误的点，即不一定「删掉不管」是最优的，可能相同的字符会先被覆盖然后再涂上。所以这个思路本来就是错的。之后再考虑，以 $1$ 为步长转移本身没有道理，因为转移时枚举一个子状态，要枚举一个可能存在的确定量。
所以设 $f_{i,j}$ 表示一个空串的 $[l,r]$ 刷成 $t[l...r]$ 的最少代价。转移时考虑枚举一个和 $l$ 或 $r$ 同色的端点 $k\in[l,r]$ 分成两个子问题即可。之后考虑如何把 $s$ 刷成 $t$ 。设 $g_i$ 表示 $s[1...i]$ 刷成 $t[1...i]$ 的最小代价。考虑比起一个空串，$s$ 中可能存在某些与 $t$ 对应相等的位置。这时只要 `chkmax(g[i], g[i - 1])` 即可。为了保证转移全面，直接枚举断点转移即可。
```cpp
for (int i = 1 ; i <= n ; ++ i) f[i][i] = 1 ;
for (int len = 1 ; len < n ; ++ len)
for (int i = 1 ; i <= n - len ; ++ i){
j = i + len ; f[i][j] = f[i][j - 1] + 1 ;
for (int k = i ; k <= j - 1 ; ++ k)
if (t[j] == t[k])
chkmin(f[i][j], f[k + 1][j - 1] + f[i][k]) ;
}
for (int i = 1 ; i <= n ; ++ i){
g[i] = f[1][i] ;
chkmin(g[i], s[i] == t[i] ? g[i - 1] : P) ;
for (int k = 1 ; k <= i ; ++ k)
chkmin(g[i], g[k - 1] + f[k][i]) ;
}
//为什么总是学不会？
```
#[UVA1427 Parade](https://www.luogu.com.cn/problem/UVA1427)
> 有一个由 $n+1$ 条横向路和 $m+1$ 条竖向路构成的网格图，每条横向路有一个高兴值和经过的时间。
>
> 现在想从网格的最下方走到最上方，求能得到的最大的高兴值是多少。
>
> 走路有限制：不能多次经过同样的路，也不会从下往上走。另外，在每条横向路上所花的时间不能超过 $k$ 。
>
> $1\leq n\leq 100,1\leq m\le 10^4$ 。
一开始想的是直接暴力 $dp$，枚举每一行的每个出发点(即从上一行转移过来的点)，考虑向左走一定是走一个包含当前点的最大子段和，向右也是。然后一开始觉得这个思路很有道理，但有点疑惑：我把 $n$ 和 $m$ 读反了，导致我以为这个做法是 $n^2m$ 没准可以卡过去的…后来发现是 $m^2n$ …虽然 $n^2m$ 也必定过不去就是了。
后来想了想，大概可以定义一个比较靠谱的状态。$f_{i,j}$ 表示到达了 $(i,j)$ 的最大高兴值。那么每次转移可以定向，从右边或者从左边。注意到由于存在 $k$ 的限制，决策区间具有单调性。所以可以用单调队列优化掉一个 $m$ 。
好像很简单的样子…但是不能一眼 A 就是罪过吧…
#[UVA11795 Mega Man's Mission](https://www.luogu.com.cn/problem/UVA1427)
> 洛克人最初只有一种武器 “Mega Buster”（这种武器可以消灭特定的一些机器人），你需要按照一定的顺序消灭 n 个其他机器人。每消灭一个机器人你将会得到他的武器（也可能没有得到武器），而这些武器可以消灭特定的机器人。你的任务是计算出消灭所有机器人的**顺序总数**。注意：一个机器人的武器可能可以消灭自己，但这对最终答案没有影响，因为必须先消灭这个机器人才能够得到他的武器。
>
> $1\leq n\leq 16$ 。
其实是很水的题…只是记录一个坑点。遇到这种求顺序总数的时候，我大脑总会选择性宕机…准确来说，显然这题是要预处理一个 $g_s$ 表示杀死 $s$ 中的怪物后可以获得那些武器。然后考虑 $f_s$ 表示杀死 $s$ 中的怪兽的顺序总数。对于 $f$ 的转移，我一开始是想的是要首先枚举每个元素，再去枚举这个元素第几个出现合法，但是这就需要再记一个其他元素的顺序，然后就爆炸了。
这也反映了自己并没有理解认真理解 $dp$ 子问题重叠的本质。考虑如何简化子问题。发现无论以什么顺序转移，最后一个加进去的元素是固定的(感性理解)。或者换句话说我们并不关心某个元素 $x$ 在集合内第几个出现，这些状态都可以合并到集合较小时 $x$ 最后一个加入的状态。所以只需要枚举最后一个元素+判断合法性即可。
菜成一坨，GGGGGGGGG。
# [UVA1625 Color Length](https://uva.onlinejudge.org/external/16/p1625.pdf)
> 输入两个长度分别是 $n$ 和 $m$ 的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。
>
> 记 $L(c)$ 为关于颜色 $c$ 和合并之后的排列的一个函数，定义如下：
> $$
> L(c)=\max_{p\in[1,n+m]\cap \mathbb{Z_+}}\{p~|~color(p)=c\} - \min_{p\in[1,n+m]\cap \mathbb{Z_+}}\{p~|~color(p)=c\}
> $$
> 你的任务是找一种合并方式，使得所有 $L(c)$ 的总和最小。
>
> $1\leq n,m\leq 5000$ 。
考虑朴素的状态当然是 $f_{i,j}$ 表示 $A$ 合并到位置 $i$，$B$ 合并到位置 $j$ 的最小总和…等下，似乎这东西并不可以很好的转移，因为考虑对于每个前驱状态，并不是很好记录每个颜色第一出现的位置，同时也不好维护最后出现的位置，根本没法转移。
考虑一个 trick，提前计算贡献。即虽然其余的都很麻烦，但是可以比较方便地知道有哪些颜色一定没有合并完。所以可以每次转移时，计算还没有合并完的贡献。这样做本质上是把贡献分摊到每个元素上面。因为考虑这种转移，对于每个终止状态，并不关心前面代价转移的形式，只关心代价转移的结果。
于是就预处理一个 $g_{i,j}$ 表示 $A$ 合并到位置 $i$，$B$ 合并到位置 $j$ 时有多少个字母还没有闭合。剩下的 $nm$ 转移即可。
# [UVA1218 Perfect Service](https://onlinejudge.org/external/12/p1218.pdf)
> 一个网络中有 $n$ 个节点，由 $n-1$ 条边连通，每个节点是服务器或者客户端。如果节点 $u$ 是客户端，就意味着 $u$ 所连接的所有点中有且仅有一台服务器。求最少要多少台服务器才能满足要求。
>
> $1\leq n\leq 10^6$ 。
这题比较水，主要是整理一下，给自己提个醒。如果设 $f_{x,0/1}$ 表示 $x$ 当根不选/选自己的话，注意到会出现 $f_{son_x,0}$ 没法转移到 $f_{x,1}$ 这种情况，因为不知道 $son_{son_x}$ 选没选。这种定义状态的方式就过于模糊。
于是考虑因为难以记儿子，所以记父亲。$f_{x,0/1/2}$ 分别表示「$x$ 和 $fa_x$ 都没选」、「$x$ 选了 $fa_x$ 不管(因为选不选都不引起冲突)」、「$x$ 没选 $fa_x$ 选了」，于是就是：
$$
\begin{aligned}
f_{x,0}&=\min_{y\in son(x)}\{f_{y,1}+\sum_{z\in son(x),z\not=y} f_{z,0}\}\\
f_{x,1}&=1+\sum_{y\in son(x)} \min\{f_{y,1}+f_{y,2}\} \\
f_{x,2}&=\sum_{y\in son(x)} f_{y,0}
\end{aligned}
$$
注意到，其中 $f_{x,1}$ 这个状态，本质上是两个状态的合并。可以考虑分裂成 $f_{x,3/4}$ 表示 $x$ 选了 $fa_x$ 选没选，发现被转移的时候，两者转移是一样的。所以就可以简并成一个状态。
# [UVA12099 The Bookcase](https://uva.onlinejudge.org/external/120/p12099.pdf)
> 有 $n$ 本书，每本书有一个高度 $h_i$ 和一个宽度 $w_i$。 现在要构建一个 $3$ 层的书架，你可以选择将 $n$ 本书放在书架的哪一层。设 $3$ 层高度(每层书的最大高度)之和为 $h$，书架总宽度为 $w$，要求 $h×w$ 尽量小。
>
> $3\le n\leq 70,1\leq h_i\leq 300,1\leq w_i\le 30$ 。
本质上是要最优化两样东西，宽度和高度。所以不妨让其中一个变得有序，所以考虑先按照 $h_i$ 把所有书降序排序。
考虑如何设计状态。发现如果某一层有最高的那本书，那么无论怎么放书，这一层的高度都不会再受影响；同时，把每一层的高度和宽度都记下来是没有必要的，于是可以记某一维为某个确切数值时另一维的最小值。具体的，$f_{i,j,k}$ 表示考虑了前 $i$ 本书，第二层的宽度为 $j$，第三层宽度为 $k$ 时，第二层、第三层的最小高度和。此处记宽度为状态是因为一方面高度和宽度是对称的，另一方面宽度的数据范围显然比高度要小。
考虑转移。首先应该定一个顺序，比如第二层高度应该大于第三层，那么此时转移有：
$$
f_{i,j,k}=\min\{f_{i-1,j,k}~,~f_{i-1,j-w_{i},k}+[j-w_i=0]\cdot h_i~,~f_{i-1,j,k-w_{i}}+[k-w_i=0]\cdot h_i\}
$$
其中第三个决策当且仅当第二层已经有了一本书。
考虑这样 $dp$ 的复杂度，似乎是 $O(n\cdot \left(\sum w_i\right)^2)$ ，有点爆炸。考虑如何剪枝：
1、$j+k\leq \sum_{t=1}^iw_t$ 。
2、$\sum_{t=1}^iw_t-j-k+30\geq j,j+30\geq k$。
其中第一可行性个比较好理解，第二个最优性剪枝是在说，因为 $\max\{w_i\}\leq 30$，所以如果高层的宽度比低层的宽度 $+30$ 还要大，那么不妨将几本书放到低层，可知这样放一定不会使结果更劣。
这么一波剪枝之后似乎就跑的飞快了…似乎是要滚一下第一维的样子。
大概转移and初始赋值这些会有一点细节的样子吧。
# [UVA10559 Blocks](https://uva.onlinejudge.org/external/105/p10559.pdf)
> 有 $n$ 个带有颜色的方块，没消除一段长度为 $x$ 的连续的相同颜色的方块可以得到 $x^2$ 的分数，让你用一种最优的顺序消除所有方块使得得分最多。
>
> $1\leq n\leq 200$ 。
大概是比较神仙的 $dp$ 了吧…
第一感觉肯定就是 $f_{l,r}$ 嘛，但是这么做的话本质上就变成贪心了，因为可能转移时，$f_{l,k}$ 和 $f_{k,r}$ 是消掉中间一部分，再合并起来的模式。注意到，对于一段 $i,j$，假设 $i<q<j$ 满足 $q\sim j$ 同色，$i<o<p<q$ 满足 $o\sim p$ 与 $q\sim j$ 同色，那么一种决策就是把这两段合并。但是注意到可能还会存在一个区间 $i<s<t<o$ 满足 $s\sim t$ 和 $o\sim p$ 同色。
于是这就启发(个鬼，这怎么可能想得出来)要多记一维状态 $d$，即 $f_{l,r,d}$ 表示 $l\sim r$ 的这段区间内，区间右侧还有 $d$ 个元素和 $r$ 同颜色时的最大得分。这样每次就以「和右端点颜色相同的颜色段」为子决策进行转移。那么需要枚举每次有多少个块和右端点一起删掉，在这基础枚举一个和右端点同色的、靠左的点进行转移，表示右端点所在的同色段暂时先不删，加入继续向左延伸的长同色段的一部分。
复杂度的话，状态是 $O(n^3)$ 的，然后我这种写法好像很迷幻，~~我觉得应该是 $n^5$ 但不知道为什么测出来极限数据(即所有颜色都相同)时运算量在 $n^4$ 量级~~ …剪枝是要剪的，每次只关心和 $r$ 同色的元素就好了。
好的，我又重新写了一下测了一下，觉得应该把访问记忆化结果也算 $1$ 次运算。发现 $100$ 个相同的颜色放在一起，这么写的运算量大概是 $258712510\approx2.6\cdot 10^8$，大概 $1s$ 内是可以跑出来结果的(uoj custom test 900ms左右)。$200$ 个颜色相同的就已经是紫荆花之恋那题跑不出来的程度了(即 $14s$ 以内跑不出来，只能本地测试)，似乎足足要 $1\min+$，大概是 $8136350020\approx8\cdot 10^9$ 的运算量~~中间可执行文件还一度被系统给 kill 掉了~~ 。
然后…然后我就加了一个好像很牛逼的剪枝，大概就是判断一下 $l\sim r$ 这一整段是不是同色，如果是的话就直接算完了返回即可。发现这样之后极端数据就应该是只有两种颜色然后左右交替这种，就可以在 $370\sim400ms$ 左右跑出来~~但似乎应该还是过不了，因为极限可以有15组数据，每组都这个速度肯定跑不进3s鸭~~。
然后发现这个某个区间是否同色可以预处理，然后就预处理了一下，发现一组快的话只需要 $320ms$ 左右了…
然后又改了一下，发现可以稍微贪一下，「枚举每次有多少个块和右端点一起转移走」显然是最大的那个快最好了。但这并没有快…
删了点重复计算和冗杂判断…发现大概是稳定在 $320ms$ 左右了…
…发现自己是个弟弟，如果要把右边和左边合并的话，那肯定是全都一起合并最优。所以现在大概是真正的 $O(n^4)$ 算法了？一组大概是 $200ms$ 左右了…人艰不拆。
```cpp
//版本1 最大点 400ms
bool check(int l, int r){
for (int i = r, j = lst[r] ; i >= l ; j = lst[j], i = lst[i])
if (i != j + 1) return 0 ; return 1 ;
}
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (check(l, r)) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;//剪枝 1
for (int i = r ; i >= l && base[i] == base[r] ; -- i){
chkmax(f[l][r][t], solve(l, i - 1, 0) + (t + r - i + 1) * (t + r - i + 1)) ;
for (int j = lst[i] ; j >= l ; j = lst[j])
if (base[j] == base[r])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, r - i + 1 + t)) ;
}
return f[l][r][t] ;
}
```
```cpp
//版本2 最大点 320- ms
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int i = r ; i >= g[r] ; -- i){
register int pq = t + r - i + 1 ;
for (int j = lst[i] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, pq)) ;
}
return f[l][r][t] ;
}
int main(){
cin >> T ; Q = T ;
while (T --){
n = qr() ;
memset(f, 0, sizeof(f)) ;
memset(buc, 0, sizeof(buc)) ;
memset(lst, 0, sizeof(lst)) ;
printf("Case %d: ", Q - T) ;
for (int i = 1 ; i <= n ; ++ i)
lst[i] = buc[base[i] = qr()], buc[base[i]] = i ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i ; j >= 1 ; -- j)
if (base[i] == base[j]) g[i] = j ; else break ;
cout << solve(1, n, 0) << '\n' ;
}
}
```
```cpp
//版本3 200- ms 左右 此时根本不需要判整段是否相同
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
//if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int j = lst[g[r]] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, g[r] - 1, 0) + solve(l, j, (t + r - g[r] + 1) )) ;
return f[l][r][t] ;
}
```
# [UVA1380 A Scheduling Problem](https://onlinejudge.org/external/13/p1380.pdf)
> 给定一棵树，pks把其中某些边改成了有向边。现在要求把所有边都改成有向边，求最长链的长度最小值。
>
> $1\leq n\leq 200$ 。
考虑首先，对于这种带方向性的计算链长，在树上一般都是要分成两部分做。于是不妨令 $f_i$ 表示从 $i$ 开始，到 $i$ 子树中的某个点结束的最长链，令 $g_i$ 表示到 $i$ 结束，起点是子树内某个点的最长链。然后开始分类讨论，设当前点为 $x$ ：
1、如果对于某个 $x$ ，该点与所有儿子的连边均为有向边，那么：
那么就是比较朴素的转移。
$$
f_{x}=1+\max_{y\in son(x)}\{f_{y}\cdot [\exists(x,y),x\to y]\}\\g_{x}=1+\max_{y\in son(x)}\{g_{y}\cdot [\exists(y,x),y\to x]\}\\
$$
2、如果存在某个 $y\in son(x)$ ，$(x,y)$ 是无向边，那么：
那自然是再分类讨论这条边重定向成 $x\to y$ 还是 $y\to x$ 。但…这样做毕竟是 $2^{\mathrm{count}(son(x))}$ 的，如果一棵树全都是无向边那人就没了。
考虑观察一点更深刻的性质。发现如果对于某个 $y$ ，被定向成了 $y\to x$ ，那么考虑对于其他 $g_z<g_y$ 的 $(x,z)$ 未定向的 $z\in son(x)$ ，一定是要定向成 $z\to x$ 的。原因是，定向成 $z\to x$ 对当前没有任何贡献，因为边不带权，且 $y$ 转移过来一定更优；同时 $z\to x$ 对另一边的 $f$ 的转移没有任何贡献。综上，这样做一定不会使得结果更劣。
那么就可以考虑，一开始用 `vector<int>` 将所有无向边连接的儿子给 `push_back` 进来。对于 $f$ 和 $g$ 分别处理。这个地方需要注意到题目中有个定理：
> 假如 $\rm G$ 是一棵树，那么需要的天数是 $k$ 或 $k+1$ 。$k$ 满足：$k$ 是 $\rm G$ 中所有链中一条链能包含的最多顶点数。
>
> 链的定义：在一条路径 $ P=(x_1, x_2, …, x_k)$中 ，对于任意的 $i=1,2,…,k-1$，总有一条从 $x_i$ 指向 $x_{i+1}$ 的有向边。
~~但其实这个定理也可以没有用。因为只需要在外层套一个二分就好了。~~·
这提示我们只关心最长链是否 $>k$，而不关心是否真的被最小化了。也就是说，我们致力于保证 $f$ 和 $g$ 是最优的，但是不用考虑 $f$ 和 $g$ 怎么合并——因为这个地方，可能会出现最优化 $g$ 和 $f$ 的时候，对于一条无向边被用了两次。但这并不重要，因为可能存在这么一个局面， $f_x$ 此时没有被最优化，$g_x$ 也没有被最优化，但是 $f_x+g_x\leq k$ 并且两者的决策不相交——这就可以保证至少在 $x$ 这里 $k$ 是合法的。那么就考虑在排完序扫两遍的过程中记录贡献即可。
注意一个问题，由于这个状态记录的不是子树的最大值(当然也可以多记一个这个)，所以如果中有以某点为根，路径长度 $>k$ 的，需要将这个信息向上传导。
```cpp
bool read_in(){
int u, v ; char w ;
res = cnt = ans = 0 ;
bool ret = 0 ; n = 0 ;
memset(fa, 0, sizeof(fa)) ;
memset(head, 0, sizeof(head)) ;
while (std :: cin >> u){
if (!u) return ret ;
ret = 1, n = std :: max(u, n) ;
while (scanf("%d%c", &v, &w) && v){
fa[v] = u ; n = std :: max(n, v) ;
if (w == 'd') add_e(u, v, 2), add_e(v, u, 1) ;
else if (w == 'u') add_e(u, v, 1), add_e(v, u, 2) ;
else add_e(u, v, 0), add_e(v, u, 0) ;
}
}
return ret ;
}
void dfs(int x, int fa, int len){
ans = std :: max(ans, len) ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && val(k) == 2) dfs(to(k), x, len + 1) ;
}
bool comp_f(const int & x, const int & y){ return f[x] < f[y] ; }
bool comp_g(const int & x, const int & y){ return g[x] < g[y] ; }
bool do_dp(int x, int fa){
// cout << x << '\n' ;
f[x] = g[x] = 0 ;
int F, G, df, dg ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) != fa){
if (!do_dp(to(k), x)) return 0 ;
if (!val(k)) son[x].p_b(to(k)) ;
else if (val(k) > 1)
f[x] = std :: max(f[x], f[to(k)] + 1) ;
else g[x] = std :: max(g[x], g[to(k)] + 1) ;
}
}
F = f[x] ; G = g[x] ;
if (son[x].empty()) return (bool)(F + G <= ans) ;
f[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_f) ;
for (int i = son[x].size() - 1 ; i >= 0 ; -- i)
suf[i] = std :: max(suf[i + 1], g[son[x][i]]) ;
// debug(suf, 0, n) ;
if (F + suf[0] + 1 <= ans) f[x] = F ;
for (int i = 0 ; i < son[x].size() ; ++ i){
dg = std :: max(G, suf[i + 1] + 1) ;
df = std :: max(F, f[son[x][i]] + 1) ;
if (df + dg <= ans) f[x] = std :: min(f[x], df) ;
}
g[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_g) ;
for (int i = son[x].size() - 1 ; i >= -1 ; -- i)
suf[i] = std :: max(suf[i + 1], f[son[x][i]]) ;
// debug(suf, 0, n) ;
if (G + suf[0] + 1 <= ans) g[x] = G ;
for (int i = 0 ; i < son[x].size() ; ++ i){
df = std :: max(F, suf[i + 1] + 1) ;
dg = std :: max(G, g[son[x][i]] + 1) ;
if(df + dg <= ans) g[x] = std :: min(g[x], dg) ;
}
// cout << x << " " << F << " " << G << " " << f[x] << " " << g[x] << '\n' ;
return (bool)(f[x] <= ans || g[x] <= ans) ;
}
int main(){
while (read_in()){
for (int i = 1 ; i <= n ; ++ i){
if (!fa[i]) root = i ;
dfs(i, 0, 0) ; son[i].clear() ;
}
// cout << ans << '\n' ;
/*
for (int i = 1 ; i <= cnt ; ++ i)
cout << to(i) << " " << val(i) << '\n' ;
*/
res = do_dp(root, 0) ; //return 0 ;
//cout << f[i] << " " << g[i] << '\n' ;
// for (int i = 1 ; i <= n ; ++ i)
// if (f[i] + g[i] > ans){ res = 1 ; break ; }
// cout << i << " " << f[i] << " " << g[i] << '\n' ;
cout << (res ? ans + 1 : ans + 2) << '\n' ;
}
return 0 ;
}
```
# [UVA12170 Easy Climb](https://uva.onlinejudge.org/external/121/p12170.pdf)
> 给出一堆山的高度 $h_i$ ，给定一个数 $d$ 。除了 $h_1,h_n$ 之外，可以任意修改山的高度，设改完之后山的高度是 $h'$，那么修改的代价是 $|h-h'|$ 。求使得任意两座相邻山峰的之间高度差得绝对值不超过 $d$ 的最小修改代价。
>
> $1\leq n\leq 100,0\leq h_i\leq 10^9$ 。
~~orz又是性质题，好烦啊怎么一直不会~~
考虑暴力怎么做。$f_{i,v}$ 表示把 $i$ 改成了 $v$ 后前 $i$ 座山彼此之间合法的最小代价和。你发现这个 $v$ 大概是没法直接转移的…
于是考虑一个深刻的性质。对于一个 $1<i<n$ ， $h_i$ 一定会被改成 $\max\{h_{i-1},h_{i+1}\}-d$ 或者 $\min\{h_{i-1},h_{i+1}\}+d$ 两者之一，如果一开始就满足性质就不用改，否则如果不满足就一定要去凑最近那个边界。类似的，考虑如果 $h_i '=h_{i+1}+d$ ，那么 $h_{i+1}'$ 就应该是关于 $h_{i}'$ 或者 $h_{i+2}$ 的一个带有常数个 $\mp d$ 的答案。那么这也就证明了，最终每座山都会变成某个 $h_p+q\cdot d$ 的形式，其中 $p\in [1,n]\cap\mathbb{Z_+}$，$q\in[-n,n]\cap\mathbb Z$ 。那么状态数就变成了 $O(n)\cdot O(n^2)=O(n^3)$ 个。考虑转移：
$$
f_{i,x}=|x-h_i|+\min\{f_{i-1,y}\} \quad (x-d\leq y\leq x+d)
$$
发现可以对 $x$ 这一维用单调队列。于是复杂度 $O(n^3)$ 。如果实现不精细可能会多一个 $\log$ 。注意到可以一开始把所有可能的 $x$ 值排序后存起来，这样就可以避免 `map` 或者 `set` 的滥用。
# [UVA1228 Integer Transmisson](https://uva.onlinejudge.org/external/12/p1228.pdf)
> 在一个仿真网络中传输一个 $n$ 比特的非负整数 $k$。各比特从左到右传输，第 $i$ 个比特的发送时刻为 $i$ 。每个比特的网络延迟总是为 $0\sim d$ 之间的整数(因此从左到右第 $i$ 个比特的到达时刻为 $i\sim i+d$ 之间)。若同时有多个比特到达，实际收到的顺序任意。
>
> 求实际收到的整数有多少种 ，以及它们的最小值和最大值。
>
> 例如，$n=3$，$d=1$，$k=2$ (二进制为`010`)实际收到的整数的二进制可能是 `001`(1)，`010`(2) 和 `100`(4)。
>
> $1\leq n\leq 64,0\leq d\leq n,0\leq k\leq 2^n $。
最小值和最大值都显然可以贪心。考虑求方案数。比较直接的想法就是设 $f_{i,j}$ 表示考虑前 $i$ 个 $0$ 和前 $j$ 个 $1$ 后，组成整数的方案数。但是转移并不知道要怎么转移，因为可能上一个 $0/1$ 的出现时间不确定，导致无法判定当前在整个数最右边插入 $0/1$ 是否合法。
然后就需要洞见一个比较深刻的性质了。考虑如果希望凑出某个数 $w$ ，那么对于任意时刻，最右边那位(指被收到的最右边那一位)必然可以**没有延迟** 。因为即使延迟了，结果也不会更优（即也不会存在没延迟拼不出来，只有延迟才能拼出来的情况）。证明的话比较简单，因为「若同时有多个比特到达，实际收到的顺序任意」，所以如果某个比特延后至 $>$ 最右边的数接收的时间，就可以调整成等于然后重排。
于是就可以知道，假设第 $i$ 位的发送时间是 $t_i$，那么考虑如何从 $f_{i,j}$ 转移到 $f_{i+1,j}$ 和 $f_{i,j+1}$ 。观察到本质上是要求插入一个新的 $1$ 或者新的 $0$ 。那么考虑假设第 $i+1$ 个 $0$ 的发送时间是 $t_0$ ，第 $j+1$ 个 $1$ 的发送时间是 $t_1$ ，那么如果为了让 $0$ 能够被尽早接收到，就需要满足 $t_0\leq t_1+d$ ，同理如果是想要 $1$ 能够尽量早到，就需要 $t_1\leq t_0+d$ 。于是转移时判断一下即可。复杂度 $O(n^2)$ 。
~~代码懒得写了~~
# [UVA1628 Pizza Delivery](https://onlinejudge.org/external/16/p1628.pdf)
> 你是一个披萨店的老板，有一天突然收到了 $n$ 个客户的订单。
>
> 你所在的小镇只有一条笔直的大街，其中位置 $0$ 是你的披萨店，第 $i$ 个客户所在的位置为 $p_i$，如果你选择给第 $i$ 个客户送餐，他将会支付你 $e_i-t_i$ 元。其中 $t_i$ 是你到达他家的时刻。
>
> 当然，如果你到的太晚，使得 $e_i-t_i<0$ 。你可以路过他家但是不能进去给他送餐，免得他反过来找你要钱。
>
> 最大化收益。
>
> $n \leq 100$ 。
考虑对于这种每秒代价递增的问题，一般都是代价提前计算。但是这题也不是最朴素的这类问题，因为存在可以放弃某些位置的情况。
然后就是比(我)较(又)神(不)仙(会)的状态设计环节。首先是，根据题面可知不用全部送餐，所以要把「准备送餐给ta」的人数 $k$ 放到状态里面。同时如果定义「选了某个区间内的全部数」作为状态，显然是不合适的。于是设 $f_{i,j,k,0/1}$ 表示**不考虑**区间 $[i,j]\cap\mathbb {Z_+}$ 内的元素，还要给 $k$ 个人送餐，当前位于 $i(0)$ 还是 $j(1)$ 的最小代价。那么最后答案就是
$$
\max_{k=0}^n\{\max_{i=1}^n\{f_{i,i,k-1,0/1}+(e_i-|p_i|)\times k\}\}
$$
考虑转移。发现对于一个 $f_{i,j,k,0/1}$ 而言，必然是由一个包含 $[i,j]$ 的更大的区间 $[l,r]$ 通过切分得来的，同时为了每次只转移走一个子问题，需要 $r=j$ 或者 $l=i$ 的更大区间。于是考虑每次只转移一个点，故转移为：
$$
f_{i,j,k,0}=\max_{l\leq i<j\leq r}\{f_{l,r,k - 1,0}+(v_l-k\times |p_l-p_i|),f_{l,r,k - 1,1}+(v_r-k\times |p_r-p_i|)\}\\f_{i,j,k,1}=\max_{l\leq i<j\leq r}\{f_{l,r,k - 1,0}+(v_l-k\times |p_l-p_j|),f_{l,r,k - 1,1}+(v_r-k\times |p_r-p_j|)\}
$$
然后就刷表就好了？
```cpp
for (int len = n - 1 ; len ; -- len)
for (int k = 0 ; k <= n - len ; ++ k)
for (int i = 1, j = i + len ; j <= n ; ++ i, ++ j){
//cout << i << " " << j << '\n' ;
for (int p = i + 1 ; p <= j ; ++ p){
chkmax(f[p][j][k + 1][0], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[p] - pos[i])) ;
chkmax(f[p][j][k + 1][1], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[j] - pos[i])) ;
}
for (int q = j - 1 ; q >= i ; -- q){
chkmax(f[i][q][k + 1][1], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[q])) ;
chkmax(f[i][q][k + 1][0], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[i])) ;
}
}
```
这东西看似是 $n^4$ 的，实际上跑得很快（
# [UVA12105 Bigger is Better](https://onlinejudge.org/external/121/p12105.pdf)
> 用不超过 $n$ 根火柴摆出一个尽量大的、能被 $m$ 整除的数。
>
> $1\leq n\leq 100,1\leq m\leq 3000$ 。
大概是个套路？遇到这种被 $m$ 整除余几的，大概需要在 $\bmod m$ 的余数之间来回转移。
然后可能是因为脑子抽了，一开始设计的状态是 $f_{i,j}$ 表示用了 $i$ 根火柴，模 $m$ 余 $j$ 时可以拼出来的最大的数，然后发现最多可以有 $50$ 位，但是 `__int128` 也只是大概 $36\cdot 10^{36}$ 多一点，不足以记下所有可行的的数字。
然后又尝试用 `string` ，写了一会儿才意识到 string 自定义的比较函数是按字典…~~当然也可以写一个大整数类，似乎最多只会带一个 50 的常数~~。
然后考虑这么设计不行，就只能去最小化贡献，然后手动构造了。考虑 $g_{i,j}$ 表示如果想要凑出从高到低的 $i$ 位，$\bmod m$ 余 $j$ 时最少需要用多少根火柴。转移和第一个转移…基本上差不多，刷就对了。然后考虑从第一位开始贪心地凑，注意判几次合法性就可以了。
```cpp
/*
int n, m ;
ll f[N][M], ans ;
int num[10] = {6, 2, 5, 5, 5, 5, 6, 3, 7, 6} ;
int main(){
while (cin >> n){
if (!n) return 0 ; ans = -1 ;
cin >> m ; memset(f, -1, sizeof(f)) ;
for (int i = 0 ; i <= 9 ; ++ i) f[i % m][num[i]] = i ;
for (int j = 2 ; j <= n ; ++ j){
for (int k = 0 ; k <= 9 ; ++ k){
for (int i = 0 ; i < m ; ++ i)
chkmax(f[((i * 10) + k) % m][j + num[k]], f[i][j] * 10 + k) ;
}
}
for (int i = 2 ; i <= n ; ++ i)
chkmax(ans, f[0][i]) ; cout << ans << '\n' ;
}
return 0 ;
}*/
int n, m, T ;
int pw[N], ans[N], f[N][M] ;
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6} ;
int main(){
while (cin >> n){
if (!n) return 0 ;
memset(f, 63, sizeof(f)) ;
int l = 1, r = n, mid, res = 0 ;
printf("Case %d: ", ++ T), cin >> m ;
memset(ans, 0, sizeof(ans)) ; f[0][0] = 0 ;
for (int i = 0 ; i <= n ; ++ i)
for (int j = 0 ; j < m ; ++ j)
if (f[i][j] != 0x3f3f3f3f)
for (int k = 0 ; k <= 9 ; ++ k)
chkmin(f[i + 1][(j * 10 + k) % m], f[i][j] + num[k]) ;
for (res = n + 1 ; f[res][0] > n ; -- res) ;
int p = 0, cost = n ; pw[1] = 1 ; //cout << res << '\n';
for (int i = 2 ; i <= res ; ++ i) pw[i] = pw[i - 1] * 10 % m ;
for (int i = 1 ; i <= res ; ++ i)
for (int j = 9 ; j >= 0 ; -- j){
int t = j * pw[res - i + 1] % m ;
if (num[j] + f[res - i][((m - p - t) % m + m) % m] <= cost){
cost -= num[j] ; (p += t) %= m ; ans[i] = j ; break ;
}
}
//cout << res << '\n' ;
int q = 1 ; while (!ans[q] && q < res) ++ q ;
for (int i = q ; i <= res ; ++ i) printf("%d", ans[i]) ;
if (!res) puts("-1") ; else puts("") ;
}
return 0 ;
}
```
注意几个细节：
1、最后数字的位数不具有可二分性，所以还是枚举吧。
2、注意可能存在前导 $0$ ，需要删掉。
# 总结
其实学到了许多吧？自己基础一点也不好，所以其实是把别人很早之前付出的努力，再重新付出了一遍。很遗憾，这些题目里面还是有不少无不太会做的题目…
感谢兔队的教导可以让我安心学下去：藏巧于拙，寓快于慢。只要努力，就一定会比昨天的我更优秀吧？
不过，努力和选择同样重要。希望在接下来越来越紧张的时间里面，我可以想清楚自己到底要做些什么题、要学习一些什么知识吧。加油吧！
# [UVA10891 Game of Sum](https://www.luogu.com.cn/problem/UVA10891)
> 有一个长度为 $n$ 的整数序列，两个游戏者 $A$ 和 $B$ 轮流取数，$A$ 先取。每次玩家只能从左端或者右端取任意数量的数，但不能两边都取。所有数都被取走视为游戏结束，然后统计每个人取走的数之和，作为各自的得分。两个人采取的策略都是让自己得分尽可能高，并且两个人都很机智，求 $A$ 得分 - $B$ 得分后的结果。
自己一开始想的 $dp$ 是要 $f_{i,j,0/1}$ ，并且转移有点复杂，结果发现根本不需要…考虑在博弈树上 dp，每个 $max$ 局面接下来一定是一个 $min$ 局面，所以有
$$
f_{i,j}=sum(i,j)-\min\{\min_{k\in[i+1,j]}\{f_{k,j}\},\min_{k\in[i,j-1]}\{f_{i,k}\}\}
$$
也就是找到与一端边界相邻，且最小的那个对方的决策（$min$ 局面）。发现前后缀 $min/max$ 维护一下就可以 $O(n^2)$ 了。
# [CF493D Vasya and Chess](https://www.luogu.com.cn/problem/CF493D)
> 有一个 $n\times n$ 的国际象棋棋盘。将白后放在 $(1,1)$ ，黑后放在 $(1,n)$ ，其余位置全都是中立的卒。
> 双方交替移动。白方先手。 每次移动，后（Queen）可以朝八个方向（上下左右对角线）之一移动任意格，直到碰到另外一个棋子，然后吃掉这个棋子。注意，在本题中，每次移动必须吃掉一个棋子。
> 当你的皇后被吃了或者你没有棋子可以吃了，就输了。 给出棋盘大小，请问哪方会赢。
~~发现这种对称位置决策的…一般后手都比较神必，拖，就硬拖。~~
考虑后手模仿先手的动作，那么如果两者之前相隔为奇数，后手可以模仿先手，发现这么做一定可以吃掉先手。如果相隔为偶数，那先手就要学聪明，移动到 $(1,2)$ ，然后成为上一种情况的后手…
# [UVA1099 Sharing Chocolate](https://www.luogu.com.cn/problem/UVA1099)
> 给出一块长为 $x$, 宽为 $y$ 的矩形巧克力，每次操作可以沿一条直线把一块巧克力切割成两块长宽均为整数的巧克力（一次不能同时切割多块巧克力）。
>
> 问：是否可以经过若干次操作得到 $n$ 块面积分别为 $a_1, a_2, ..., a_n$ 的巧克力。
>
> $n\leq 15,1\leq x,y\leq 100$ 。
大力状压，$f_{s,x,y}$ 表示 $s$ 这个集合内的巧克力是否可以被 $x,y$ 给切出来。考虑这样转移存在问题。因为必须要枚举子集来转移，所以最后时间复杂度 $O(3^nxy)$，空间复杂度 $O(2^nxy)$ 。有点爆炸。
考虑化简状态。发现固定了巧克力集合 $s$ ，那么对于一个固定的 $x$ ，$y$ 要么不存在要么同样被固定。所以状态就可以简化成 $f_{s,\min\{x,y\}}$ 。转移时依旧要判断两个状态是否都可行。注意转移来的状态 $f_{s',x'}$ 也需要保证信息是落在较短边上的。复杂度 $O(x3^n)$。
神必 uva 卡我常数。不过也需要记得，对于这种信息 $01$ 且求并的转移，一旦某个状态确定为 $1$ 了就可以 `break`。这个技巧确实要记住。
# [LA4725 Airport](https://www.luogu.com.cn/problem/UVA1450)
> 机场上有两个跑道，分别为 W 和 E，每个时刻 $i$，W和E都分别有 $a_i,b_i$ 架飞机进入跑道。每个跑道的飞机都按顺序从 0 开始排序，每个时刻都允许一架飞机起飞，现要求你安排起飞的飞机，使得任意时刻的飞机的最大编号最小。
>
> $1\leq n\leq 5000$ 。
这题能比较自然地想到要二分。但是问题在于二分了之后并不知道要怎么去 check。这个地方有个很妙的 idea。就是如果之前有机会要飞，可以不飞，等到什么时候攒到了 $mid$ 号再飞。这样就不需要再考虑这东西的后效性了。但是有一点需要注意，就是攒着一起飞的话，在第 $i$ 个时刻只能选择飞之前的，因为这个决策本质上等价于在 $i-1$ 时刻飞。所以也要分别统计 $W$ 和 $E$ 的可飞量。
# [LA4094 Wonder Team](https://vjudge.net/problem/UVALive-4094)
> There are $n$ football teams participating in the competitions, each team plays twice (home and away) against each other team. Each team receives three points for a win and one point for a draw. No point is awarded for a loss.
>
> When the games are finished, teams are ranked by numbers from $1$ to $n$ according to the total points. The rank of each team $t$ having $p$ points is one plus the number of teams having more than $p$ points. It is possible that more than one team have the same ranks. In addition to the Champion (the first ranked team or teams), the **Wonder Team** is also awarded, if there exists one. The team that has absolutely **the highest number of wins** (absolutely means no other teams has the same number of wins), absolutely **the highest number of goals scored**, and absolutely **the lowest number of goals **conceded, is called the WonderTeam. (WonderTeam should have all these properties.)
>
> Your task is to find out the worst possible rank for the **Wonder Team**.
>
> $1\leq n\leq 50$ 。
English problem, English solution!
First of all, I'd like to claim that the 2nd Constraint and 3rd Constraint is no-use, becauce we always can let WT won another team with $10^9:1$.
Let's assume $a_1,b_1$ means the WonderTeam's wins and draws, $a_2,b_2$ means an arbitrary team's wins and draws, whose rank is higher than WT. After a series of easy inference, if one team has higher rank than WT, the equation below should be satisfied:
$$
b_2-b_1>3(a_1-a_2)\qquad (1)
$$
~~Then my train of thought ended up with this:(~~
Thinking more carefully, if we want to maxmize WT's rank, we have to get other teams' score as high as we can. So we can use a greedy way to construct it : Just let WT's wins actually one more than others. At the same time let WT lose its other games. Also we let other teams won WT one time, and draw with each other.
Then we can find that $\forall a_2$ ，there is $a_1-a_2=1$, which means $(1)$ turned to be:
$$
b_2-b_1>3
$$
And about $b_2$ , there will exists two teams who losed in the game with WT , which means the-two has exactly $1$ win and $2n-4$ draws, while the rest teams has exactly $1$ win and $2n-3$ draws.
So we can cliam that when $n>4$ , WT's lowest rank can be $n$ ; when $n=4$, it can be $2$ ; otherwise it can only be $1$ 。
# CCO 2017 Rainfall Capture
> Lucy 有 $n$ 个高度为 $h_1,h_2,...,h_n$ 的柱子。她想知道，在所有可能的摆放方案中，所有可能的雨滴量（以 $r$ 为单位）是多少。
>
> 柱子只能竖着摆。接雨滴的定义：满则溢。
比较神仙的 dp，对着代码啃了很久…
考虑直接求雨滴量并不好求，因为要去考虑左右两边的柱子高度。考虑对于一个排布 $4,2,5$ ，那么中间 $=2$ 或者 $=1$ 时要分开考虑；但是我们发现无论怎样，中间在接完雨滴之后高度都会变成 $4$ ，所以考虑求**所有可能的雨滴+柱子**的体积和。由于每个柱子都要摆，所以最后只需要去 check 那些 $\sum h_i\sim max$ 的答案。
考虑定义 $f_{i,v}$ 表示用了 $i$ 个柱子之后能否凑出体积 $v$ 来。考虑一个比较常用的 trick，将所有 $h_i$ 从小到大排序之后，按顺序转移。这样就能保证每次加进来的柱子都是当前最高的(无中生有了一个很有用的性质)。考虑一个状态 $f_{i,v}$ ，他的转移应该为：
$$
f_{i,v}=\bigcup_{p_j\leq v} f_{i-1,v-p_j}
$$
其中 $p_j$ 是每个柱子的高度，需要从小到大转移，且转移时需要严格按照先枚举 $p_j$ 再枚举 $1\sim i$ 的顺序。
考虑这个式子的意义。对于任何一个大小为 $i\in[1,n-1]\cap\mathbb{Z_+} $ 的柱子集合 $o$，按秩转移时每次加入一个 $\geq \max_{t\in o}p_t$ 的新柱子 $p'$，放在最左边（或者最右边），同时再加入一个按高度从小到大排序后，恰好排名比 $p'$ 大 $1$ 的柱子 $p''$ 放在 $p'$ 的同侧（即，如果 $p'$ 放在了整个序列的左边，$p''$ 应该被放在 $p'$ 的左边）。那么此时考虑，每当加进来一个元素 $p_0$，集合大小从 $i-1$ 变成 $i$ ，$p'$ 就向右交换一个，这样新加进来的这个柱子上方水位高度一定会是 $p'$ 的高度（因为最左边有 $p''$）， 所以体积的变化量是 $\Delta v=(p'-p_0)+p_0$，前一半是水，后一半是新的柱子，所以可以从 $i-1,v-p'$ 转移过来。
需要注意的是，这样转移一定是不包含最高那个柱子的，因为当最高的柱子为 $p'$ 不存在一个更高的 $p''$ 。
于是最后复杂度 $O(n^2\sum h)$ ，当然可以用 bitset 优化成 $O(\frac{n^2\sum h}{w})$ 。但其实在注意到本题只关注可达性判断之后，就可以发现等高的柱子不用重复转移，就可以优化成 $O((\sum h)\cdot n\cdot \max\{h\})$ 。
```cpp
int s ;
int n, m ;
int base[N] ;
//bool f[N][M] ;
bitset <M> f[N] ;
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), m = max(m, base[i]) ;
sort(base + 1, base + n + 1) ;
for (int i = 1 ; i < n ; ++ i)
s += base[i] ; f[0][0] = 1 ;
for (int i = 1 ; i < n ; ++ i){
for (int j = 1 ; j <= i ; ++ j)
f[j] |= (f[j - 1] << base[i]) ;
//for (int k = base[i] ; k <= n * m ; ++ k)
// f[j][k] |= f[j - 1][k - base[i]] ;
}
for (int i = s ; i <= n * m ; ++ i)
if (f[n - 1][i]) printf("%d ", i - s) ; return 0 ;
}
```
# [UVA1073 Glenbow Museum](https://www.luogu.com.cn/problem/UVA1073)
> 对于一个各边长度任意且都平行于坐标轴的多边形，我们可以用这样的方式描述它：考虑它的每一个内角，如果这个内角为 $90$ 度，那么用 $R$ 代表它；如果这个内角为 $270$ 度，那么用 $O$ 代表它。从某个点开始，按照逆时针的顺序读取 $R$ 和 $O$，最后得到一个由 $O,R$ 组成的字符串。
>
> 给定整数 $n$，问有多少个长度为 $n$ 的 $O,R$ 组成的字符串，使得有一个或以上与之对应的多边形，满足这个多边形内部有一点，可以看到这个多边形的所有内角（即，这个点与多边形所有内角顶点的连线都不与多边形的边相交）。
显然最后一定是 $\frac{n}{2}-2$ 个 $O$ 和 $\frac{n}{2}+2$ 个 $R$。同时显然不会有相邻的 $O$，证明大概是需要拐回来之类的。那么问题就是给你固定数量的 R 和 O ，O 和 O 之间不相邻的方案数。
第一种 $dp$ 就是 $f_{k_1,k_2,l,r}$ 表示用了 $k_1$ 个 O 和 $k_2$ 个 R，最左端的字母是 $l$，最右端是 $r$ 的方案数。转移的时候考虑新加入一个 $R$ 还是 $O$ 即可。
第二种 $dp$ 则是一个改进，因为显然我们不关心 $O$ 的数量，因为最后是一定的；只关心如何排列。所以令 $f_{k_1,k_2,c}$ 表示有 $k_1$ 个 R ，$k_2$ 对相邻的 RR，第一个字母是 $c$ 的方案数。转移的时候考虑向后加一个 R 还是 OR 即可 。
然而显然这种 dp 是有组合意义的。所以我们分类讨论：
1、尾部不是 O 的方案数，显然就是前面 $\frac{n}{2}+2$ 个空填 $\frac{n}{2}-2$ 个O的方案数。
2、尾部是 O 的方案数，此时第一个位置不能放 O。类似的组合一下就完了。
于是就可以组合数做。处理的时候因为答案过大，所以可以考虑取对数~~（学到许多）~~。
# [CF340E Iahub & Permutations](https://www.luogu.com.cn/problem/CF340E)
> 有一个长度为 $n$ 的排列 $a$，其中有一些位置被替换成了 `-1`。你需要尝试恢复这个排列，将 `-1` 替换回数字。
> 求多少种可行方案使得得到的是一个排列且不存在 $a_i=i$ 的位置。
>
> $n\leq 5000$ 。
orz 一个十分巧妙的转化，大概就是对于这种带有**放置限制**的排列问题，比如某个下标不能放置某个数，那么可以将这个排列对应到一个 $n$ 阶摆 $rook$ （即 $n\times n$ 的棋盘上放 $n$ 个互不攻击的车）问题上。这样一方面可以把「位置 x 不能放 y」约束展开，抽象成一个二维约束点 $(x,y)$ 上不能放车的约束；另一方面可以知道这个对应一定是完备的。
那么就转化成了，有些行和列已经放了车，整个棋盘对角线不能放车，有多少种本质不同的放车方案数。首先可以发现，如果某行某列有车，这一行一列就可以删掉；同时如果对于某个 $-1$ ，他所在的这个位置对应的行/列恰好被删了（同时存在位于下标 $k$ 的 $-1$ 和一个 $pos$ 使得 $a_{pos}=k$ ），那么对于这个 $-1$ 而言就没有限制了。
这样考虑 $dp$ 。$f_{i,j}$ 表示 $i\times i$ 的方格里考虑 $j$ 个限制的方案数。那么 $f_{i,0}=i!$。同时注意到 $f_{i,j-1}$ 到 $f_{i,j}$ 恰好多了一个限制，这个限制对应的应该是 $f_{i-1,j-1}$ 的方案数。所以有转移
$$
f_{i,j}=f_{i,j-1}-f_{i-1,j-1}
$$
复杂度 $n^2$ 。
# CF212D Cutting Fence
> 给出 $a[1...n]$ 。
> 定义 $f$ ：
> $$
> f(i,k)=\min_{i\leq j\leq i+k-1}\{a[j]\}
> $$
> 之后有 $m$ 个询问，每个询问给出一个数 $k$，问所有 $f(j,k) (1\leq j\leq n-k+1)$ 的平均值。
> $1\leq n,m\leq 10^6$.
首先不难知道要求出每个 $a_i$ 对包含其区间的贡献，然后对于长度为 $1\sim n$ 的区间分别计算其和，最终除以 $n-k+1$ 即为答案。
考虑两遍单调栈求出每个元素 $x$ 左/右边第一个比他小的元素下标 $l,r$，可知 $x$ 的贡献区间即为 $[l+1,r-1]$。枚举 $x$ ，那么区间 $l+1,r-1$ 的所有跨过 $x$ 的子区间都会存在贡献。此处假设 $x-l<r-x$，考虑分类讨论子区间长度 $L$ ：
1、 $1\leq L\leq x-l$ ，这种区间每个元素都可以是 $x$ ，所以贡献为 $L\cdot a_x$ 。
2、$x-l+1\leq L\leq r-x$ ，这种区间最多只能取到 $x-l$ 次 $x$ ，所以贡献为 $(x-l)\cdot a_x$ 。
3、$r-x+1\leq L\leq r-l-1$ ，这种区间最多只能取到 $r-l-L$ 次，故贡献为 $(r-l-L)\cdot a_x$ 。
然后观察这些修改，发现 $L\cdot a_x$ 这东西，对于一个区间是在加一个等差数列的形式，$(x-l)\cdot a_x$ 和 $(r-l)\cdot a_x$ 都是区间加一个常数的形式。于是可以维护二阶差分。复杂度线性。
# [USACO12 Bovine Alliance G](https://www.luogu.com.cn/problem/P3043)
> ~~给出 $n$ 个点 $m$ 条边的图，现把点和边分组，每条边只能和相邻两点之一分在一组，点可以单独一组，问分组方案数~~.
>
> 以上是错误的题意，以下是正确的题意：
>
> > 题意是给每条边找一个配对的点，要求边 $(u,v)$ 配对的点是 $u$ 或 $v$ ，且每个点最多只能被一条边配对，求不同方案数。
>
> $1\leq m\leq n\leq 10^5$ 。
对着错误的题意思考了半天也不会…觉得首先对于点分组可以直接跑一个第二类斯特林数，但是这样边就没法分配了，因为可能存在边的两个端点在同一个点集内，所以可能需要套一个容斥什么的。推容斥系数可能会很高妙~~反正我不会~~。
然后正确的题面的话，考虑问题可以转化成给每条边定向，使得最后整张图每个点的度数都 $\leq 1$ 的方案数。然后…然后就是考察对于图论模型的洞见性有多强了：
1、不难发现一个简单环的定向方式总共是 $2$ 。
2、考虑去计算一棵树的定向方式。发现随便找一个根，显然哪个点当根对于整棵树的方案数没有影响。考虑如果将所有边都向儿子定向，那么这样一定合法，这是第一种方案。同时，单独把某一条边取反，假设这条边连接的儿子是 $x$ ，那么同时需要把 $x\to fa_x,fa_x\to fa_{fa_x}, fa_{fa_x}\to fa_{fa_{fa_x}}$ 全部取反，那么最终会取反到根，根的入度会变成 $1$ ，这也就说明不能有 $>1$ 条边同时取反。所以可以知道一棵树的定向方式为 $1+(n-1)=n$ 。
发现对于无向图，本质上就是树插环的形态。所以拿一个带权并查集维护即可。有一个坑点，就是如果两个点不在同一个即集合里，边数也要++。