Contest Info

date 2017.08.10 12:00-17:00

practice link

Solutions

A. String

题目大意：给定一个有 \(n\) 个单词的字典。给出 \(q\) 次询问，每次询问给出两个字符串 \(pre\) 和 \(suf\)，输出字典中有多少个单词以 \(pre\) 为前缀，以 \(suf\) 为后缀，并且不重叠。

题解：设字典中的单词为 \(s_1, s_2, \dots, s_n\)。构造一个串 \(S= \text{#}s_1\text{@}s_1\text{#}\cdots \text{#}s_n\text{@}s_n\text{#}\)。建立这个串的后缀自动机，并求出 parent 树的 dfs 序，用树状数组维护 dfs 序。每次询问的时候找到串 \(suf\text{@}pre\) 对应的结点，求出子树和。

再考虑如何处理重叠的情况。很容易发现只有单词的长度小于 \(len(pre)+len(suf)\) 的时候，才会出现重叠。我们把单词和询问都按照长度排序，枚举询问，在树状数组中删除不符合条件的单词。

有一个在线的做法，我们枚举每个长度，对小于等于这个长度的单词建立一个可持久化线段树维护 dfs 序。

B. Mindis

题目大意：给你一个圆心在原点，半径为 \(r\) 的 \(\odot O\) 和不在圆外的两点 \(P, Q\) ，保证 \(OP = OQ\)。求圆上一点 \(D\)，最小化 \(PD+QD\)。

题解：

法一：把两个点旋转一下再把圆和它们整体向下平移，让两个点落在 \(x\) 轴左右两边对称的地方。设此时 \(P(-x,0),Q(x,0),O(0,-d)\) 。到 \(P,Q\) 距离和相等的点的轨迹是一个椭圆（可能退化成一条线段），画图易知椭圆和圆相切时距离最小。显然椭圆和圆在它们的切点处和同一条直线相切，设切点为 \((x_{0},y_{0})\) 。

设 \(PD + QD = c\) ，则椭圆的方程为 \(\frac{x^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}=1(a^{2}=\frac{c^{2}}{4},b^{2}=a^{2}-x^{2})\) 。两条切线为 \(x_{0}x+(y_{0}+d)(y+d)=r^{2}\) 和 \(\frac{x_{0}}{a^{2}}x+\frac{y_{0}}{b^{2}}y=1\) ，若 \(x_{0}\not=0\) ，对比系数有

\[ \left\{ \begin{aligned} &\frac{a^{2}y_{0}}{b^{2}}=y_{0}+d\\ &a^{2}=r^{2}-(y_{0}+d)d\\ \end{aligned} \right. \]

由第一个方程可得 \(y_{0}=\frac{db^{2}}{a^{2}-b^{2}}\) ，代入第二个方程可得

\[ \begin{aligned}\\ a^{2}&=r^{2}-(\frac{db^{2}}{a^{2}-b^{2}}+d)d\\ a^{2}&=r^{2}-\frac{d^{2}a^{2}}{x^{2}}\\ a^{2}&=\frac{x^{2}r^{2}}{x^{2}+d^{2}}\\ c&=\frac{2xr}{\sqrt{x^{2}+d^{2}}}\\ \end{aligned}\\ \]

这样就解出了 \(c\) ，即为答案。但是这样还存在问题，因为可能产生增根，我们注意到 \(y_{0}\) 要满足 \(y^{2}_{0}\le b^{2}\) ，即

\[ \begin{aligned}\\ \frac{d^{2}b^{4}}{x^{4}}&\le b^{2}\\ b^{2}&\le\frac{x^{4}}{d^{2}}\\ \frac{x^{2}{r^{2}}}{x^{2}+d^{2}}-x^{2}&\le \frac{x^{4}}{d^{2}}\\ rd&\le x^{2}+d^{2}\\ \end{aligned}\\ \]

若不满足这个不等式，则易证它们必然在 \((0,r-d)\) 相切，答案即为 \(2\sqrt{x^{2}+(r-d)^{2}}\)

法二：（题解做法）找到 \(P,Q\) 关于 \(\odot O\) 的反演点 \(P',Q'\) ，则对于圆上任意一点 \(D\) 有 \(\triangle DOP \sim \triangle P'OD\) ，相似比为 \(\frac{OP}{r}\) ， 对 \(Q\) 同理。因为 \(OP=OQ\) ，所以 \(PD+QD=\frac{OP}{r}(P'D+Q'D)\) ，我们只需要找 \(P'D+Q'D\) 的最小值就行了，而 \(P',Q'\) 都在圆外且与圆心距离相等，所以找最小值就很简单了。如果 \(P'Q'\) 和 \(\odot O\) 相交或相切，那么 \(D\) 在交点或切点时 \(P'D+Q'D\) 取最小值，否则在 \(P'Q'\) 的中垂线和圆的交点中离 \(P'Q'\) 较近的那个点处取得最小值。

需要注意两点重合或者都在圆上的特殊情况。

C. Inversion

题目大意：给出一个长度为 \(2\leq n\leq10^5\) 的数组 \(A\)，\(1\leq A_i \leq 10^9(1\leq i\leq n)\)。数组 \(B\) 满足 \(B_i=\max\limits_{i \not\mid j} A_j\)，\(2\leq i \leq n\)。输出 \(B\) 数组。

题解：先将 \(A\) 数组带着下标排个序，然后枚举 \(i\) 再从大到小去找第一个不被 \(i\) 整除的 \(j\)，则 \(B_i=A_j\)。时间复杂度 \(\mathcal{O}(n\log n)\)。

F. Gumballs&Dungeons

题目大意：一个人在一个迷宫中冒险，迷宫中有 \(7\) 个怪物和一些 \(buff\) ，这个人还可以通过使用魔法来获得能力值的提升，问在把所有怪物杀死的前提下，这个人能获得的最大 \(HP\)。（更多细节请阅读原题。）

题解：（题解的做法）首先容易得到这样两个结论：先使用魔法 \((吃buff)\) 再打怪一定比先打怪再使用魔法更优，攻击大于等于 \(20\) 时攻击怪物产生的效果相同（防御同理）。我们设 \(dp[state][i][j]\) 表示当前已经杀死了 \(state\) 中的怪物并且吃到了所有能吃到的 \(buff\) ，用光了魔法后，攻击为 \(i\) ， 防御为 \(j\) 时 \(HP\) 的最大值。由于迷宫中有障碍和未攻击的怪物阻挡，每个状态下不一定能攻击到所有剩余的怪物或者拿到所有剩余的 \(buff\) ，对于每种状态下能够攻击的怪物和能拿到的 \(buff\) ，容易通过 \(dfs\) 来预处理，同时根据结论 \(2\) ，使用魔法时，攻击和防御最多分别用 \(20\) 次即可，其它都用在 \(HP\) 上。那么转移方程为：

\[ \begin{aligned}\\ &dp[state\cup\{k\}][min(20,i+\Delta ATK)][min(20,j+\Delta DEF)]=max( this, dp[state][i][j]-hurt+\Delta HP)(state 下能够攻击到 k 且 dp[state][i][j]>hurt)\\ &\Delta ATK = 攻击buff加成+i'*攻击魔法加成(0\le i' \le 20)\\ &\Delta DEF = 防御buff加成+j'*防御魔法加成(0\le j' \le 20)\\ &\Delta HP = HPbuff加成+(魔法最大使用次数-i'-j')*HP魔法加成\\ &上面的buff加成和魔法最大使用次数均指杀死k之后新开的区域中能得到的东西 \end{aligned}\\ \]

G. GCDispower

题目大意：给你一个 \(1\sim n\) 的排列，并给你 \(m\) 个询问。每次询问给你一个 \([l,r]\) ，问 \(\sum_{i=l}^{r}\sum_{j=i+1}^{r}\sum_{k=j+1}^{r}[gcd(p_{i},p_{j})=p_{k}]\cdot p_{k}\) 。

题解：对于每一对满足 \(gcd(p_{i},p_{j})=p_{k}(i<j<k)\) 的三元组 \((i,j,k)\) ，我们当作它给 \(i\) 这个位置贡献了 \(p_{k}\) 的答案。容易发现对一个 \([l,r]\) ，答案就是把所有小于等于 \(r\) 的三元组的贡献计算完后， \([l,r]\) 的区间和。因此我们离线处理所有询问，对 \(r\) 从小到大排序，依次处理每个 \(r\) 加入时新产生的贡献，并用一个树状数组维护。

现在我们考虑加入 \(r\) 时新产生的贡献，也即满足 \(gcd(p_{i},p_{j})=p_{r}(i<j<r)\) 的 \((i, j, r)\)。因此我们只需要处理 \(r\) 左边的 \(p_{r}\) 的倍数即可。这部分的复杂度是我们熟知的 \(\mathcal{O}(n\log n)\) 。为叙述方便，我们假设这些数和 \(p_{r}\) 仍然占据了所有 \([1,r]\) 的下标。现在对于每个 \(i\in [1,r)\) ，它的贡献就是 \([i+1,r)\) 中和 \(p_{i}\) 的 \(gcd\) 为 \(p_{r}\) 的数个数乘以 \(p_{r}\) 。由容斥原理容易知道 \(\displaystyle ans=p_{r}\sum_{\displaystyle j|\frac{p_{i}}{p_{r}}}\mu(j)\sum_{k=i+1}^{r-1}[(j\cdot p_{r})|p_{k}]\) ，因此我们只需要从右往左扫，一边统计答案，一边更新对所有的 \(j, j\cdot p_{r}\) 的倍数的个数就可以了。主要的瓶颈在复杂度分析， 这题容斥部分的复杂度为

\[ \begin{aligned}\\ &\sum_{i=1}^{n}\sum_{i|d}\sigma(\frac{d}{i})\\ =&\sum_{i=1}^{n}\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}\sigma(j)\\ =&\sum_{i=1}^{n}\mathcal{O}(\frac{n}{i}\log(\frac{n}{i}))\\ =&\mathcal{O}(n\log^{2}n)\\ \end{aligned}\\ \]

因此是可以通过本题的。比赛时分析成了 \(\mathcal{O}(n^{2})\) 直接没尝试写。

H. Kirinriki

题目大意：定义两个长度为 \(n\) 的串 \(A,B\) 的距离为 \(\text{dis}_{A,B}=\sum_{i=0}^{n-1}\mid A_i - B_{n-1-i}\mid\)。给你一个串 \(S\)，求两个不相交的子串，使得它们的距离不大于 \(m\)，并且长度最长。求这个最长长度。

题解：假设我们已有了两个最优的子串。我们将它们同时往两边延伸，那么结果只会有两种 \([1, i]\) 或者 \([j, n]\)。于是我们枚举所有的 \([1,i],[j,n]\)，往里缩，用 two-pointer 维护距离不超过 \(m\)。复杂度 \(\mathcal{O}(n^2)\)。

题解的做法是枚举中心，往外延伸，是差不多的思想。

J. Gameia

题目大意：Alice 和 Bob 一起玩游戏。一开始有一棵节点未染色的树， Bob 可以在游戏的任意时刻断开树上的一条边，最多断开 \(K\) 次。游戏开始之后，两人交替进行操作， Alice 先手：

• 在 Alice 的回合，她可以选择一个未染色的点，将其染为白色
• 在 Bob 的回合，他可以选择一个未染色的点，将其染为黑色，并且将与该点相邻的点重新染为黑色（不管之前是否染色）

不能操作的时候游戏结束。如果最后剩余有任何的白色结点，那么 Alice 获胜，否则 Bob 获胜。问谁必胜。

题解：显然 Bob 在比赛开始之前先断边是等价的。比赛的时候猜了一个结论， Bob 获胜的充要条件为：Bob 必须通过不超过 \(K\) 次断边操作，将树分成若干个连通块，且每个连通块恰有 \(2\) 个点。

下面来详细证明：

• 如果原树不存在两两匹配的方案。Alice 每次选择叶子结点的父亲，那么 Bob 必须选择叶子结点。此时断边操作没有用。某个时刻 Alice 会将一个周围已染色的孤立点染为白色，那么 Alice 获胜。
• 如果原树存在两两匹配的方案。
  • 如果 \(K\) 的大小足以使原树分成若干两个点的连通块，显然 Bob 获胜。
  • 否则， 此时显然有树的结点个数为偶数。又因为存在两两匹配的方案，所以 Alice 可以选择一个父亲结点只有一个子结点的叶子结点。一旦 Bob 用完了断边的机会，那么 Bob 此时会选择父亲节点，从而树结点变成奇数个。此时不存在两两匹配的方案，所以 Alice 获胜。

K. Classes

签到题

L. Typesetting

题目大意：给一份需要插入一张图片的文章排版。行宽为 \(W\)，图片宽度为 \(pw\)，高度 \(h\) 和插入位置未知，图片到左边缘间距为 \(dw\)。在插入的图片所占的 \(h\) 行中，每行被分为左右两个部分，左边能容纳最多 \(dw\) 个字符，右边能最多容纳最多 \(W-dw-pw\) 个字符。并且：

• 单词不能被拆开放到两行，也不能被拆开放在图片左右两边
• 如果两个单词在同一行连续出现，中间间隔恰一个空格
• 不能改变单词的相对位置

给出 \(W,pw,dw\)，现在有一篇有 \(n\leq 10^5\) 个单词的文章，每个单词的字符数 \(1\leq a_i \leq W\)。再给出 \(q(q\leq 10^5)\) 次询问，每次给出图片插入的行 \(x\) （如果直接排版文章所有单词所用的行数 \(y < x-1\)，那么图片实际上只能插入到第 \(y+1\) 行）和图片的高度 \(h\)。求最少总行数。

题解：定义 \(next(x,w)\) 为，从第 \(x\) 个单词开始往 \(w\) 个字符的块中，尽可能多的装单词，第一个不能被装下的单词。即 \(\displaystyle next(x,w)=\min\; y \geq x,\quad s.t. \; (y-x)+\sum\limits_{i=x}^{y} a_i >w\)。可以通过预处理 \(a_i\) 的前缀和二分求解。

定义 \(pre[i]\) 为插入图片前的 \(i\) 行，最多能容纳到第几个单词。显然，\(pre[0]=0\)，\(pre[i]=next(pre[i-1]+1,W)-1\)。

再定义 \(suf[i]\) 为插入图片后的第一个单词为 \(i\) ，至少需要再使用多少行。显然 \(suf[n+1]=0\)，\(suf[i]=suf[next(i,W)]+1\)。

对于有插入图片的这些行，肯定是贪心地依次将左右两边都尽可能装满。对每个单词建两个点：\(i\) 和 \(i+n+1\)，分别表示以 \(i\) 作为插入了图片的某行的左边块的开始和右边块的开始。对于第 \(i\) 个单词，令 \(j=next(i,dw)\)，则连一条 \(j+n+1\) 到 \(i\) 的边；令 \(j_1=next(i,W-dw-pw)\)，则连一条 \(j_1\) 到 \(i+n+1\) 的边。但是，还有几个特殊的情况：如果 \(i=j \land i=j_1\) 说明 \(i\) 太长了，有图片插入的行都无法容纳它，只能从图片后面的行继续放，这种情况我们不连任何边，\(i\) 和 \(i+n+1\) 两个点为根的树独立出来；如果 \(i=j \lor i=j_1\)，正常连边即可。这样就把这个贪心策略转换成了一个森林。

对于每个询问，我们找到 \(pre[x-1]+1\) ，从这个点在对应的树中向上爬最多 \(2h\) 层，就知道了图片后面的第一个单词 \(y\)，那么答案就是 \(x-1+h+suf[y]\)。向上爬的操作我们可以用倍增法来实现。

时空复杂度都是 \(\mathcal{O}(n\log{n})\)。

Replay and Summary

Replay

Z 一来就说 C 是一个 sb 题，然后写了一个 log 方的鬼东西，显然 tle 了。又加了一个输入优化，还是 tle 了，看来题是真的 sb。 D 拿过来想了想觉得可以 log 做，然后拿过来很快过掉了。

W 发现 K 题是一道似乎很简单的题啊，发现跟数学有一点点的关系就交给 Z 了，Z 很快 1a 了。D 和 W 开始看 H 和 A 这两道字符串的题。在 H 卡了很久没想出怎么做。Z 在刚 B 和 G 这两道计算几何和数学题。

W 上了个厕所之后发现 H 挺逗你玩的，直接扫几遍就行了。过了之后继续想 A。A 其实已经想的差不多了，就差处理前后缀交叉的情况。想了想离线排序就可以做了。直接开始写后缀自动机，然后 wa 了之后看了看代码发现很多细节错误，数组开小，以及有一个 ++j 迷之写成 –j。改了之后也过了。

之后就很僵硬了。D 和 Z 在做 J 这道博弈，然后很果断地觉得删边是没有用的，直接不断删掉两个点的链就行了。wa 了很多次。W 决定不能死在这道题上，让 Z 去做 B，让 D 去做 L。

W 画了画发现其实删边是有用的，然后根据出错的那种情况猜了一个结论。改了改之前的代码也过掉了。（还发现 D 之前写的时候没 continue）。Z 疯狂的 tle 和 wa B。W 建议推一推公式，但是 Z 还是觉得尝试一下二分和三分。

D 的 L 也写得差不多了。W 写出了 B 的公式，写了之后过掉了。后面的时间都在辅助 D，D 发现有一个小错误然后开始改，趁着最后交了几发都 wa 了。比赛结束之后再仔细看了看，发现是没有改完，改完的话就 a 了。

（W 觉得以后一定要监督 D 开数组 +10）

coldwater

A 题后缀自动机非主流做法想不到还挺好写的，题解的转成矩形覆盖确实也很讲道理。L 一开始误判为大模拟，结果没看到数据范围，导致 D 不是很敢写。现在想来早点给他的话，应该就能过这题了。D 题读完题感受了一下觉得就是怎么暴力删边，然后 hash 判断树的同构，看过的人太少觉得可能想得太 naive 也没敢写（树同构也不怎么记得了）。B 题大力写了个式子还是比较开心的。

ShinriiTin

越来越摸鱼了，一来接了 C 的锅，然后 A 题给了一点 idea，之后就不停带偏 J 题。然后 W 说 L 是一道大模拟让我去写，我听说是大模拟根本不想写，但是去读了一下之后发现应该是树上倍增搞一下。由于已经是比赛最后阶段，有点方，细节没有处理完，加上访问了数组的 n+1 位置却只开了 max_N+1，就背锅了。结束之后改了一下交了就 a 掉了，真的是唆不粗话。

zhongzihao

一天到晚摸鱼，不知道在干什么，一开始就 T 了两发 C ，不知道怎么就敢写的。然后就水了一道小容斥， 1a 以后开始对着计算几何 B 绝望地 wa 和 tle 了好多好多发（最后还是 W 过的）。中间又穿插着想 G ，其实一会就想出了正解，但是莫名其妙以为是 n 方的算法到最后都没敢写。现在看来应该按照常见的 1-n 所有约数个数的 nlogn 复杂度的分析方法多想想。比赛时上界放得太宽了，或者最次打个表算算到底有多少个也好，不知道在想什么也没去打，实在是很不应该。