2021-01-14~2021-02-28¶

CF1450E¶

题意¶

$n$ 个人每人有一个权值 $a_i$，同时有 $m$ 个下列两种关系：

$a_i = a_j+1$。
$|a_i-a_j|=1$。

求是否存在合法的序列 $a_1,a_2,\cdots,a_n$，若存在，最大化 $\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i$。($1\le n\le 200$，$n-1\le m\le 2000$)

题解¶

首先原图的基础图必然是二分图，因为相邻两个人的权值相差为 $1$，如果不是二分图直接无解。

如果是二分图，那么第一个关系等价于 $a_i \ge a_j + 1 \land a_i \le a_j+1$，第二个关系先写为 $a_i-a_j \le 1 \land a_j-a_i \le 1$。之后跑 floyd 差分约束，如果任意 $d_{i,i} < 0$ 说明有负环，否则任意两点间距离的最大值即为 $\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i$ 的最大值，即 $a_i - a_j \le x$。

注意到上述第二个关系并不完全等价，但是建图中每条边都是非 $0$ 的，若有 $d_{i,j} = 0 \Rightarrow a_i=a_j$，则说明有另一条长度为偶数的路径，再加上这一条边形成了一个奇环，与原图是二分图矛盾，从而该做法是正确的。

CF1473F¶

题意¶

给定序列 $a_1, a_2, \cdots, a_n$，和 $b_1, b_2, \cdots, b_n$，需要选择 $1,2,\cdots,n$ 的一个子集 $S$，满足如果 $i \in S$，则 $\forall (j < i \land a_j \mid a_i),j \in S$ ，求 $\sum_{i\in S}b_i$ 的最大值。($1 \le n \le 3000$，$1 \le a_i \le 100$，$-10^5 \le b_i \le 10^5$)

本题空间限制 32MB。

题解¶

最大权闭合子图，直接跑边数 $O(n^2)$ 存不下，注意到 $a_i$ 最大只有 $100$，且如果 $k < j < k,a_j \mid a_i,a_j=a_k$，则如果选 $i$ 必然选 $j$，由 $j$ 的限制必选 $k$，从而只需要连边 $i \to j$，这样每个点最多连出去因子个数条边，从而可以通过本题。

CF1473G¶

题意¶

给出一个地板图，每列宽度相同，由数个长度相同的瓷砖组成。第一列有 $1$ 个瓷砖，之后：

有 $a_1$ 列比前一列多一个瓷砖，接着有 $b_1$ 列比前一列少一个瓷砖。
有 $a_2$ 列比前一列多一个瓷砖，接着有 $b_2$ 列比前一列少一个瓷砖。
...
有 $a_n$ 列比前一列多一个瓷砖，接着有 $b_n$ 列比前一列少一个瓷砖。

可以见下面的图：

cf1463g

保证任意时刻瓷砖数量为正，现在你在第一个瓷砖，每次可以到下一列一个与当前瓷砖边界相交的瓷砖，问到最后一行瓷砖有多少种方案，对 $998244353$ 取模。($1 \le n \le 1000$，$1 \le a_i, b_i \le 10^5$，$|a_i - b_i| \le 5$)

题解¶

首先因为相邻两列只差一个，每次只能移动到下一列的 2 个（或 1 个，如果在边界且在减少），这等价于平面直角坐标系中 $(i,j)$ 移动到 $(i,j+1)$ 和 $(i+1,j)$，即每一列相当于是一条对角线。

我们考虑每一对 $a_i$ 和 $b_i$，设 $m = 1+\sum\limits_{j=1}^{i-1}(a_j-b_j)$，相当于从第 $m$ 个对角线的第 $1$ 到 $m$ 个点的方案数已知，只能向上或向右移动，到第 $m+a_i-b_i$ 条对角线的第 $1+b_i$ 到 $m+a_i-b_i-b_i$ 个点的方案数。两者的编号都从 $1$ 开始编号，则从第 $j$ 个点到第 $k$ 个点的方案数即为 $\dbinom{a_i+b_i}{b_i+k-j}$。

使用 NTT 卷积 $n$ 次即可，因为 $|a_i - b_i| \le 5$ ，所以每次有意义的项数在 $O(n)$ 级别，时间复杂度为 $O(n^2\log n)$。

需要的注意是，$k - j$ 可以是负数，所以我们可以直接让组合数对应的多项式整体增大偏移五位，最后答案再减小偏移五位即可。

CF1476F¶

题意¶

有 $n$ 个灯，每个灯有一个照明度 $p_i$，可以向左照或向右照明，向左则可以照明 $[i-p_i,i-1]$，向右则可以照明 $[i+1,i+p_i]$，求一种方案让所有灯都被照亮，或判断无解。($1 \le n \le 3\times 10^5$)

题解¶

设 $f_i$ 是用前 $i$ 个灯能照亮的最大前缀长度，考虑如何转移：

如果这个灯向左照，那么想要和前面接上，必须从一个 $f_i \ge i-p_i-1$ 的位置转移，可以用线段树维护所有 $f_i$ 相同的值中最小的下标值，从而可以快速找到这个位置。转移时，中间的所有灯必然向右照，可以用 ST 表维护区间最大值，同时如果 $i$ 这个位置是向右的，那么也要和它的范围取最大值，如果是向左的则不用考虑。
如果这个灯向右照，那么如果 $f_{i-1} < i$，前缀没接上，因此直接将 $f_{i-1}$ 的值传下去即可；否则为 $\max(f_{i-1},i+p_i)$。

需要注意的是即使 $f_{i-1} \ge i$ 也是有可能向左照明的，因为这可能让左边的一个很亮的灯改为向右照明。

输出方案时只需记录每个灯的转向即可，要注意如果一个灯左右转能照亮的前缀相同，那么肯定选择右转。

CF1476G¶

题意¶

给定长度为 $n$ 的序列，$m$ 个下列两种操作：

给定 $l,r,k$，询问区间 $[l,r]$ 中选 $k$ 个不同的数，它们出现次数最大值与最小值之差的最小值是多少；或判断不能选出 $k$ 个不同的数。
更改一个位置的数。

($1 \le n, m \le 10^5$)

题解¶

盲猜带修莫队，但是发现到了某个区间时，询问不太好处理。

这里用到了 $n$ 个数每种数出现次数所组成的集合大小不超过 $O(\sqrt{n})$ 这个性质，可以直接维护所有数出现次数排序过后的序列，当一个数增加时，设其数量为 $x$，而这个序列中所有 $x$ 必然是连续的，因此只需将最右侧的 $x$ 改为 $x+1$ 即可；一个数减少只需将最右侧的 $x$ 改为 $x-1$ 即可。这样每次修改都是 $O(1)$，到一个区间处理询问时，只需在上述过程中额外维护的每个连续的数的左边界和右边界，就可以 $O(\sqrt {n})$ 利用双指针得到最小值。

每个块大小为 $O(n^{\frac{2}{3}})$，总时间复杂度 $O(n^{\frac{5}{3}}+m\sqrt{n})$。

CF1477D¶

题意¶

给定 $m$ 对无序关系 $(l_i,r_i)$，构造两个长度为 $n$ 的排列 $p_1,p_2,\cdots,p_n$ 和 $q_1,q_2,\cdots,q_n$，满足 $\forall i \in [1,m],(p_{l_i}-p_{r_i})(q_{l_i}-q_{r_i})>0$。同时要求最小化 $p_i \ne q_i$ 的个数。

($1 \le n \le 5 \times 10^5$，$0 \le m \le \min \left(\dfrac{n(n-1)}{2},5 \times 10^5\right)$)

题解¶

考虑对于 $m$ 对关系建图，如果一个点的度数为 $n-1$，那么它与其它 $n-1$ 个位置的大小关系是确定的，因此在两个排列中该位置的值必然相等。下面通过构造证明除了上述这些点对应的位置，其它位置都可以不同：

如果我们能将剩下的位置划分为数个不相交的集合，每个集合 $S$ 满足 $\exists i \in S,\forall j \in S$，$(i,j)$ 不在给定的 $m$ 对关系中。那么可以设 $S$ 中的位置分别为 $j_1,j_2,\cdots,j_{|S|-1},i$，我们在第一个排列中给这些位置赋值 $1,2,\cdots,|S|-1,|S|$，在第二个排列中给他们赋值 $2,3,\cdots,|S|,1$，因为 $i$ 与其它位置都没有关系，而其它位置之间的大小关系不变，从而这个集合内位置之间的满足条件的。对于多个集合之间的关系，我们只要将值连续地赋给它们（即第一个集合的值域为 $[1,|S_1|]$，第二个集合的值域为 $[|S_1|+1,|S_1|+|S_2]$），就可以保证多个集合之间的关系也满足条件。

考虑如何找到上述的划分。首先建出补图中随便一个生成树，可以对 $[2,n]$ 中每个点求所有和它相连点对应集合的 $\operatorname{mex}$ 来 $O(n+m)$ 实现。

2021-03-25 update：这里的做法是假的，这样是会成环的，本题只要保证所有度数不为 $n-1$ 的点在补图的生成森林中度数非 $0$，方案就是合法的。关于成环的问题，因为实现过程的特点，没有出现 bug。~~不过以后不能这么乱搞了。~~

接下来只需将整棵树划分为数个大小超过 $1$ 的菊花图即可，让中间的点当作上述中的 $i$ 即可。考虑遍历每个点：

如果这个点已经在一个菊花图中，则跳过。
如果这个点不在一个菊花图中，随便找一个它相邻的点 $x$。如果 $x$ 不在一个菊花图中，那么让 $x$ 成为菊花图的中心，将周围所有未在菊花图中的点都拉入它的图；如果 $x$ 在菊花图中，那么它一定不是中心（否则这个点就会在菊花图中），如果对应菊花图的大小为 $2$，则直接将中心改为 $x$，将周围所有未在菊花图中的点都拉入它的图；否则直接让 $x$ 脱离原来的菊花图，重新成为一个中心，也将周围所有的未在菊花图中的点都拉入它的图。

CF1479C¶

题意¶

构造一个不超过 $32$ 个点的有向无环图，使得 $1$ 号点到 $n$ 号点恰有 $R-L+1$ 条路径，长度分别为 $L,L+1,\cdots, R$。所有边权均要为正整数，且不能有重边。($1 \leq L \leq R \leq 10^6$)

题解¶

考虑先构造出 $[0,R-L]$ 所有长度的路径，使用类似数位 dp 的构造，先构造一些点使得到达这个点之后接下来的路径可以走遍 $[0,2^i-1]$ 中的每个整数。再从 $1$ 号点考虑从哪一位开始脱离上界，然后和上述对应的该点相连，权值即为这一位往上未脱离上界的部分。最后所有点向 $n$ 号点连 $L$ 的边即可。

这样其实会有问题，首先从 $1$ 号点连出去第一个脱离上界的边的权值是 $0$，这个可以考虑让这条边权值变为 $1$，然后连出去的那个点的所有边权值减少 $1$，并把原来权值是 $1$ 的边删掉（这条边相当于变为了直接从该点到 $n$ 号点）。其次，$1$ 号点要直接和 $n$ 号点连一条权值为 $L$ 的边，那就无法连权值为 $R$ 的边了，可以再开一个点新增两条边来实现这个功能。

CF1481E¶

题意¶

$n$ 本书，每本书有一个颜色 $a_i$，每次操作可以将任意一本书放到最右侧，问使得每种颜色的书都连续放在一起最少需要操作多少次。($1 \le n \le 5 \times 10^5$)

题解¶

设 $f_{i}$ 是 $[i,n]$ 中最多保留多少本书不动，则有以下三个转移：

$f_{i+1} \to f_i$，即移动第 $i$ 本书。
若 $i$ 是颜色 $a_i$ 的所有书中最靠左的，设 $r_{a_i}$ 是该颜色最靠右的书，那么可以选择把保留所有颜色为 $a_i$ 的书，移动中间夹着的其它书，即 $f_{r_{a_i}+1}+\textit{cnt}_{a_i} \to f_i$，其中 $\textit{cnt}_{a_i}$ 是颜色为 $a_i$ 书的数量。
若 $i$ 不是颜色 $a_i$ 的所有书中最靠左的，那么也我们可以选择保留所有颜色为 $a_i$ 的书，但此时因为左边还有相同颜色的书，我们需要先把左边的颜色为 $a_i$ 的书移到最右侧，然后再把中间夹着的书移出去。因此这样所有 $[i,n]$ 中颜色不为 $a_i$ 的书都要被移动，即 $\textit{tot}_{a_i} \to f_i$，其中 $\textit{tot}_{a_i}$ 是 $[i,n]$ 中颜色为 $a_i$ 书的数量，这个值可以随着 dp 的进行而逐步增加。

上述三者取 $\min$ 即可，时间复杂度为 $O(n)$。

CF1481F¶

题意¶

给定一棵 $n$ 个节点的树，$1$ 号节点为根，你需要将 $x$ 点标为 $\text{a}$，剩下 $n-x$ 个点标为 $\text{b}$。对于每个节点，它所代表的字符串即为从根节点到该节点路径上所有节点上字母按顺序组成的字符串，最小化 $n$ 个字符串中本质不同的数量。($1 \leq n \leq 10^5$，$0 \leq x \leq n$)

题解¶

设 $d$ 为最深点的深度，则答案的下界为 $d+1$，设 $a_i$ 为深度为 $i$ 的节点的个数 ($i \in [0,d]$)，那么如果 $a_0,a_1,\cdots,a_d$ 选出一部分的和为 $x$，即可达到下界，相当于每层的颜色都一样，显然答案为 $d+1$。这转化为了一个 $\text{01}$ 背包问题，且所有物品容量之和为 $n$，那么每种物品的容量最多有 $O(\sqrt n)$ 种不同取值，转化为多重背包问题，使用队列即可优化到 $O(n\sqrt n)$。但是这个模型有更快的解法，考虑使用二进制分组，可以证明总物品数量是 $O(\sqrt n)$ 级别的：

设 $\textit{cnt}_i$ 是容量为 $i$ 的物品个数，容易得到满足 $cnt_i \ge 2^k$ 的 $i$ 至多有 $\sqrt{\dfrac{n}{2^{k-1}}}$ 个（当 $k=0$ 时则是经常使用的结论”所有物品容量之和为 $n$，那么每种物品的容量最多有 $O(\sqrt n)$ 种不同取值“）。

那么二进制分组后的总物品数量即为：

\[ \begin{aligned} &\sum _{i=1} ^ n [\textit{cnt}_i > 0]\Big(\lfloor\log_2(\textit{cnt}_i)\rfloor+1\Big)\newline =&\sum_{k=0}^{+\infty} \sum _{i=1} ^ n [cnt_i \ge 2^k]\newline \le&\sum_{i=0}^{+\infty} \sqrt{\frac{n}{2^{i-1}}} \newline =&O(\sqrt{n}) \end{aligned} \]

其中第一步的等式相当于若 $\lfloor\log_2(\textit{cnt}_i)\rfloor = k$，则 $\Big(\lfloor\log_2(\textit{cnt}_i)\rfloor+1\Big)$ 的值会被 $[cnt_i \ge 2^0],[cnt_i \ge 2^1],\cdots,[cnt_i \ge 2^k]$ 处统计到。

再使用 bitset 优化 $\text{01}$ 背包，则时间复杂度为 $O(\dfrac{n\sqrt n}{w})$。

考虑如果上述情况无解，考虑按深度从小到大一层一层填字母。设 $\text{a}$ 还剩 $x$ 个，$\text{b}$ 还剩 $y$ 个，如果这一层还可以的数量不超过 $x$ 或 $y$，就填其中一中颜色，直到某一层颜色大于 $\max(x,y)$。此时，可以发现这一层的非叶节点数量一定不超过剩余节点总数的一半，因为每个非叶节点在下层至少还有一个儿子节点。因此我们一定可以用剩余字母更多的那一种（不妨设为 $\text{a}$）将所有非叶节点填满，之后再把剩余的 $\text{a}$ 全部填到这一层的叶节点上，之后剩下所有的节点全部填 $\text{b}$ 即可。可以发现这样填涂后的答案为 $d+2$，因为相比答案为 $d+1$ 的情况，仅仅多了在上述这一层中填 $\text{b}$ 的叶节点对应的字符串。

CF1486F¶

题意¶

给定一颗 $n$ 个节点的树，给出一些路径，求有多少对路径只有一个交点。($1 \le n \le 3 \times 10^5$)

题解¶

把所有路径都提到两个点的 lca 上，那么如果交点均是两个点的 lca，它们对应的两个子树就不能相同（否则交点就会多），这个可以进行容斥，对于每个点减掉有一个子树相同的对数，再把两个子树都相同的对数加回来，前者直接开数组记录，后者开个 map 记录就行。

对于交点不均是两个点 lca 的，必然对于一个对点是 lca 而不是另一对点的 lca，可以将深度小的 lca 对除了 lca 的两条链进行树上差分，在深度大的 lca 处进行统计。每个 lca 在统计时将自己子树上来的两个差分值减掉，这样就能保证与自己两个子树有交点的路径的贡献不会被算到，从而统计到的路径只和自己有一个交点。

总时间复杂度为 $O(n \log n)$。

CF1487F¶

题意¶

将 $n$ 表示为数个由 $1$ 组成数字的和差，最小化所有数字 $1$ 的个数和。($1 \le n < 10^{50}$)

题解¶

设 $f_{i,j,k,l}$ 为前 $i$ 位已经确定且合法，此时还能延伸出去 $j$ 个 $1111\cdots 111$，$k$ 个 $-1111\cdots 111$，下一位进位的值为 $l$ 时用的 $1$ 个数的最小值。

转移时可以选择任意减少 $j$ 和 $k$，相当于让一些 $1111\cdots 111$ 或 $-1111\cdots 111$ 终止，只要 $(j-k+l) \bmod 10$ 和这一位的数字相同，就可以进行转移，令下一个 $l= \left\lfloor\dfrac{j-k+l}{10}\right\rfloor$ 即可。

可以证明，最多用 $5$ 个数（正负皆可）就可以让 $n$ 最高位减少一位：

当最高位 $\le 5$，全部用 $1111\cdots 111$，否则可以用高一位的 $1111\cdots 111$ 去减一些低位的 $-1111\cdots 111$。

从而 $\max(j,k) \le 5|n|$，$|n|$ 为 $n$ 的位数，而进位的值满足 $|l| \le \max\left(\left|\dfrac{l+j}{10}\right|,\left|\dfrac{l-k}{10}\right| \right) \le \left|\dfrac{l+5|n|}{10}\right|$，从而有 $|l| \le \dfrac{5|n|}{9}$。总时间复杂度为 $O(n^4)$，常数较大。

CF1492E¶

题意¶

给定一个 $n \times m$ 的矩阵，求一个长度为 $n$ 的序列，使得它与矩阵每一行最多有两个位置不同，或判断无解。($2 \le n$，$1 \le m$，$nm \le 250000$)

题解¶

考虑先将所选序列定为第一行，然后去接着往下爆搜，设已经改了 $x$ 个，如果当前行和目前序列差的超过 $4-x$ 个，就说明不合法要回溯。否则，枚举改哪一个或两个，继续往下搜，最后全搜完了再遍历一遍看是否合法。这样因为实际能做的选择非常少，近乎看作是常数，因此看似是爆搜，其实复杂度为 $O(nm)$。

ARC106E¶

题意¶

$n$ 个人，第 $i$ 个人上 $a_i$ 天班，休息 $a_i$ 天。每天可以给一个来上班的人发一个奖章，问让所有人都至少有 $k$ 个奖章至少要多少天。($1 \le n \le 18$，$1 \le k, a_i \le 10^5$)

题解¶

考虑二分图匹配，左边是 $nk$ 个点，每个点代表第 $i$ 个人第 $j$ 次获得的奖牌，右边每个点有 $m$ 个点代表一共有 $m$ 天，第 $i$ 个人的所有点和右边他上班的天数相连，这个图的最大匹配为 $nk$ 即说明 $m$ 天是一个合法解。

我们可以考虑二分 $m$ 的值，然后再求出最大匹配的数量。直接 dinic 或增广路必然会 TLE，可以使用 Hall 定理：

设二分图的两个点集 $|V_1| \le |V_2|$，则二分图最大匹配数为 $|V_1|$ 的充分必要条件是：对于任意 $V \subseteq V_1$，$V_2$ 中至少有一条边和 $V$ 中某个点相连的点的数量至少为 $|V|$。

考虑到本题的图中左边与第 $i$ 个人对应点相连的右侧点都是相同的，因此只需将同一个人的点放在一起进行考虑。注意到 $2nk$ 是二分的上界，因为此时每个人都至少来了 $nk$ 天，从而必然满足 Hall 定理。

设所有员工组成的集合为 $U$，我们现在相求出所有 $S \subseteq U$，右侧与 $S$ 中相关点至少有一条边相连的点有多少个。通过补集转化去求右侧只与 $U\backslash S$ 中相关点有相连的点有多少个，可以先求出右侧与 $U\backslash S$ 中所有相关点恰好都有相连的点有多少个，再用高维前缀和求出上述的值。之后再去判断 Hall 定理的信息即可，注意此时左侧实际有 $|S|k$ 个点，且高维前缀和时没算空集，需要注意一下细节。

总时间复杂度 $O\big((n2^n+nk)\log nk+n^2k\big)$。

ARC106F¶

题意¶

$n$ 个点，第 $i$ 个点有 $a_i$ 个接口，每条边可以连接两个接口，每个接口只能用一次，问有多少种不同的生成树。两个生成树相同当且仅当它们用的接口都一样且每对接口间连边情况相同。($1 \le n \le 2 \times 10^5$)

题解¶

枚举每个点的度数，由 prufer 序列的性质可以确定每个点出现的次数，则答案为：

\[ \sum_{\sum \limits _{i=1}^nd_i=2n-2}\binom{n-2}{d_1-1,d_2-1,\cdots,d_n-1} \prod_{i=1}^n A_{a_i}^{d_i} \]

设生成函数：

\[ \begin{aligned} f_{a}(x) =& \sum_{i=1}^{+\infty}\frac{1}{(i-1)!}A_{a}^ix^i \newline =& \sum_{i=1}^{+\infty}\frac{a!}{(i-1)!(a-i)!}x^i \newline =& a\sum_{i=1}^{+\infty}\frac{(a-1)!}{(i-1)!(a-i)!}x^i \newline =& a\sum_{i=1}^{+\infty}\binom{a-1}{i-1}x^i \newline =& ax\sum_{i=0}^{+\infty}\binom{a-1}{i}x^i \newline =& ax{(x+1)}^{a-1} \newline \end{aligned} \]

则答案为：

\[ \begin{aligned} & \left[x^{2n-2}\right](n-2)!\prod_{i=1}^nf_{a_i}(x) \newline =& \left[x^{2n-2}\right](n-2)!\prod_{i=1}^na_ix(x+1)^{a_i-1} \newline =& \left[x^{2n-2}\right](n-2)!x^n\prod_{i=1}^na_i(x+1)^{a_i-1} \newline =& \left[x^{n-2}\right](n-2)!\prod_{i=1}^na_i(x+1)^{a_i-1} \newline =& \left[x^{n-2}\right](n-2)!\left(\prod_{i=1}^na_i\right)(x+1)^{\left(\sum \limits _{i=1}^na_i\right)-n} \newline =& (n-2)!\left(\prod_{i=1}^na_i\right)\binom{\left(\sum \limits _{i=1}^na_i\right)-n}{n-2} \newline =& \left(\prod_{i=1}^na_i\right)\frac{\left[\left(\sum \limits _{i=1}^na_i\right)-n\right]!}{\left[\left(\sum \limits _{i=1}^na_i\right)-2n+2\right]!} \newline &= \left(\prod_{i=1}^na_i\right)\left[\left(\sum _{i=1}^na_i\right)-n\right]^{\underline {n-2}} \end{aligned} \]

ARC107C¶

题意¶

给出一个 $n \times n$ 的方阵，$1, 2, \cdots, n^2$ 每个数字恰好出现一次。两行或两列只要满足 $n$ 个对应位置相加之和不超过 $k$ 就能交换，问能得到多少种不同的方阵。($1 \leq n \leq 50$)

题解¶

可以发现行和列是独立的，因为行交换后，两列能否交换不会因此改变。所以只用考虑行有多少种交换方案，再乘以列的即可。可以证明如果 $x$ 和 $y$ 能交换，$y$ 和 $z$ 能交换，则 $x$ 和 $z$ 也能交换，相当于传递性： $$ xyz \to yxz \to zxy \to zyx $$ 因此使用并查集将能交换的合并到一起，在一个集合内的相对顺序可以任意，从而每一个都乘以一个对应大小的阶乘即可。

ARC107D¶

题意¶

求选 $n$ 个物品使得容量之和为 $k$ 的方案数，物品容量为 $\dfrac{1}{2^i}\ (i = 0,1,\dots)$，每种物品有无数个。($1 \leq k \leq n \leq 3000$)

题解¶

考虑物品容量的特殊性进行dp，设 $f_{i,j}$ 为已容量为 $i$ 且已选个数为 $j$ 的方案数，那么如果方案中存在一个容量为 $1$ 的物品，有 $f_{i-1,j-1} \to f_{i,j}$；如果方案中不存在一个容量为 $1$ 的物品，那么此时的方案数和将所有物品容量乘以 $2$ 的方案数是相同的，即 $f_{2i,j} \to f_{i,j}$。

直接进行记忆化搜索 dp 即可，边界条件为 $f_{0,0} = 1$，注意当 $i>j$ 或 $i=0,j\ne0$ 时不合法，有 $f_{i,j} = 0$。

时间复杂度为 $O(n^2)$。

ARC107F¶

题意¶

$n$ 个点 $m$ 条边的无向图，删去一个点及它相连的边的代价为 $a_i$，每个点有一个权值 $b_i$，一个连通块的权值为该连通块中所有点的 $b_i$ 之和的绝对值。最大化 所有连通块权值之和 $-$ 删点付出的代价。($1 \le n,m \le 300$)

题解¶

考虑所有点都没删，且对答案贡献的 $b_i$ 都取了绝对值，然后再考虑每个点如果被删了或者实际上并没有取绝对值会让权值减少多少，并添加一些限制使得跑出来的网络流是合法的，求这个图的最小割，就等价于让减小的值最小，即最终的答案最大。本题中的限制即为同一个连通块中所有点取正或是取负都是相同的。

对于每个点，拆成两个点 $u_i$ 和 $v_i$:

源点 $S$ 连 $u_i$，流量为如果 $i$ 所在连通块所有点都取正号，那么和该点取 $|b_i|$ 相比，减少了多少.
$u_i$ 连 $v_i$，流量为如果删掉 $i$ 那么花费的代价和该点取 $|b_i|$ 相比，减少了多少.
$v_i$ 连汇点 $T$,流量为如果 $i$ 所在连通块所有点都取负号，那么和该点取 $|b_i|$ 相比，减少了多少。

这样，对于每个点，如果一个割合法，那么三条边必须要删一条，否则 $S$ 和 $T$ 连通。

考虑如何进行限制，如果两个点在同一个连通块，那么它们不能都没被删而且一个取正号一个取负号，因此如果 $i$ 和 $j$ 之间有边，我们可以将 $v_i$ 连 $u_j$，$v_j$ 连 $u_i$，流量均为正无穷，这样如果 $S \to u_i$ 和 $v_j \to T$ 被割掉而其它的没有被割掉，那么 $S$ 和 $T$ 还是连通的，另一边也同理，从而可以限制掉这种不合法情况。

ARC108E¶

题意¶

给出一个 $1$ 到 $n$ 的排列，每次随机选择一个数，使得所选数构成的子序列的单增的，每次等概率地从选了对应位置所选数构成子序列仍单调的位置里面选，如果不存在这样的位置则终止。求选择数个数的期望。($1 \le n \le 2000$)

题解¶

设原排列为 $p_1,p_2,\cdots,p_n$，那么将原序列稍稍平移得到一个新序列 $a_1,a_2,\cdots.a_{n+2}$： $$ a_i= \begin{cases} 0,&i=1 \newline p_{i-1},&2 \le i \le n+1 \newline n+1,&i=n+2 \end{cases} $$ 我们设 $f_{l,r}$ 是在 $a_l$ 和 $a_r$ 已选的情况下，$a_{l+1},a_{l+2},\cdots,a_{r-1}$ 这些数中选择个数的期望，那么最终答案即为 $f_{1,n+2}$。考虑期望的线性性，则有如下转移： $$ f_{i,j} = \frac{1}{|S|}\sum_{k \in S}(f_{i,k}+f_{k,j}+1),S={k|i < k < j \land a_i < a_k < a_j} $$ 直接暴力区间 dp 复杂度是 $O(n^3)$ 的，考虑所有 $k$ 要满足 $i < k < j \land a_i < a_k < a_j$，那么可以将转移式稍微变换形式： $$ f_{i,j} = \frac{1}{|S|}\left(\sum_{k \in S}f_{i,k}+\sum_{k \in S}f_{k,j}+|S|\right) $$ 因此使用树状数组维护固定左端点/右端点的每个 $a_i$ 的上述三个量，并按状态对应的区间长度从小到大转移即可，时间复杂度 $O(n^2 \log n)$。

ARC108F¶

题意¶

给出一棵 $n$ 个节点的树，每个点可以染黑白两种颜色，问对于 $2^n$ 种染色情况，最远同色点对的距离之和是多少。如果某种颜色只有一个点，那么该颜色的最远同色点对距离为 $0$。($1 \le n \le 2 \times 10^5$)

题解¶

先找出树的直径，如果直径两端点同色，那么显然答案即为直径长度，方案数为 $2^{n-1}$。下面考虑当直径两端点不同色的情况：

设除了直径端点的两个点外，到直径两个点的距离分别为 $a_i$ 和 $b_i$，将所有点按 $\max(a_i,b_i)$ 从大到小进行排序，依次枚举如果前面的点均与近的那个端点同色，即对距离的贡献为 $\min(a_i,b_i)$，而该点与远的那个端点同色，即对距离的贡献为 $\max(a_i,b_i)$，那么此时的答案即为 $\max(a_i,b_i)$，方案数即为后面的点的颜色都可以随便取的方案数 $2^{n-i}$。当 $\max(a_i,b_i) \le \max \limits _{j=1} ^{i-1} [\min(a_j,b_j)]$ 时，$\ge i$ 的点无论怎么选，答案均为 $\max \limits _{j=1} ^{i-1} [\min(a_j,b_j)]$，可以直接计数 $2^{n-i+1}$ 并跳出循环。注意如果上述情况一直没有发生，那么最后所有点都确定还是可以贡献一个方案的。另外，因为直径端点的颜色谁黑谁白不确定，因此上述对于直径两端点不同色的情况的方案数还要再乘以 $2$。