题解合集

powerlessness · 2020-02-27 23:15:05 · 个人记录

[P1] CF1239C / CF1248E [*2300]

模拟。

首先我们把所有人以 t_i 为第一关键字、i 为第二关键字进行升序排序。

显然，根据潜规则，排队的人的编号是单调递减的。我们用一个队列存正在排队的人，然后再用一个小根堆来存正在座位上暗中观察的人。

如果队列里没人，那么把排序后的人里面最靠前的入队。设队头打完水的时间为 L。

然后我们依次枚举 t_i\le L 的每个人。

如果队列里最后一个人比他的编号大，那么这个人可以入队。（排队的人的编号单调递减）

否则这个人因为潜规则，只能暗中观察。

最后我们把队头的答案更新，然后 pop 掉。如果队列空了，那么让暗中观察的人里面编号最小的入队。

[P1] CF1251E2 [*2300]

并不是独立做出来的……

首先观察到一点：如果对于某个 m_i，有 \sum_j[m_j<m_i]<m_i，那么通过收买比 m_i 小的人不可能让它投票。

而且还有这么一条性质：如果有一个人免费给我投票，那么 m_i 比他小的都会给我投票。

那么从小到大贪心的策略不可行，也就是说我们必须「从大到小」地收买（并不是严格从大到小）。

考虑从大到小贪心，预处理 pre_x=\sum_i[m_i\le x]，令 cnt 为已经收买的人数。如果对于某个 m_i，pre_{m_i-1}+cnt<m_i，那么我们需要在 \ge m_i 的人里收买 m_i-pre_{m_i-1}-cnt 个人。

感性理解即可证明，不能通过收买第 i 个人来降低成本。

所以开个小根堆维护 \{p_j\mid m_j\ge m_i\} 即可。

[P1] CF1251D [*1800]

卡我常数，差评……

显然，左端点的中位数和右端点的中位数，所形成的闭区间内的数，一定都是合法的。且显然不在这个区间内的数一定不合法。

显然这个具有单调性，于是考虑二分。

check 的时候，把所有右端点 <mid 的和左端点 >mid 的先判掉，然后贪心即可。

[P1] CF1252K [*2200]

为什么这题有 2200。。。

线段树维护矩阵乘积，记得同时维护原串和反串的答案，然后 pushdown 的时候 swap 一下。

[P1] CF1252H [*1900]

屑题卡精度……

首先注意到任何一个矩形都可以被分成两个相等的小矩形，于是答案一定 \ge\max_i\{a_i\cdot b_i\}。

然后考虑选择两个不同矩形的情况。

对于任何两个矩形 i,j，答案会等于 \max(\min(a_i,a_j)\cdot\min(b_i,b_j),\min(a_i,b_j)\cdot\min(a_j,b_i))。

令 \min(a_i,a_j,b_i,b_j)=a_i，那么上式可以化为 \max(a_i\cdot\min(b_i,b_j),a_i\cdot\min(b_i,a_j))，也就是 a_i\cdot\min(b_i,\max(a_j,b_j))。

注意到 A\times B 和 B\times A 的矩形完全相同，我们可以让所有的 a_i\le b_i，这样上式可以进一步化简为 a_i\cdot\min(b_i,b_j)。

我们将矩形按 a_i 升序排列，因为 a_i\le b_i，所以对于所有的 i<j，都有 \min(a_i,a_j,b_i,b_j)=a_i。那么我们只需要在从大到小枚举 i 的过程中维护 \min\{b_j\} 就好了。

[P1] P4602 [*2000]

首先很容易得到一个贪心策略：如果对于某个 k，\sum_{d_i\ge k}l_i\ge L，那么用的钱最少的方法一定是从 d_i\ge k 里价格最小的开始，贪心地往上取。如果做完之后用的钱仍然 \ge g，那么称这个 k 为 合法的。答案就是所有的 合法的 k 里面最大的。

显然，「贪心地往上取」可以将果汁按价格排序，然后通过各种二分做到单次 O(\log n)。

注意到这个 合法性 也是单调的，也就是说，如果一个数 k 合法，那么比它小的显然都合法。

所以我们可以先二分 k，然后对每一个二分出来的 k 二分 check 合法性。

注意到一个重要的性质：cdecl 不会整体二分。所以我们必须使用在线做法。

那么问题就变成了：在序列中插入一个数，在历史版本上进行一些二分操作。

可持久化序列！主席树！然后在历史版本的线段树上二分即可。

注意一个细节：二分的时候，如果发现线段树里的 \bf\sum l_i 比查询的 \bf L 小，那么直接返回 INF。

现在感觉主席树挺自然的，不像刚学的时候那么突兀了（

[P1] CF1208D [*1900]

首先，显然 1 的位置是序列中最后一个 0 出现的位置，而且每一个数对后面所有比它大的数有贡献。

考虑从小到大依次填数，令当前枚举到了 i，每一次找到这个序列里最后出现的 0 的位置，然后把那个位置改成 INF，并将它后面的数字全部减去 i。

[P1] CF1239D [*2400]

注意一下题目的限制条件：每个人都认识自己的猫，选出来的人和猫总数必须 \bf=n。

也就是说，第 \bf i 人和第 \bf i 只猫必须也只能选一个。这让我们想到 2-SAT。

第 \bf x 个人认识第 \bf y 只猫 可以转化为 x=\texttt{true}\to y=\texttt{true}。那么根据 2-SAT 的套路，这个限制可以转化为 x\to y 的一条有向边。

然后我们发现所有的 \texttt{false} 点都不会有边，所以我们只需要 n 个点了。

如果上面建出来的图出现了 SCC，那么里面必须同时选 \texttt{true}（人）或者同时选 \texttt{false}（猫）。

注意到如果不考虑 1\le j,p 的限制，全部选人一定是合法的。那么我们只要把一个强连通分量里选成猫，其它的都选人就行了。

所以如果只有一个强连通分量，那么无解。否则把某个缩点后入度为零的 SCC 全部选猫，然后其它选人即可。

[P1] CF1238F / P3174 [*2300]

？？？？为什么这破题能有 *2300。。。

首先注意到，不能有三个区间互相相交，也就是说，只能是一个区间完全覆盖另一个，或者两个区间重叠一部分。

完全覆盖的点都是叶子，重叠一部分的点形成了一条链。这张图显然是一条毛毛虫。

求一棵树上的最大生成毛毛虫显然可以直接 DP。

虽然题比较傻逼，但是恶评 + 双倍经验我觉得海星（

[P1] P4281 [*500]

答案显然是 \operatorname{LCA}(x,y),\operatorname{LCA}(x,z),\operatorname{LCA}(y,z) 中的一个。傻逼题。

[P1] CF1238E [*2200]

这个题的套路我见过。。

令 dp_S 为 S 这个集合中最小的 slowness。包括所有完全的和不完全的。（不太好描述）

令 \displaystyle c_{x,y}=\sum_{i=1}^{n-1}[s_i=x\land s_{i+1}=y]。

令 S 集合向外延伸的链的数量是 f(S)。那么显然有 \displaystyle f(S)=\sum_{i\in S}\sum_{j\not\in S}c_{i,j}。

那么令 S-S'=\{x\}，可以写出转移方程 dp_S=dp_{S'}+f(S')。

然后开始化式子。

\begin{aligned}&f(S')\\=&\sum_{i\in S'}\sum_{j\not\in S'}c_{i,j}\\=&\sum_{i\in S}\left(\sum_{j\not\in S}c_{i,j}+c_{i,x}\right)-\left(\sum_{j\not\in S}c_{x,j}+c_{x,x}\right)\\=&f(S)+\sum_{i\in S}c_{i,x}-\sum_{j\not\in S}c_{x,j}\end{aligned}

初始值 dp_\varnothing=0。然后按照这个式子 DP 就好了。

其实直接把所有的 f(S) 预处理出来，就没那么多事了……

[P1] P4592 [*500]

这题太无聊了吧……出在 TJOI2018 也是很魔幻了……

树剖、树上差分、可持久化 Trie 板子题，不想写题解了，太傻逼了。

吐槽一下，为什么我在树剖里面查询（O(q\log^2 n)）和在外面树上差分（O(q\log n)）跑得一样快啊，是我复杂度算错了还是出题人太傻逼了……

[P1] P2824 [*1800]

题目越来越水了。。在切水题的路上越走越远（

二分答案。在线段树上维护 b_i=[a_i<mid] 里 0 的数量和 1 的数量。

众所周知，对 01 序列排序是十分简单的，然后就可以直接做了。

复杂度 O(n\log^2n)。

貌似有 O(n\log n) 的做法，有时间再看看吧。。

[P1] P1081 [*1600]

预处理 a_{i,j} 为从 i 开始走 2^j 轮之后，A 行驶的距离，b_{i,j} 同理，f_{i,j} 为 2^j 轮之后的位置。

然后没了，只不过细节有点卡。

[P1] CF1256E [*2200]

挺有意思的一道题……

如果某个字符串里某种字符的出现次数和另外一个字符串的不一样，那么肯定是 NO。

注意到一点：交换两个不同字符会改变逆序对的奇偶性。而且显然，答案是 YES 当且仅当两个字符串能够同时被排好序，而能同时被排好序等价于逆序对奇偶性相同。

那么我们可以得到一个思路：如果两个字符串中所有字符的出现次数一样，且奇偶性相同，那么 YES，否则 NO。

但是还有一个特例：如果一个字符串里有两个相同字符，且两个串的所有字符的出现次数一样，那么也是 YES。因为如果对这两个相同的字符进行交换，并不会改变逆序对的奇偶性。

[P1] P3215 [*2300]

先考虑静态 + 全局查询的情况。

首先，可以一直将最左边的左括号和最右边的右括号匹配。最后剩下的一定是 )))))...(((((( 这样的括号串。

然后每一次操作可以消除一对同方向的括号。如果有两个不同方向的括号，那么需要两次操作才能消除。

令 ( 为 1，) 为 -1，最小前缀和为 \text{lmn}，最大后缀和为 \text{rmx}，那么 QUERY 的答案就是 \lceil|\text{lmn}|/2\rceil+\lceil\text{rmx}/2\rceil。

\texttt{这里插播一条重要新闻：神鱼啊可爱哦爱！}

翻转操作只是把 前缀和 和 后缀和、左儿子和右儿子翻转了，反转操作只是把 1 和 -1 翻转了，也就是最小值和最大值翻转，然后全部取相反数。

所以用平衡树维护最大最小的前缀后缀即可。

[P1] P4556 [*2000]

考虑树上差分。链上加可以表示为 +x, +y, -\operatorname{LCA}(x, y), -fa[\operatorname{LCA}(x,y)]。

显然，如果对每一种颜色跑一遍 DFS 是会 T 飞的。我们要想一个办法，快速地合并所有儿子的操作信息。只用一遍 DFS 处理完所有的颜色。

考虑线段树合并。

在每一个点上开一棵动态开点权值线段树。每一次操作可以转化为在某一个点的线段树上单点修改。

[P1] GSS2 [*2000]

离线所有询问，将所有询问按照右端点排序。枚举 r=1\to n，在 i 号点维护 a_i,\ldots a_r 去重后的和，那么每次询问可以转化成查询区间历史最大值，每次移动右端点可以转化成区间修改。

>_<

[P1] AT2388 [*2500]

妙题啊……

令 a_{n+1} 为 a_1,a_2,\ldots,a_n 的异或和，b_{n+1} 同理，那么每次操作相当于交换 a_i,a_{n+1}。

那么我们很容易想到一道初赛题：

求最少交换几次，可以让原序列排好序。

同理，我们在 a_i 和 b_i 之间连边。这里先假设 a 中的所有数字之间互不相等。

如果形成了一个长为 n 的环，那么我们需要 n+1 次操作。所以只需要枚举所有环就可以得到答案。

比如 n=3,a=[1,2,3,0],b=[2,3,1,0]，需要 4 次操作。（其中 a 的最后一位是 a_{n+1}，b 同理）

接下来考虑可以有数字相等的情况，但是 a_1\sim a_n 中的所有数字都不和 a_{n+1} 相等。

如果有两个环中存在相同的数字，那么其中一个环就可以少用一次操作。

比如 n=6,a=[1,2,3,1,2,3,0],b=[2,3,1,2,3,1,0]，只需要 7 次操作。

具体的方法自行思考。

然后考虑没有特殊限制的情况。

和前面一种情况类似。如果某个数（无论 a,b）在环中，且和 a_{n+1} 或 b_{n+1} 相同，您可以节省一次操作。

比如 n=3,a=[1,2,0,3],b=[2,3,1,0]，只需要 3 次操作。因为 a_3=b_4,b_2=a_4。

但是注意，这种情况最多节省一次操作。

最后考虑无解的情况。

显然，如果 a,b 排序后（a_{n+1},b_{n+1} 参与排序）不完全相等，那么无解。

[P1] CF446C [*2600]

众所周知，F(n)=\frac{\sqrt5}5\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]。

观察到 \sqrt5\equiv383008016\pmod{10^9+9}，也就是说：

\frac{\sqrt5}5\equiv276601605\pmod{10^9+9}
\frac{1+\sqrt5}2\equiv691504013\pmod{10^9+9}
\frac{1-\sqrt5}2\equiv308495997\pmod{10^9+9}

设 X=691504013,Y=308495997,Z=276601605。

那么 F(n)\equiv Z(X^n-Y^n)\pmod{10^9+9}。

所以用线段树维护区间加 [ZX,ZX^2,\ldots],[-ZY,-ZY^2,\ldots] 就好了。

[P0] HDU3709 [*1400]

数位 DP 入门题。。

枚举支点，把 a=b 转化成 a-b=0。设 dp_{i,j,k} 为前 i 位，支点是 j，两边力矩的差为 k 的方案数，然后直接跑数位 DP 就好了。

然后我闲得蛋疼用另一种方法重写了这题：

设支点为 pos，那么一个数 \overline{a_1a_2\ldots a_n} 两边力矩之差为 \displaystyle\sum_{i=1}^na_i(i-pos)=-\left(\sum_{i=1}^na_i\right)pos+\sum_{i=1}^na_i\cdot i。

令 \displaystyle A=-\sum_{i=1}^na_i,B=\sum_{i=1}^na_i\cdot i，那么这个数是平衡数当且仅当 -\frac BA\in\mathbb Z,1\le-\frac BA\le n。

所以我们可以设 dp_{i,A,B} 为前 i 位，两边力矩之差的一次项系数和常数项分别为 A,B 时的方案数。

然后发现 sb HDU 只开了 64MiB……

在本地测试极限数据之后，把数组压成了这样：int dp[19][163][1540];

然后发现只有不到 40MiB，交上去发现过了 2333

UPD：

前一种 DP 相当于是：dp_{i,j,k} 为前 i 位，f(j)=k 的方案数。

后一种 DP 相当于是：dp_{i,j,k} 为前 i 位，f(x)=j\cdot x+k 的方案数。

事实上，因为 f(x) 是一个一次函数，所以只要两个点值就可以确定。不知道能不能搞出一种奇怪的做法……

所以能不能钦定 x_0,x_1，令 dp_{i,j,k} 为前 i 位，f(x_0)=j,f(x_1)=k 的方案数啊（

实际上只是用不同的方式表示了 f(x)？

[P0] CF401D [*2000]

？？？刚学记搜的都能 AC 吧，tm 还是紫的……

建议难度：绿（我也不知道这个 *2000 是怎么评出来的）

考虑对每种数字的出现次数状压。令输入的数 n 中，数码 i 出现了 a_i 次，c_i=\prod_{i=0}^{i-1}(a_i+1),c_0=1，那么我们可以让每一个 10 元组 (x_0,x_1,\ldots,x_9) 对应一个数 \sum_{i=0}^9c_ix_i，而且这些数是从 0 开始连续编号的。

显然，三元组的数量不会超过 3^{10}=59049，所以直接记搜就好了。

[P0] HDU4734

sb 题

[P0] HDU4389

~~设 \sout{dp_{i,j,k}} 为前 \sout i 位，数字和为 \sout j，膜 \sout{\operatorname{lcm}(1,2,3,\ldots,81)=k} 的方案数。~~

这显然做不了啊喂！

分段打表不太清真，然后我看了下题解：

做 81 次 DP，每次钦定一个数字和 k。设 dp_{i,j,k,l} 为前 i 位，当前数字和为 j，j\bmod k=l 的方案数。

>_< wtcl

[P0] P1297 [*800]

sb 题

每个选项的选择概率是 \frac1{a_{i-1}}，正确率是 \frac1{a_i}，有 \min(a_i,a_{i-1}) 种 AC 的事件。所以 AC 第 i 题的概率是 \frac{\min(a_i,a_{i-1})}{a_ia_{i-1}}，即 \frac1{\max(a_i,a_{i-1})}。

[P0] P4316 [*800]

sb 题

设 p_i 为 1\to i 的概率，dp_i 为 1\to i 的期望长度，d_i 为 i 的出度，那么对于所有的 x\xrightarrow{w}nx，有 dp_{nx}=dp_{nx}+\frac{dp_x+w\cdot g_i}{d_i}。

[P0] P2473 [*1600]

简单题

设 dp_{i,S} 为，1\sim(i-1) 吃掉的宝物集合为 S 的期望得分。为了方便区分，令第 i 个宝物的前提宝物集合为 s_i 而不是 S_i，为了统一大小写 (?)，令它的得分为 p_i。

对于任意的 j\in[1,n]：

如果 j\in S，那么 j 可选可不选，而且对 S 没有影响。所以这个决策对 dp_{i,S} 的贡献是 \frac1n\left[\max(0,p_j)+dp_{i+1,S}\right]。
如果 j\not\in S,s_j\subseteq S，那么 j 可选可不选，但是对 S 有影响。分两类讨论：
- 如果选 j，那么得分会加上 p_j，S 会变成 S\cap\{j\}。所以这个决策对 dp_{i,S} 的贡献是 \frac1n\left(p_j+dp_{i+1,S\cap\{j\}}\right)。
- 如果不选 j，那么得分不变，S 也不变。所以这个决策对 dp_{i,S} 的贡献是 \frac1ndp_{i+1,S}。
如果 j\not\in S,s_j\subsetneq S，那么不能选 j。所以这个决策对答案的贡献也是 \frac1ndp_{i+1,S}。

如果 i>k，那么期望得分显然是 0。然后按照上面的 DP 即可。

[P1] CF461B [*2200]

设 dp_{i,0/1} 为子树 i 的划分方案数，且 i 所在的连通块有/没有黑点。

那么对于某个 i 的儿子 u，有：

注：如果要保持 $i$ 的连通块没有黑点，那么有两种方法： - 把 $i\leftrightarrow u$ 割掉，且 $u$ 的连通块里有黑点； - 不割掉 $i\leftrightarrow u$，且 $u$ 的连通块里没有黑点。
注：如果要保持 $i$ 的连通块有黑点，那么有三种方法： - 把 $i\leftrightarrow u$ 割掉，且 $u$ 的连通块里有黑点，$i$ 的连通块里有黑点； - 不割掉 $i\leftrightarrow u$，且 $u$ 的连通块里没有黑点，$i$ 的连通块里有黑点； - 不割掉 $i\leftrightarrow u$，且 $u$ 的连通块里有黑点，$i$ 的连通块里没有黑点。

所以转移就好了，答案是 dp_{1,1}。

[P1] P2221 [*1900]

题目让我们维护的是 \displaystyle\sum_{i=l}^r\sum_{j=i}^r\sum_{k=i}^ja_k。

考虑分别计算每一个数对答案的贡献。上式可以化成 \displaystyle\sum_{i=l}^ra_i(i-l+1)(r-i+1)，也就是 \displaystyle\sum_{i=l}^ra_i[-i^2+(l+r)i+(-lr-l+r+1)]。

所以我们只要分别维护 a_i,i\cdot a_i,i^2\cdot a_i 就好了。

[P1] CF1282D [*2300]

考虑「300 个 a」和「300 个 b」两个字符串与目标串的编辑距离。

显然「300 个 a」和目标的编辑距离等于 300-\texttt{a 的数量}，「300 个 b」同理。

把 a 的数量和 b 的数量加起来，即可得到目标串的长度 n。

考虑「n 个 a」和目标串的编辑距离。显然它会等于 n-\texttt{a 的数量}。

考虑「1 个 b 和 (n-1) 个 a」和目标串的编辑距离。如果目标串的第一位是 b，那么这个编辑距离一定会小于「n 个 a」的。我们可以根据这个来判定原串的第一位是 a 还是 b。

同理，我们每一次查询可以得到目标串的一位。但是我们需要 3 次查询进行「预处理」。

注意到我们已经有 a 的数量和 b 的数量了。所以最后得到目标串的最后一位并不需要查询。总查询次数 3+n-1=n-2。

[P1] CF1278E [*2200]

显然，同一个点的所有儿子对应的区间一定是互相包含的。我们可以很容易地得到类似下面的构造方式（其中 a, b, c 都是 x 的儿子）：

---- x ------
         ------ a --------------------------------
                                               ----- a 的子树 -----
          ----- b -------------
                            ----- b 的子树 -----
           -- c --
               -- c 的子树 --

具体的实现方式：在每一个点的右端点左右插入儿子区间的左右端点，最后重标号。

[P1] CF1278D [*2100]

考虑先计算边数。如果对于两个区间 [l,r],[x,y]，有 x<l<y<r，或者 l<x<r<y（题目保证所有端点互不相同），那么 [l,r],[x,y] 有交。

注意到如果按上述方法统计，每一对区间会被算两遍。所以我们只需要考虑其中一种情况，比如 x<l<y<r。

然后用类似扫描线的方法统计即可。

[P2] CF1282E [*2400]

感觉挺难想的，看完题解之后又恍然大悟……

考虑建出原多边形三角剖分的对偶图。那么如果两个三角形之间有两个公共点，它们之间肯定有一条公共边，所以它们对应的点之间在对偶图上有一条边。

考虑先求出 q。这个排列的定义是，按照从前往后的顺序删除三角形，剩下的部分仍然是一个凸多边形。显然我们只需要把度数为 0 的点依次删掉就好了，做法类似拓扑排序。

然后考虑怎么求出 p。注意到按照倒序把 q 中的三角形合并进多边形，得到的一定还是一个凸多边形。所以我们可以用一个链表维护当前凸多边形的 p，然后每一次显然会多加入一个点，就把这个新加入的点插入在已经存在的两个点之间就好了。

[P2] CF1270E [*2300]

我讨厌数学 /dk

按照点的 x,y 的奇偶性把它们分成 S_{0,0},S_{0,1},S_{1,0},S_{1,1}。

如果 A=S_{0,0}\cap S_{1,1} 非空，且 B=S_{0,1}\cap S_{1,0} 非空，那么 A,B 是一个合法的分法。

否则 A,B 中存在一个集合是空集。将另一个集合按照某一维（比如 x）坐标的奇偶性分成两个集合，如果两个集合都非空，那么这也是一个合法的分法。

容易写出 A=S_{0,0}\cap S_{0,1},B=S_{1,0}\cap S_{1,1}。

如果还是不满足条件，那么将所有坐标除以二下取整。然后重新进行上面的过程。

感性理解即可

[P1] P4516 [*2000]

设 dp_{i,0/1,0/1} 为以 i 为根的子树中，i 是否被监听，是否被选中且其它点都被监听的泛化物品。

对于某一条边 x\to y，其中 x 是 y 的父亲时，合并 dp_x 和 dp_y 的方法如下：

- $x$ 以前没有被监听，现在因为 $y$ 被选中，所以就被监听了。可得 $dp'_{x,0,0}+dp_{y,1,1}$； - $x$ 以前已经被监听了，所以 $y$ 必须被监听，可以被选中。可得 $dp'_{x,1,0}+(dp_{y,1,0}\oplus dp_{y,1,1})$。综上所述，$dp_{x,1,0}=(dp'_{x,0,0}+dp_{y,1,1})\oplus[dp'_{x,1,0}+(dp_{y,1,0}\oplus dp_{y,1,1})]$。
- $x$ 以前没有被监听，现在因为 $y$ 被选中，所以就被监听了。可得 $dp'_{x,0,1}+(dp_{y,0,1}\oplus dp_{y,1,1})$； - $x$ 以前被监听了，所以 $y$ 可以被监听也可以不被监听，可以被选中也可以不被选中。可得 $dp'_{x,1,1}+(dp_{y,0,0}\oplus dp_{y,0,1}\oplus dp_{y,1,0}\oplus dp_{y,1,1}\oplus)$。综上所述，$dp_{x,1,1}=[dp'_{x,0,1}+(dp_{y,0,1}\oplus dp_{y,1,1})]\oplus[dp'_{x,1,1}+(dp_{y,0,0}\oplus dp_{y,0,1}\oplus dp_{y,1,0}\oplus dp_{y,1,1})]$。

[P1] HDU5290 [*1900]

设 dp_{i,j} 为：

显然 j\in[-100,100]，且 dp_{i,j} 一定会小于等于 dp_{i,j+1}。

对于某一条边 x\to y，其中 x 是 y 的父亲时，合并 dp_x 和 dp_y 的方法如下：

选 x。那么距离 x 小于等于 w_x 的都会被染色，且 x 子树中深度 >w_i 的都要染色。可得 dp_{x,w_x}=dp'_{x,w_x}+dp_{y,-w_x};
不选 x。

初值 dp_{x,x_w}=1,dp_{x,-1}=0，然后做一遍后缀 min。

[P1] P3267 [*1900]

感觉和前一道题本质相同……

注意一下 i 不需要被监视时，dp_i 的初值即可，没有什么难点。

[P1] P4622 [*1700]

注意「除了开头和结尾那个数」这条限制，它告诉我们了下面的信息：

开头结尾都是 0；
相邻两数差的绝对值小于等于 1。

那么设 dp_{i,j} 为 a_i=j 时的合法方案数。如果 a_i=-1 显然有 dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}。

[P2] CF348E [*2800]

神仙题……

考虑选出一条直径，那么相当于其它的子树都是挂在直径下面的。设直径为 A\leftrightarrow B，根为 A。

考虑每一个点会与哪些点产生联系。设某棵子树的根为 x，那么这棵子树里的点会与所有子树外的，与根的距离等于 \max(A\leftrightarrow x,B\leftrightarrow x) 的点产生联系。

令这个点集为 S，那么如果 x 到 S 中所有点的路径的交中的点被删除，那么 x 将失去与所有点的联系。

然后分类讨论：

如果 \{A,B\}\subseteq S，那么只要删除 x 这个点本身才可以让 x 这个子树失去与所有点的联系；
如果 A\not\in S，那么删除 x\leftrightarrow B 可以让 x 这个子树失去与所有点的联系。我们称这种点为 R 点；
如果 B\not\in S 同理。我们称这种点为 L 点。

那么删除一个在 A\leftrightarrow B 上的点 y，有下面三种子树会对答案有贡献：

如果删除一个不在 A\leftrightarrow B 上的点，这个点所对应的子树中黑点个数就是答案。

[P2] P3989 [*2500]

神仙题……

首先，当 n>21 时肯定无解。

然后考虑设 dp_S 为，对于 S 集中的字母，最早的合法位置。

设 f(i,j) 为第 i 个位置后，第一次出现 j 的位置。

考虑枚举排列中的最后一位，可以得到 dp_S=\max_{i\in S}f(dp_{S\backslash i},i)。

[P2] 0117C [*2000]

设 dp_{l,r} 为将 [l,r] 这个区间归原的方案数。

枚举分界点 i\in[l,r)，那么答案就是 \binom{r-l-1}{i-l}dp_{l,i}dp_{i+1,r}。因为顺序可以随意指定。

可以通过做前缀后缀 min max 去掉 check 的部分，将复杂度将至 O(n^3)？

[P1] AT2163 [*1800]

如果出现了两个相邻的数字，那么它上面一定也是两个相邻的数字。

在排列的中心构造一下即可。

[P1] AT2165 [*2000]

二分答案。

令 f_i=[a_i\le mid]，那么考虑找到离中间最近的长度为 2 的连续段。如果是 0，那么 ans>mid，否则 \le mid。特判掉 0,1 交替出现的情况。

[P1] CF895C [*2000]

首先注意到我们只需要考虑每个质因子出现次数的奇偶性，所以可以状压。

然后我们用一个集合 S 来表示所有出现次数为奇数的质因子。

设 \displaystyle cnt_x=\sum_{i=1}^n[a_i=x]，A_i 为 i 中出现次数为奇数的质因子，dp_{i,S} 为原数组中所有 \le i 的数拼出集合 S 的方案数。

然后有 dp_{0,\varnothing}=1，转移分以下两种情况：

。答案是 dp_{70,\varnothing}-1。

[P1] CF786B [*2600]

线段树优化建图板子。具体见其它题解。

[P1] CF776D [*2000]

直接建 2-SAT 就好了，然后您会发现这个只需要用并查集，然后就做完了。

[P1] P3825 [*2500]

枚举原串中的每一个 x 要变成 a 还是 b，然后 2-SAT。

[P1] ARC103F [*2400]

略。

[P1] ARC103D [*2000]

可以用 1,2,4,\ldots,2^{30} 构造出任何满足 2\mid(x+y),x+y<2^{31} 的点。

显然如果 x+y 奇偶性不同就是无解，否则可以用 (1),1,2,4,\ldots,2^{30} 构造出来。

[P1] ARC030D [*2200]

略。

[P1] BZOJ2818 [*1900]

略。

[P2] CF576D [*2600]

将所有的边按照 d 从小到大排序，然后依次考虑只允许使用前 i 条边的最短路。

首先令 can_{i,j,k} 表示能不能在 d_i 时刻从 j 号点到达 k 号点，dis_{i,j,k} 仅仅使用前 i 条边从 j 号点到达 k 号点的最短路，排完序后的前 i 条边构成的邻接矩阵为 G_i。

那么 can_i=can_{i-1}\times G_i^{d_i-{d_{i-1}}}，其中乘法是矩阵乘法。

然后考虑更新最短路。dis_{i,j,k}=\min(dis_{i-1,j,k},dis_{i-1,j,x_i}+1+dis_{i-1,y_i,k})。

最后对于每一个能从 1 走 d 步到达的点，因为限制了只允许使用前 i 条边，且前 i 条边已经被解锁了，所以可以直接对于所有 can_{1,j}=1 的 j，ans\leftarrow\min(ans,d+dis_{i,j,n})。

[P1] CF1149B [*2200]

直接 DP 就行了。

[P1] CSAcademy - Manhattan

\begin{aligned} &\text{let}~f(k)=\min(x_2+k,x_4)-\max(x_1+k,x_3)+1,\\ &\text{assume that}~y_2<y_3,\text{then}\\ &\sum_{a=x_1}^{x_2}\sum_{b=y_1}^{y_2}\sum_{c=x_3}^{x_4}\sum_{d=y_3}^{y_4}\binom{|a-c|+|b-d|}{|a-c|}\\ \xlongequal{k=a-c}&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\sum_{b=y_1}^{y_2}\sum_{d=y_3}^{y_4}\binom{|k|+|b-d|}{|k|}\\ =&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\sum_{b=y_1}^{y_2}\sum_{d=y_3}^{y_4}\binom{|k|+d-b}{|k|}\\ =&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\sum_{b=y_1}^{y_2}\left[\binom{|k|+y_4+1-b}{|k|}-\binom{|k|+y_3-b}{|k|}\right]\\ =&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\sum_{b=y_1}^{y_2}\left[\binom{|k|+y_4+1-b}{|k|+1}-\binom{|k|+y_3-b}{|k|+1}\right]\\ =&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\left[\binom{|k|+y_4-y_1+2}{|k|+1}-\binom{|k|+y_4-y_2+1}{|k|+1}-\binom{|k|+y_3-y_1+1}{|k|+1}+\binom{|k|+y_3-y_2}{|k|+1}\right]\\ \xlongequal{p=|k|+2}&\sum_{k=x_3-x_2}^{x_4-x_1}f(k)\left[\binom{p+y_4-y_1}p-\binom{p+y_4-y_2-1}p-\binom{p+y_3-y_1-1}p+\binom{p+y_3-y_2-2}p\right]\\ \end{aligned}

屑出题人

[P1] P3658 [*1900]

设 i 在排列 A 中的出现位置为 a_i，B 中为 b_i。

那么实际上就是要求出有多少对 (i,j) 满足 |i-j|>k,a_i<a_j,b_i>b_j。

然后就是三维偏序裸题了。

[P1] P4169 [*1900]

对于两个点 (x,y),(x',y')，如果 x'\le x,y'\le y，那么 x'+y' 最大的点距离 (x,y) 最近。

所以我们可以把平面旋转四次，然后取每次答案的 \min。

[P2] CF1045G [*2200]

对于两个机器人 (x,r,q),(x',r',q')，如果满足 |x-x'|\le\min(r,r'),|q-q'|\le K，那么它们可以交流。

考虑按 r 降序排序。假设 r\le r'，那么只需要满足 |x-x'|\le r,|q-q'|\le K，即 x-r\le x'\le x+r,q-K\le q'\le q+K。

然后就是裸的二维数点了。

[P1] CF528D [*2500]

\begin{aligned} &\text{let}~S_c(x)=\sum_{i=0}^{n-1}[\exists i-k\le j\le i+k,S_j=c]x^i,\\ &~~~~\,\,T_c(x)=\sum_{i=0}^{m-1}[T_i=c]x^i,T'_c(x)=\sum_{i=0}^{m-1}[T_{m-i-1}=c]x^i.\\ &ans_i\\ =&\sum_{j=0}^{m-1}\sum_{k\in\{A,T,G,C\}}[x^{i+j}]S_k(x)\cdot[x^j]T_k(x)\\ =&\sum_{k\in\{A,T,G,C\}}\sum_{j=0}^{m-1}[x^{i+j}]S_k(x)\cdot[x^{m-j-1}]T'_k(x)\\ =&\sum_{k\in\{A,T,G,C\}}[x^{m+i-1}]S_k(x)\cdot T'_k(x)\\ \end{aligned}

然后直接乘就完事了

[P(-1)] CF342E [*400]

傻逼题

不说了，伤心

[P1] P3242 [*2100]

假设 dfn_x\le dfn_y。

如果 x 是 y 的祖先，假设 z 是 x 以 y 为根时的父亲，那么 (x,y) 是 (u,v) 的子路径当且仅当 1\le dfn_u<dfn_w,dfn_y\le dfn_v<dfn_y+sz_y 或 dfn_y\le dfn_u<dfn_y+sz_y,dfn_w+sz_w\le dfn_v\le n。

否则 (x,y) 是 (u,v) 的子路径当且仅当 dfn_x\le dfn_u<dfn_x+sz_x,dfn_y\le dfn_v<dfn_y+sz_y。

然后就变成给一堆矩形和一堆点，求覆盖每一个点的矩形的权值 k 小。

然后扫描线 + 整体二分。

[P2] P2619 [*2300]

考虑一个偏移量 ofs，把所有白边全部加上 ofs 跑 Kruskal。

注意到 ofs 越小，选的白边数量越多。那么我们可以二分 ofs，直到选的白边数量 =k。此时答案就是 MST 边权 -k\cdot ofs。

如果对于某个 ofs=mid，选的白边数量 >k，但是当 ofs=mid+1 时，白边数量却 <k 了，那么切换成黑边的这些白边一定是边权相等的（证明略）

即在 ofs=mid 时，一定有一个选白边数量 =k 的合法方案，它的权值和与选 >k 条白边的这个方案相同。

Kruskal 的时候，遇到相同的边权优先选白边。

[P1] P4072 [*2200]

\displaystyle dp_{i,j}=\min_{k<i}\{dp_{k,j-1}+(s_i-s_k)^2\}

\begin{aligned} dp_{x,j-1}+(s_i-s_x)^2<dp_{y,j-1}+(s_i-s_y)^2\\ dp_{x,j-1}-2s_is_x+s_x^2<dp_{y,j-1}-2s_is_y+s_y^2\\ \frac{dp_{x,j-1}-dp_{y,j-1}+s_x^2-s_y^2}{s_x-s_y}<2s_i\\ \end{aligned}

设 f(x)=dp_{n,x}。显然这个 f(x) 随着 x 的增加是单调递减的，然后可以感性理解它是下凸的，即导数递增。

注意到如果我们不考虑次数，直接进行 DP，那么得到的答案一定是 f(x) 的极值，即 f'(x) 的零点。但是我们要求的是 f(m) 的值。

于是我们可以考虑二分一个 k，然后设 g(x)=f(x)+xk,g'(x)=f'(x)+k。那么 g'(x) 的零点是关于 k 单调的。

如果对于某个 k，g'(m)=0，那么 f(m)=g(m)-km。

然后这个 k 的范围应该是 f 的值域。\color{white}\sf{斜率单调才可以单调队列，否则必须二分}

如果对于某个 k，答案 >m，但是 k+1 时，答案 <m，那么可以证明，在 k+1 时，存在一个答案 =m 的最优解。

然后后面就开始出现大量的简单题了：

[P0] P2502 [*1200]

暴力做 m 遍 MST 就完事了。

[P0] P1197 [*800]

经典套路，把询问全部倒过来。

[P0] P3465 [*1200]

其实就是找到一些不相交的基环外向树，且它们包含图中所有的点。

[P0] P5937 [*800]

前缀异或和，然后 2-SAT，然后用并查集做就好了。

[P0] P5214 [*800]

线段树分治 + dsu。

[P1] P5633

同 P4072。

[P1] P5631

权值为 x 的边会在 [0,x) 和 (x,10^5] 出现，然后按照这个做线段树分治。

[P1] CF938G [*2900]

首先线段树分治，然后我们只需要处理询问 1 和询问 3 了。

然后注意到 x\to y 的异或和等于 x\to rt 的异或和异或上 y\to rt 的。所以可以用带权并查集维护。

然后就和 P4151 一样了。

[P1] AGC038D [*2000]

显然，所有 op=0 的限制上的点形成了一片森林。

然后所有 op=1 的点形成了一个环。

如果所有的限制都满足 op=0，那么 m 可以取到 n-1，因为可以把所有点放在一棵树上。

边数的上界是把从每个连通块里选一个点，连成完全图，然后加上森林的边。设连通块数为 cnt，那么边数上界为 n-cnt+cnt(cnt-1)/2。