Contest Info

date: 2018.10.04 12:40-17:40

practice link

Solutions

A. Number Theory Problem

签到题。

B. Hemi Palindrome

题目大意：定义一个 \(01\) 串是半回文的，当且仅当它的所有奇数位是回文的或所有偶数位是回文的。求第 \(k\) 个 \(n\) 位的半回文串。

题解：数位 \(dp\;+\) 容斥。实现时需要注意各种细节。

C. Mr. Panda and Strips

题目大意：给定一个序列 \(\{c_i\}\) 要求把它划分成若干个区间，然后从中选择一个，或者选取两个然后拼接起来形成一个新区间。要求这个新区间中没有重复元素，问它最长能多长。

题解：预处理 \(f[l][r]\) 表示区间 \([l,r]\) 中最长的没有重复元素的子区间的长度。我们枚举第一个区间的左端点 \(l\)，令 \(r\) 表示它往右最大的合法的右端点的位置。我们把 \([l,r]\) 中的元素在 \([r+1,n]\) 中删除，那么右边被分成若干个区间，它们的 \(f\) 值的最大值加上 \(r-l+1\) 可以更新答案。

然后我们把 \(r\) 往 \(l\) 缩，就变成了若干区间的并，我们用并查集维护。复杂度 \(\mathcal{O}(n^2\alpha(n))\)。

D. Ice Cream Tower

题目大意：定义一个塔是一个序列 \(A_0, \dots, A_{k-1}\) 其中 \(A_{i-1}\times 2\leq A_i\)。给你一个序列 \(\{a_i\}\)，和塔的高度 \(k\)，问你最多能组成多少座塔。

题解：二分塔的数量，然后贪心一层一层放，正确性显然。

E. Bet

题目大意：有 \(n\) 只队伍在比赛，每个队伍有一个比例 \(a_{i}:b_{i}\)。一个人在赌博，设他给第 \(i\) 只队下注 \(x_{i}\) 元。若第 \(i\) 只队赢了，他将收回 \(x_{i}\) 元，并额外获得 \(\frac{b_{i}}{a_{i}}\) 元；如果输了就什么都得不到。现在他想要给若干只队下注，使得只要这些队中至少有一个赢，他就能严格赚钱。求他最多能赌多少只队。

题解：对每只队有 \(\frac{a_{i}+b_{i}}{a_{i}}x_{i}>\sum x_{i}\)。那么我们有 \(\sum\frac{a_{i}}{a_{i}+b_{i}}<1\)。同时我们只要给第 \(i\) 只队下注 \(\frac{a_{i}}{a_{i}+b_{i}}\) 元，那么条件就成立。因此这个条件是充要的。所以我们只要按照 \(\frac{a_{i}}{a_{i}+b_{i}}\) 排序，取前若干个使得和小于 \(1\) 即可。

需要用大整数来避免精度误差。

F. Mr. Panda and Fantastic Beasts

题目大意：给定 \(n\) 个小写字母串，求 \(s_1\) 的最长的子串，使得它不是 \(s_2,\dots,s_n\) 的子串。如果多解，输出字典序最小的。

题解：把这些串用 # 拼起来。然后把第一个 # 后面（含）的所有后缀标记为非法。这个可以拓扑排序做。然后在 parent 树上 dp。

G. Pandaria

题目大意：\(n\) 个点的无向图，点和边都带权。若干次询问，每次询问 \(u, w\)，问仅由边权小于等于 \(w\) 的边连通的图中，\(u\) 所在连通块的点权的众数。

题解：做一次 Kruskal，每次合并的时候新建一个节点，该点的点权为边权。那么每次询问，我们从点 \(u\) 往上倍增地跳到最后一个点权小于等于 \(w\) 的点，它所在子树的点便是所求连通块的点。我们预处理树上线段树合并即可。

H. Great Cells

题目大意：在一个 \(n\times m\) 的网格中，每个位置是 \([1, k]\) 的整数。定义一个位置是 good 的，当且仅当它是该列严格最大的，且它是该行严格最大的。定义 good 个数恰有 \(g\) 个的局面数为 \(A_g\)。求：

\[ \sum_{g=0}^{nm}(g+1)\cdot A_g \mod (10^9 + 7) \]

题解：可以发现：

\[ \begin{aligned} &\sum_{g=0}^{nm}(g+1)\cdot A_g \mod (10^9 + 7)\\ =&\sum g\cdot A_g + \sum A_g \end{aligned} \]

后者就是总局面数 \(k^{nm}\)，而前者即为每个位置是 good 的局面数，也即：

\[ nm\left(\left(\sum_{i=1}^{k-1}i^{n+m-2}\right)\cdot k^{nm-n-m+1}\right) \]

注意 \(n=m=1\) 需要特判。

I. Cherry Pick

题目大意：给你 \(m\) 个互不相同的正整数 \(c_{1},\cdots,c_{m}\)。定义一个整数 \(x\) 的代价 \(f(x)\) 为不小于 \(x\)，且能用这些 \(c\) 组合出（每个数可以用任意个）的最小的整数。求 \(\sum_{i=0}^{n}f(i){n\choose i}p^{i}(100-p)^{n-i}\)。

题解：我们先来研究哪些数能被 \(c\) 表示。设 \(\gcd=\gcd(c_{1},\cdots,c_{m})\)。那么显然不被 \(\gcd\) 整除的整数都不能被表示。不妨设 \(c\) 有序，接下来我们归纳地证明：任意大于等于 \(c_{m-1}c_{m}\)，且能被 \(\gcd\) 整除的整数都能被表示。

\(m=2\) 时，设 \(x\ge c_{1}c_{2},\gcd\mid x\)。那么方程 \(c_{2}t\equiv x\pmod{c_{1}}\) 显然有解。那么对于一个 \(0\le t<c_{1}\) 的解，显然 \(c_{1}\cdot\frac{x-tc_{2}}{c_{1}}+c_{2}\cdot t\) 就是一种组合方案。

\(m>2\) 时，若 \(\gcd(c_{1},\cdots,c_{m-1})=\gcd\)，那么结论已经成立。否则，方程 \(c_{m}t\equiv x\pmod{\gcd(c_{1},\cdots,c_{m-1})}\) 显然有一个 \(\displaystyle{0\le t<\frac{\gcd(c_{1},\cdots,c_{m-1})}{\gcd}}\) 的解。因为 \(c_{m-2}\neq c_{m-1}\)，所以 \(c_{m-2}\le c_{m-1}-\gcd(c_{1},\cdots,c_{m-1})\)。因此 \(x-tc_{m}=c_{m}(c_{m-1}-t)\ge c_{m-2}c_{m}\ge c_{m-2}c_{m-1}\)。结论也成立。

因此，我们可以先假设所有被 \(\gcd\) 整除的整数都能被表示。这样我们只需要求出上式中模 \(\gcd\) 余 \(0,1,\cdots,\gcd-1\) 的项即可计算出答案。这很容易用 \(FFT\) 解决。对于小于 \(c_{m-1}c_{m}\) 的，我们直接背包求出能被表示的整数，修正一下答案即可。

J. Mr. Panda and TubeMaster

题目大意：给定一个 \(n\times m(n,m\leq 30)\) 的网格，有一些格子做了标记。现在让你在一些格子中放 L 型（可以若干次 \(90\) 度旋转，共四种）的管子。要求满足：1.做标记的格子一定有管子。2.每个管子必须在一个环中。连通两个格子的公共边有一个分数（分数 \(\in [-500, 500]\)），最大化得分。

题解：二分图最大权匹配。我们把点黑白染色，每个点拆成入和出两个点。也即二分图两部各有 \(n\times m\) 个点。我们定义如果黑点有管子，那么从两侧进，上下出。如果白点有管子，那么从上下进，左右出。如果一个格子没有做标记，那么它可以向自己连边，表示它自身是一个环。用 km 算法求最大权匹配即可。对于不存在的边我们赋一个极小的值（比可能的最小答案更小的值），然后判断这样的边是否在匹配中以判断是否无解即可。

K. Justice Rains From Above

题解：空间中有一点 \(P(x,y,z)(z>0)\)，平面 \(xOy\) 上有 \(n\) 个互不相同的点。问以 \(P\) 为顶点，锥角为 \(2\alpha\) 的圆锥体至多能覆盖多少个平面上的点。

题解：对于平面上的每个点，所有能覆盖它的圆锥的轴也是一个以 \(P\) 为顶点，锥角为 \(2\alpha\) 的圆锥体。因此题目等价于这 \(n\) 个圆锥体相交的地方最多是多少个圆锥相交形成的。与平面上的圆交类似，我们采用扫描线法。

对于 \(A,B\) 两个点，设 \(\angle APB=\theta\)，若 \(\theta>2\alpha\)，显然这两个圆锥不相交。否则，我们考虑求它们的两条交线所在平面与平面 \(APB\) 的二面角。

我们不妨将 \(APB\) 旋转到 \(yOz\) 平面上，且使 \(PA\) 和 \(PB\) 关于 \(z\) 轴对称。那么有 \(A(0,-\sin\frac{\theta}{2},\cos\frac{\theta}{2})\)，\(B(0,\sin\frac{\theta}{2},\cos\frac{\theta}{2})\)。交线显然经过原点，且在 \(xOz\) 平面上。不妨求 \(x\) 轴负方向的那条交线，设它的坐标为 \((-1,0,k)\)，且有这条交线与 \(PA\) 和 \(PB\) 成 \(\alpha\) 度角。因此可以解得 \(\displaystyle{k=\sqrt{\frac{\cos^{2}\alpha}{\cos^{2}\frac{\theta}{2}-\cos^{2}\alpha}}}\)。有了它之后，二面角也就可以暴力算出来了。

之后我们旋转 \(A\) 所对应的圆锥，使得它的轴对应 \(z\) 轴。这样我们就可以求出其它所有圆锥与它相交的角度区间。这里的角度是指交点在 \(xOy\) 平面上的投影与 \(x\) 轴成的角。

L. World Cup

签到题。

Dirt Replay

B: -1 写错了，爆 ll

D: -2 数组大小开反了

E: -4 c++爆精度；java 小数类爆精度；下标写错RE；输出 println 还多输出了换行符

G: -1 离散化输出的时候没还原