Contest Info

date 2017.09.10 12:00-17:00

practice link

Solutions

A. string string string

题目大意：给定一个字符串 \(S\)，和一个正整数 \(k\)，问 \(S\) 有多少个恰好出现 \(k\) 次的子串。

题解：sam 裸题。直接逆拓扑序递推算出每个状态 \(S\) 的 \(|Right_S|\) 即可。

B. cable cable cable

题目大意：给定一个二分图 \(G=(U+V,E)\) 的 \(U,V\)，且 \(|U|=k\), \(|V|=n(k\leq n)\)。让你确定边集 \(E\)，使得 \(\forall U+V',V'\subset V,|V'|=k\) 存在完备匹配。最小化 \(|E|\)。

题解：答案即为 \(k+(n-k)\times k\)。

我们在 \(V\) 中选择 \(k\) 个点（第一类点），向 \(U\) 一一连边。然后剩余的 \(n-k\) 的点（第二类点），向 \(U\) 中的每个点连一条边。我们设 \(V'\) 中有 \(t\) 个来自第一类点，有 \(k-t\) 个来自第二类点，显然这 \(k-t\) 个点可以选择这 \(t\) 个点没有连的 \(U\) 中的点去匹配，于是这样的构造满足要求。如果我们去掉任何一条边，都可以构造出一个不满足要求的 \(V'\)，所以这个构造也是最小的。

C. happy happy happy

题目大意：Bob 和一个小孩玩游戏，小孩先手。给定一个数列 \(\{a_n\}\)，每人每次可以从两端选择一个数字拿走。小孩一定会选择两端中的较大数，如果大小相等，则选择左边一侧的数字。最后得分严格多的人获胜。

Bob 想在自己输的前提下，让小孩的得分减他的得分的差值，尽可能小。求这个差值。\(1\leq n\leq 90,n \text{ is even}\)。

题解：预处理 \(mn[l][r],mx[l][r]\)，分别表示状态为区间 \([l,r]\)，接下来该小孩操作的最小/最大差值。然后就直接卡时爆搜，加上三个剪枝：

if(dif + mx[l][r] <= 0) return;
if(dif + mn[l][r] >= ans) return;
if(dif + mn[l][r] > 0){
	ans = std::min(ans, dif + mn[l][r]);
	return;
}

这题数据太水了，不知道正解该怎么做。还可以用 bitset 优化 dp 卡过。

D. array array array

签到题

E. number number number

题目大意：求最小的不能用 \(k\) 个斐波那契数之和表示的数。

题解：这道题猜起来很简单，但是证明想了挺久，证明非常有趣。

我们证明，对每个数，每次减去最大的不大于它斐波那契数，这样使用的斐波那契数一定是最少的。对一个数（设为 \(t\)）的任意表示方案，我们利用 \(F_{n-1}+F_{n-2}=F_{n} (n\ge2)\) ， \(2F_{n}=F_{n+1}+F_{n-2}(n\ge2)\) ， \(F_{1}=F_{2}\) ， \(F_{0}=0\)不断化简，直到不能操作，容易发现这样不增加表示次数。我们证明这样的操作一定会结束：考虑表示方案的前缀数组（比如 \(2F_{0}+F_{1}+F_{2}\) 为 \((2,3,4,4,\cdots)\)），容易发现每次操作后，前缀数组每一位都不会变大，并且至少有一位严格变小。也就是说，这样的操作方式保证每一步之后都一定不会和之前出现的某个方案相同。由于 \(t\) 是一个有限的数，不同的能表示 \(t\) 的方案显然也是有限的，所以这样的操作一定会结束。

观察结束后的方案，我们发现这个方案有如下性质：\(F_{0}\) 和 \(F_{1}\) 没有出现，每一位至多是 \(1\) ，不存在连续的两个 \(1\) 。我们用归纳法来证明结束方案是唯一的：\(t=0\) 和 \(t=1\) 时显然。 \(t\geq 2\) 时，我们用反证法，假设结束方案不包括不大于 \(t\) 的最大斐波那契数（设为 \(F_{n}\)） ，不妨设 \(n\) 为奇数，那么剩下的数加起来最多是 \(F_{n-1}+F_{n-3}+\cdots+F_{3}<F_{n-1}+F_{n-3}+\cdots+F_{3}+F_{2}=F_{n}\le t\) ，矛盾。 \(n\) 为偶数时同理。我们将归纳假设应用于 \(t-F_{n}\) 上即可证明：结束方案一定是我们之前描述的方案。

既然这样，就说明这种方案的表示次数一定小于等于所有其它的方案，是最小的。这样以后我们就容易知道： \(F_{2k+3}-1\) 不能被 \(k\) 个斐波那契数表示，而比它小的数都可以。

coldwater’s comment

跟 这题 很像。相关 wiki：黄金进制。

F. gems gems gems

题目大意：有一列数，两个人从左到右轮流取数。先手第一次可以取 \(1\) 个或 \(2\) 个数。之后的每个人，设前一个人取的数个数为 \(x\)，那么他可以取 \(x\) 个或 \(x+1\) 个数。不能取数时游戏结束。定义得分为取到的数之和，两人分别设为 \(a,b\)。先手想要最大化 \(a-b\)，后手想要最小化 \(a-b\)。求 \(a-b\) 的值。

题解：dp 。设 \(dp[0/1][i][j]\) 表示上一次是 Alice/Bob 取到了前 \(i\) 个数，且上一次取了 \(j\) 个的最优值，记 \(pre[i]\) 表示前 \(i\) 个数的和。状态转移方程为：

\[ dp[1][i][j]= \begin{cases} &0,&(i+j>n)\\ &dp[0][i+j][j]+(pre[i+j]-pre[i]),&(i+j+1>n)\\ \max\{&dp[0][i+j][j]+(pre[i+j]-pre[i]),\\ &dp[0][i+j+1][j+1]+(pre[i+j+1]-pre[i])\},&(\text{others})\\ \end{cases} \]

\[ dp[0][i][j]= \begin{cases} &0,&(i+j>n)\\ &dp[1][i+j][j]-(pre[i+j]-pre[i]),&(i+j+1>n)\\ \min\{&dp[1][i+j][j]-(pre[i+j]-pre[i]), \\&dp[1][i+j+1][j+1]-(pre[i+j+1]-pre[i])\},&(\text{others})\\ \end{cases} \]

最后答案为 \(dp[1][0][1]\)。实际上 \(j\) 只有 \(\mathcal{O}(\sqrt i)\) 级别。

G. mustedge mustedge mustedge

题目大意：给出一个简单无向图，有 \(n\le10^5\) 个点和 \(m\le10^5\) 条边。之后给出 \(q\le10^5\) 次操作，每次操作添加一条新的无向边连接点 \(u\) 和 \(v\)（可能重边），或者询问从点 \(u\) 到 \(v\) 的所有路径中，有多少条边是必须经过的(\(1\le u\not=v\le n\))。

题解：先随便求一个原图的生成树，然后将不在树中的边当做操作 \(1\) 处理。然后，操作 \(1\) 就是将树中 \(u\) 到 \(v\) 的路径中还存在的边删掉，操作 \(2\) 就是询问树中 \(u\) 到 \(v\) 的路径中还存在的边的数量。

法一：用 dfs 序加上树状数组来维护每个点到根的路径上存在的边的数量，删去一个点时对它子树对应的 dfs 序区间进行修改，时间复杂度为 \(\mathcal{O}(\log{n})\)。询问的时候，分别求 \(u\)，\(v\) 和 \(\text{lca}(u,v)\) 的答案计算一下即可，时间复杂度为 \(\mathcal{O}(\log{n})\)。因为每条边只会被删除一次，可以使用并查集维护删边，这样修改的总时间复杂度为 \(\mathcal{O}(n\log{n})\)。

整个算法的时间复杂度为 \(\mathcal{O}((m+q)\log{n})\)，空间复杂度为 \(\mathcal{O}(n)\)。但是因为要存很多信息，特别是要求 \(\text{lca}\) 时使用了 Tarjan，导致实际使用的内存偏多，场上没能成功卡进 32M 的空间限制（赛后给两个递归的函数加上了inline，少了近 2K 内存，过掉了）。

法二：对生成树进行树链剖分，然后用树状数组维护 dfs 序，删去一条边直接在树状数组中进行修改，询问时则一边跳重链一边询问每一段连续区间的答案。同样使用并查集删边。

整个算法的时间复杂度为\(\mathcal{O}((m+q)\log{n}+q\log^2{n})\)，空间复杂度为 \(\mathcal{O}(n)\)。由于要记录的信息较少，特别是不需要花额外的开销去计算 \(\text{lca}\)，只需要 20M 的内存就可以轻松过掉这题。

H. transaction transaction transaction

题目大意：给出一个 \(n\le10^5\) 个点的树，点 \(i\) 的点权为 \(p_i\)，每条边 \(e\) 还有一个边权 \(w(e)\)。从点 \(u\) 到点 \(v\) 的收益为 \(\displaystyle p_v-p_u-\sum\limits_{e \in \text{path}(u,v)} w(e)\)。现在让你选择一个起点和一个终点，求最大的收益。

题解：直接树分治即可，但是需要注意优化一下常数，或者使用靠谱的读入优化。

I. cube cube cube

题目大意：给你一个八轴八面的魔方，问你是否可以在三步以内让魔方恢复。

题解：题目中只给出了 \(12\) 种操作，实际上我们可以旋转每个面，以及这个面对应的中间层，所以有 \(16\) 种操作，再反向旋转，于是一共有 \(32\) 种操作。实际上写程序的时候，对于面的旋转我们只用写一个函数 \(\text{r}(x)\) 来旋转 \(x\) 这个面，反向旋转时调用两次 \(\text{r}(x)\) 即可。对于中间层的旋转我们要写两个函数 \(\text{m}(x),\text{rm}(x)\) 分别表示两个方向的旋转，否则我们要调用五次 \(\text{m}(x)\) 来表示 \(\text{rm}(x)\)，可能会超时。

旋转面的时候，我们可以打表预处理每个面邻接的面中受影响的编号。也可以找规律节省一些打表的时间，比赛中直接打表也只花了不到 10 mins 的时间。最后直接搜索即可。

J. ping ping ping

题目大意：给出一个 \(n\leq 10^4\) 的树，和 \(q\leq 5\times 10^4\) 个要求 \((u_i,v_i)\)，表示要求 \(u_i\) 和 \(v_i\) 不连通。破坏一个点即为删掉与该点相连的所有边。问最少破坏多少个点使得 \(q\) 个要求全部满足。

题解：我们将所有要求按照 \(\text{lca}\) 的深度从深到浅排序。然后贪心地去破坏这些 \(\text{lca}\)，如果一个要求已经满足，那么我们就不用去破坏。正确性：考虑当前的要求，要满足它那么一定要破坏一个 \(u\) 到 \(v\) 的路径上的点，显然破坏 \(\text{lca}\) 会使得受影响的要求个数最大，因为所有受影响的要求的 \(\text{lca}\) 比当前的 \(\text{lca}\) 浅。

判断要求是否被满足，我们只需要知道每个点到根的路径上，有多少个坏点，就可以知道 \(u,v\) 的路径上是否有坏点。每次破坏点的时候，将子树整体 \(+1\)，用树状数组维护区间修改，单点查询即可。

K. triangulation triangulation triangulation

题目大意：给你一个有标号的正 \(n\) 边形，求满足如下条件的三角剖分方案数：在这 \(n-2\) 个三角形中，存在一个三角形的面积严格大于剩余的每一个（\(n-3\) 个）三角形。

题解：感谢tls的题解。

设第 \(i\) 个点的坐标为 \(\left(\cos\frac{2\pi(i-1)}{n},\sin\frac{2\pi(i-1)}{n}\right)\) ，假设一个三角形的两边分别跨过了 \(x\) 和 \(y\) 条边，则它的面积为

\[ \begin{aligned}\\ &\text{abs}\left((\cos\frac{2\pi x}{n}-1,\sin\frac{2\pi x}{n})\times(\cos\frac{2\pi(x+y)}{n}-1,\sin\frac{2\pi(x+y)}{n})\right)\cdot \frac{1}{2}\\ =&\text{abs}\left(\cos\frac{2\pi x}{n}\sin\frac{2\pi (x+y)}{n}-\sin\frac{2\pi x}{n}\cos\frac{2\pi (x + y)}{n}-\sin\frac{2\pi(x+y)}{n}+\sin\frac{2\pi x}{n}\right)\cdot \frac{1}{2}\\ =&\text{abs}\left(\sin\frac{2\pi x}{n}+\sin\frac{2\pi y}{n}-\sin\frac{2\pi (x+y)}{n}\right)\cdot \frac{1}{2}\\ \end{aligned}\\ \]

我们枚举最大的三角形三条边中跨越边数较小的两条边，容易发现剩下的三个（两个或一个）部分互不干扰。我们只需要 dp 出这个三角形的三边分别跨越 \(k_1,k_2,k_3\) 条边的部分，划分为严格小于枚举的面积的三角形的方案数。这个 dp 的状态转移，只需要枚举一个顶点与原三角形分割的那条边组成三角形，就能转化为两个子问题。状态转移方程为： \[ \begin{cases} dp[1]=1\\ dp[i]=\sum_{j=1}^{i-1}dp[j]\cdot dp[i-j]\cdot [\text{area}[i][j-i]<S] \end{cases} \] 容易发现，如果枚举的三条边互不相同，答案要乘以 \(2n\) ，如果两条边相同而和另一条边不同，答案要乘以 \(n\) ，如果三条边都相同，答案要乘以 \(\frac{n}{3}\) 。

L. card card card

题目大意：给你两个循环数组 \(a\) 和 \(b\)，定义每个位置的值为它到它右边第一个让 \(a\) 的前缀和小于 \(b\) 的位置的这一段 \(a\) 的和，求值最大的位置，如果有多个，求最左边的位置。保证 \(a\) 的和等于 \(b\) 的和。

题解：按照题意简单模拟即可，用单调栈找到这个位置，用前缀和计算答案。

Replay and Summary

Replay

D 先看了 A 题，发现是个大水题直接莽 sam 就可以了，交给 W 来写。W 很快写完，然后发现没给字符集大小，心大直接不管交了一发，就过掉了。Z 发现 D 是个水题，写过也 a 了。W 发现 B 已经被 a 穿了，但是看了看没什么思路啊，就交给刚做完 D 的 Z， Z 看了两眼莽了个式子过掉了。E 看了看觉得是个递推式，W 正准备写一个 BM 模板上去，结果 Z 就说过掉了，W 被吓得不敢说话。

H 题 W 看了之后给 D 说是一个树分治的题，然后 D 说他来写，就交给 D 写去了。期间 Z 发现 L 是个水题，写了一发，然后因为没仔细看空间限制（32MB 真是小啊）而 MLE 了一发，奠定了本场疯狂 MLE 的基础。D 写完 H 各种错误（wa MLE TLE ce），W 赶紧让他冷静下来，然后发现可以优化，优化之后过掉了。

F 题 W 之前看成了取绝对值，看了看 clarification 之后发现不是绝对值，Z 觉得直接 dp 转移就可以了。 W 给 Z 出了点数据，Z 怎么都跑不过。各种调试之后，交了一发 MLE，感人肺腑。改成 vector 之后过掉了。

D 跟 W 讨论了一下，觉得 G 似乎可以用 lct 或者树剖随便怎么搞一搞。此时二人完全没有吸取到之前 MLE 的教训，更没有仔细查看时间空间限制。W 就让 D 去写了。D 写了之后先是 TLE，在本地从 7s 优化到 1s 之后提交发现 MLE，最绝望的是怎么修改都比 32MB 多一点点。

W 和 Z 趁 D 在刚 G 的时候，做了一个魔方，然后打了一个表来辅助搜索。缓慢稳定地 1a 了 I 题。最后半小时 W 想到了 J 的贪心，然后没写完。虽然不知道为什么出题人这么缺内存，但是弊队总是不注意时间空间限制的毛病得改改了。