Contest Info

date: 2018.09.18 16:30-21:30

practice link

Solutions

A. Accommodation Plan

题目大意：

给出一个\(n\le10^5\)个节点的边带权无向树，求选出\(k\)个点的方案数，满足存在一个点到所有选出的点的距离都不超过\(L\)，取模。

题解:

对于每个方案只在到这些点的距离都不超过\(L\)的深度最小的点处统计。

对于每个点，需要统计多少个点到它的距离不超过\(L\)(记为\(a\))，以及多少个点到它和它父亲的距离都不超过\(L\)(记为\(b\)).

答案就是\(\sum \binom{a}{k} - \binom{b}{k}\).

\(a\)可以点分治计算，\(b\)可以考虑计算\(a-b\)，就是子树中到它距离在\([L-w,L]\)(\(w\)为它和父亲连边的权值)的点数。

时间复杂度\(O(n\log^2{n})\).

B. Card Game

签到题。

C. The Most Expensive Gift

题目大意：一个仅有 \(a,b,c\) 组成的字符串 \(S\)，定义它的子序列 \(T\) 的价值为 \(\displaystyle \frac{\text{len}_T^2}{c_T}\)。其中 \(\text{len}_T\) 是 \(T\) 的串长，\(c_T\) 是 \(T\) 的最短循环节长度，且 \(c_T\mid \text{len}_T\)。

题解：考虑长度为 \(x\) 的循环节，它出现了 \(y\) 次，那么答案为 \(xy^2\)。当 \(x=9\) 的时候，一定存在一个字母在该循环节中出现 \(3\) 次，考虑这个字母单个字母作为循环节，那么 \(x'=1,y'=3y\)，可得 \(x'y'^2=(3y)^2=9y^2\)。所以长度大于等于 \(9\) 的都不会更优，我们只需要枚举所有长度小于等于 \(8\) 的串作为循环节即可。

D. Cut the Cake

签到题。

F. Bad Word

题目大意：对一个字母串进行操作，每次可以删掉一个非回文的子串，最多删多少次可以全删完。

题解：猜测了一下，如果有解，那么解最大是 \(2\)。

G. Zenyk, Marichka and Interesting Game

题目大意：有 \(n\) 堆石子，先手只能取 \(A\) 个，后手只能取 \(B\) 个，不能取者输，问胜负情况。

题解：定义 \(f(x)=x\mod{A+B}\)，我们证明 \(x_{1},\cdots,x_{n}\) 与 \(f(x_{1}),\cdots,f(x_{n})\) 的胜负态相同。我们使用归纳法证明。

当 \(x_{1},\cdots,x_{n}<A+B\) 时，容易证明两人都从最大的石子堆取最优。这种情况下的胜负态可以直接求出。

若 \(f(x_{1}),\cdots,f(x_{n})\) 是胜态，那么至少存在一个 \(f(x_{i})\ge A\)，且 \(f(x_{1}),\cdots,f(x_{i})-A,\cdots,f(x_{n})\) 为负态。那么对于原问题也可以取 \(x_{i}\) 这堆石子，显然取完后是个负态。因此 \(x_{1},\cdots,x_{n}\) 也为胜态。

若 \(f(x_{1}),\cdots,f(x_{n})\) 是负态，若先手取的石子堆 \(x_{i}\ge A+B\)，那么后手可以从同一堆中取，转移到一个负态。若先手取的石子堆 \(x_{i}<A+B\)，由于 \(f(x_{1}),\cdots,f(x_{n})\) 是负态，那么取完后必然是胜态。因此不论先手怎么取都只能转移到胜态。

I. Slot Machine

题目大意：若干个盒子，每个盒子里面有一些带颜色的小球。每次可以选择一个盒子，然后从里面随机获得一个球。问最坏情况下需要多少次选择，才能拿到两个同色球。

题解：第一种情况，如果一个盒子里面有两个同色球，那么我们可以一直选择这个盒子，答案是颜色种数加一。

第二种情况，我们枚举一个盒子，作为第一次选择的盒子，然后枚举里面的每个颜色，假设这个颜色是从这个盒子中拿到的，然后找到含这个颜色球的颜色种数最小的其他盒子。然后模拟最坏情况即可。

J. Half is Good

题目大意：略

题解：可以看到 \(w\) 只有 \(62\) 位，我们把前 \(22\) 位分组，然后接着的 \(32\) 位暴力 sort。最后 \(8\) 位影响答案的概率很小。

K. Dance

题目大意：数轴上有 \(n\le100\) 个整点，坐标范围在 \([1,100]\)。现在将每个点向左或向右移动 \(d\le50\) 的距离。定义一个点集的代价为 \(a+b(r-l)\)，其中 \(l,r\) 为点集中的最左、最右点的坐标，总代价为所有不同划分方法下点集代价和的最小值。求所有移动方案下最小的总代价。

题解：不妨固定一个移动方案，设该方案下的点集为 \(S\)，我们证明：\(S\) 最小的总代价等于 \(\min_{S\subset T}f(T)\)，其中 \(f(T)\) 表示将 \(T\) 划分为若干个集合，每个集合是连续的一段，所有不同划分方法下的最小代价。其中代价是 \((a-b)\text{段数}+b|T|\)。

首先显然有 \(S\) 最小的总代价一定是将 \(S\) 划分为几个连续的区间。那么我们可以将这些区间填满，得到的集合一定有 \(S\subset T\)。因此 \(S\) 最小的总代价大于等于 \(\min_{S\subset T}f(T)\)。

而对于所有的 \(S\subset T\)，我们可以先将 \(T\) 的划分中不属于 \(S\) 的元素去掉，将属于同一集合的元素在 \(S\) 中划分在一起。这样代价不会变大。因此 \(S\) 最小的总代价小于等于 \(\min_{S\subset T}f(T)\)。

因此我们相当于要求出 \(\min_{T}f(T)\)，其中 \(T\) 包含了某个移动方案作为子集。为了讨论方便我们先将原坐标减去 \(d\)，那么移动就变成了不变或向右移动 \(2d\)，之后用 \(d\) 表示原先的 \(2d\)。那么显然不满足要求的集合是这样的：存在一个 \(x\)，在移动前 \(x\) 位置有一个点，但是 \(x\notin T\land x+d\notin T\)。

考虑从左到右 \(dp\)，如果我们要在某个位置上放一个点，且前面已经有了一个点，那么若 \(a<b\)，则把这个新点作为独立的一段最优；若 \(a\ge b\)，则把它和前一个点放在一起最优，这样很容易转移。如前所述，为了去掉非法的集合，我们需要知道前 \(d\) 个位置的状态，因此需要用一个 \(2^{d}\) 的状压 \(dp\) 来做，这对于较大的 \(d\) 无法做到，考虑另一种方法。

注意到相互影响的位置之间都相差 \(d\)，因此我们可以按照模 \(d\) 的余数分组 \(dp\)。我们枚举余 \(0\) 的位置有哪些位置有数，之后依次从 \(1\) 转移到 \(d-1\)。这里有一个巧妙的转移技巧，设当前从余 \(i\) 转移到 \(i+1\)，正在填位置 \((i+1)d+j\)，设当前的状态为 \(S\)，那么 \(S\) 的前 \(j-1\) 位记录的是余 \(i\) 的信息，剩余的是余 \(i+1\) 的信息。设转移到的状态为 \(S'\)，那么 \(S'\) 的前 \(j\) 位记录的是余 \(i\) 的信息，剩余的是余 \(i+1\) 的信息。当然这对较小的 \(d\) 时间复杂度会过高。

L. Impress Her

题目大意：一个 \(n\times m\) 的矩阵，矩阵中每种数都是四连通的。定义一种数的凸包是包含它的最小矩形。问有多少对数 \((a,b)\) 满足 \(a\) 的凸包包含了 \(b\) 的凸包（允许边界重合）。

题解：由于每种数都是四连通的，因此 \(i\) 的凸包的大小至多是 \(\min\{n,m\}\times\text{cnt}_{i}\)。所以所有数的凸包大小的和是 \(\mathcal{O}(nm\min\{n,m\})\) 的。我们直接暴力对每个数求出它的凸包包含了哪些数的凸包。我们可以数出凸包内部有多少种数，然后再减去凸包边界上和外面相连的有多少种数即可。

时间复杂度 \(\mathcal{O}(nm\min\{n,m\})\)。

Dirt Replay