Contest Info

date: 2018.10.13 13:40-18:40

practice link

Solutions

A. Boxes and Balls

签到题。

B. Business Cycle

题目大意：

有一个\(n\le10^5\)个点的环，从\(0\)到\(n-1\)编号。

每个点有一个权值\(v_i\)，绝对值不大于\(10^9\).

初始携带一定的金钱\(x\ge0\)，从位置\(0\)开始，每走一步会从当前位置\(i\)移动到\(i+1\pmod{n}\)，并获得\(v_i\)的金钱（为负数则失去其绝对值的金额），如果身上携带的金额小于\(0\)，会被立即修正为\(0\).

在最多走\(P\le10^{18}\)步的情况下（可以一步都不走），要获得至少\(G\le10^{18}\)的金钱，初始携带的金额最少为多少？

题解：

分两种情况讨论：

会用到负数修正的情况，那么在修正之后，之前携带的金额都归零，也就是说初始时携带大于\(0\)的金额是没有意义的。

这种情况我们暴力走一个环，判断中途是否满足条件，否则用最后的金额数\(x\)作为初始携带的金额数且不允许修正地再走一圈，若还没有达到\(G\)，如果现在剩下的金额可以不用修正地走完一圈且走一圈的收益为正，我们会贪心地绕圈，直到剩余不足两个周期.

然后取剩余部分的最大前缀和即可。

不会用到负数修正的情况，则在走不到一圈的时候，答案要与对应前缀的最小值的相反值取\(max\)，当走一圈有正的收益时，一样会继续贪心绕圈，直到剩余不足两个周期，同时要与一个周期内的前缀的最小值的相反值取\(max\).

注意绕圈的部分得到的收益会爆long long，需要使用__int128.

复杂度\(O(n)\).

C. Suffixes and Palindromes

题目大意：

给出一个长度为\(n\le10^5\)小写字母串的后缀数组和manacher数组，求合法的字典序最小串或者判断其不合法。

题解：

对于manacher数组，模拟一遍manacher，将其中的相等关系用并查集合并，不等关系建无向边，只会有\(O(n)\)个关系。

然后将相等的缩点，从\(sa[1]\)开始确定各个位置，首先\(sa[1]\)肯定选择字符\(a\)，然后决定\(sa[i]\)时，若\(rk[sa[i]+1]<rk[sa[i-1]+1]\)，或者不等关系中含有当前最大的字符，这一位一定要填更大的字符。

如果枚举到大于\(z\)的字符也不合法。

时间复杂度\(O(n)\).

D. Change

签到题。

E. Colorful Floor

题目大意：用一个 \(r\times c\) 的网格密铺整个平面。用 \(k\) 种颜色给这个网格染色。现在给出这 \(k\) 种颜色的一个排列 \(\{p\}\)，定义合法的染色方案为，将颜色 \(i\) 替换成颜色 \(p_{i}\) 以后看起来不变。求所有本质不同的合法方案数（即不论怎么平移都不相同）。

题解：按照 \(burnside\) 引理，答案即为 \(\displaystyle{\frac{\sum_{u=0}^{r-1}\sum_{v=0}^{c-1}f(u,v)}{rc}}\)，其中 \(f(u,v)\) 是将网格纵向平移 \(u\) 格，横向平移 \(v\) 格后保持不变的合法方案数。容易证明，\(\sum_{u=0}^{r-1}\sum_{v=0}^{c-1}f(u,v)\) 与 \(\sum_{u=0}^{r-1}\sum_{v=0}^{c-1}g(u,v)\) 一一对应，其中 \(g(u,v)\) 是将网格纵向平移 \(u\) 格，横向平移 \(v\) 格，将颜色替换后保持不变的方案数。且注意到 \(g(u,v)=g(\gcd(u,r),\gcd(v,c))\)，因此答案为 \(\displaystyle{\frac{\sum_{u\mid r}\sum_{v\mid c}\varphi(\frac{r}{u})\varphi(\frac{c}{v})g(u,v)}{rc}}\)。

注意到在平移 \((u,v)\) 的情况下，每个数会被平移到 \(\text{lcm}(\frac{r}{u},\frac{c}{v})\) 个位置。要满足将颜色替换后保持不变，这 \(\text{lcm}(\frac{r}{u},\frac{c}{v})\) 个位置应当恰好是 \(p\) 的某个循环节重复若干次。设 \(h(x)\) 表示 \(p\) 中所有长度为 \(x\) 的约数的循环节的长度之和，那么

\[ g(u,v)=h(\text{lcm}(\frac{r}{u},\frac{c}{v}))^{\frac{rc}{\text{lcm}(\frac{r}{u},\frac{c}{v})}} \]

F. Hungry Game of Ants

签到题。

G. Legacy of the Void

题目大意：给一棵 \(n\) 个结点的树，树上每个点有一个点权 \(w_{i}\) 和一个概率 \(p_{i}\)。每次先等概率地选取树的一个连通块，然后连通块中的每一个点被选取的概率为 \(p_{i}\)，该次选取的代价为所有被选的点的权值和。现在选取 \(Q\) 次，将这 \(Q\) 个代价排序，问第 \(K\) 小的代价的期望。

题解：答案相当于 \(\sum_{i=1}^{+\infty}P(X\ge i)\)，其中 \(X\) 是第 \(k\) 小的代价的随机变量。而容易发现 \(P(X\ge i)\) 等价于小于 \(i\) 的代价小于 \(K\) 个。那么我们现在只需把每次选取的概率分布求出即可。

考虑一个连通块 \(S\)，它的概率生成函数即为：\(\prod_{u\in S}(1-p_{u}+p_{u}x^{w_{u}})\)。考虑在树上 \(dp\)，设 \(dp[u]\) 表示在 \(u\) 的子树中选取连通块，且 \(u\) 必选的所有连通块的概率生成函数之和。那么 \(dp[u]=(1-p_{u}+p_{u}x^{w_{u}})\prod_{u\to v}(1+dp[v])\)。用 \(FFT\) 加速即可。

时间复杂度 \(\mathcal{O}(n\sum w_{i}\log\sum w_{i}+Q\log Q\sum w_{i})\)。

H. Open Face Chinese Poker

题目大意：

打\(52\)张的扑克，不含大小王。

初始有\(14\)张手牌，选一张扔掉，再选三张作为第一手，再选五张作为第二手，剩下的为最后一手。

给出三张牌和五张牌的组合，如Royal Flush，Full House等，给出不同种组合之间的等级和同一种组合之间比较大小的方法，规定第一手不能大于第二手，第二手不能大于最后一手。

再给出每一手打出的牌的分值计算方法，问最大的得分和可以是多少。

题解：

首先枚举大小为\(3\)和\(5\)的子集预处理出是什么组合和用来比较的数组。

然后dfs将手牌分为\(1\)，\(3\)，\(5\)，\(5\)三堆，然后比较大小判断合法，合法则计算总分更新答案即可。

I. Champions League

题目大意：给你 \(32\) 支球队，它们分别来自某些国家，且被分成了 \(4\) 个等级，每个等级 \(8\) 只队。现要将它们分为 \(8\) 组 \(A\sim H\)，要求如下：

• 从等级 \(1,2,3,4\) 开始依次分组，但是组内分配的顺序可以随意。同等级的不能分在一组。

• 同一个国家的球队不能分在一组。

• 分配某只球队时，若 \(A\sim D\) 组及 \(E\sim H\) 组中已分配的它所在国家的球队一样多，那么这只球队可以随意分配，否则要将它分配到数量较少的那个部分去。

题解：状压 \(dp\)，按照国家依次填入，转移暴力即可（即可？）。看起来状态有 \(2^{32}\) 个，但是由于填完每个国家之后，每个等级的数量都已经确定了，因此每个国家的状态最多只有 \({8\choose 4}^{4}\) 个。

数据是假的吧。。我本地样例都要 \(5s\)，结果最后 \(1s\) 多？？？

J. Dome and Steles

题目大意：给你 \(n\) 个宽为 \(1\) 的长方体，要你将它们按照某种顺序排列起来，可以交换长和高，使得覆盖它们的半球的半径最小。

题解：二分答案。显然一个长方体在半球内，相当于它的顶点在半球内。对于每个长方体，假设它放在原点，我们可以列出圆心坐标范围的一个二次不等式，它的解是一个区间。而对于放在 \(i\) 的长方体，它的范围要加上 \(i\) 的偏移。那么现在问题就变成要找一个排列使得这 \(n\) 个区间加上偏移后尽可能有交。感受一下可以发现，从中间到两边区间长度逐渐增长是最优的，贪心即可。

K. Convex Polyhedron

题目大意：给你一个 \(n\) 个点的三维凸包，你可以任意旋转它。现在阳光从正上方直射，问最大的阴影面积。

题解：首先我们可以 \(\mathcal{O}(n^{4})\) 地把所有面求出来，只需要枚举三个点，判断是否所有点都在这个面的一侧即可。

假设我们已经枚举出了所有向阳的面，设 \(\vec{o_{i}}\) 是向阳面 \(i\) 的法向量，\(S_{i}\) 是 \(i\) 的面积。那么 \(i\) 在地面上的阴影面积为： \[ \begin{aligned} &S_{i}\cdot\cos\langle(0,0,1),\vec{o_{i}}\rangle\\ =&S_{i}\frac{(0,0,1)\cdot\vec{o_{i}}}{|\vec{o_{i}}|}\\ =&(0,0,1)\cdot S_{i}\vec{e_{i}} \end{aligned} \] 其中 \(\vec{e_{i}}\) 是 \(\vec{o_{i}}\) 的单位向量。那么最终的答案即为 \((0,0,1)\cdot\sum_{i}S_{i}\vec{e_{i}}\)。

注意到我们旋转凸包，相当于整体旋转 \(\sum_{i}S_{i}\vec{e_{i}}\) 这个向量。因此上式取最大值时显然是当 \(\sum_{i}S_{i}\vec{e_{i}}\) 与 \((0,0,1)\) 同向的时候，即为 \(|\sum_{i}S_{i}\vec{e_{i}}|\)。

枚举向阳的面可以随机若干个平面，在它上面的是向阳，取最大值即可。

tips：数据范围 \(10^{9}\) 还有 \(3\) 位小数，用 double 真是心大啊。

L. Multiplication Table

题目大意：定义无穷矩阵 \(A_{ij}=i\times j\)。给出一个 \(n\times m\) 的矩阵，其中一些位置未知，问它是否可能是 \(A\) 的子矩阵。

题解：若有某行或某列有超过一个元素，那么矩阵可能的位置就唯一确定了，验证一下即可。

若每行每列都只有至多一个元素，那么可以将任意一个位置质因数分解后验证。这种情况下的时间复杂度为 \(\mathcal{O}(1344\min\{n,m\})\)。

M. November 11th

分类讨论，签到题。

Dirt Replay