Contest Info

date: 2018.09.30 13:00-18:00

practice link

Solutions

A. Balloon Robot

题目大意：

在一个\(m\le 10^9\)个位置的圆桌上，有\(n\le10^5\)个参赛队伍，第\(i\)支队伍的座位号为\(s_i\).

接下来有\(p\)次事件，为队伍\(a_i\)在\(b_i\)时刻通过了一道题目。

有一个发气球机器人，从位置\(k\)出发，每秒循环移动一个位置，然后把当前位置的队伍应该获得的气球都发送给他们（包括恰好这一秒通过的题目）.

找一个\(k\)，使得总的等待时间最少，输出最少等待时间。

题解:

假设\(k\)给定，事件\(i\)的贡献为\(s_{a_i}-k+x\cdot m - b_i\)，其中\(x\)为最小的非负整数，使得\(s_{a_i}-k+x\cdot m - b_i\)非负。

令\(b_i=y\cdot m + c_i\)，\(0\le c_i<m\)，则\(s_{a_i}-k+x\cdot m - b_i = s_{a_i}-k+(x-y)\cdot m - c_i\).

显然\(x-y\)只会取\(0,1,2\)三种取值，将对应的\(k\)作为关键事件，从大到小扫描一次即可。

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

B. Expected Waiting Time

题目大意：一个长度为 \(2n\) 的括号序列，每个位置有一个权值，定义它的价值为右括号所在位置的权值和减去左括号所在位置的权值和。求所有合法括号序列的价值和。

题解：计算每个位置对答案的贡献，显然即为该位置填右括号时的合法方案数减去填左括号时的合法方案数。不妨计算左括号，我们可以枚举与它匹配的右括号的位置，那么这对括号中间、外面的填法分别都是卡特兰数。前缀和计算一下即可。

时间复杂度 \(\mathcal{O}(n)\)。

C. Crusaders Quest

签到题。

D. Graph Generator

题目大意：

给出一个生成图的方法，对于\(1\)到\(n\)的排列\(p_n\)，第\(i\)次操作：

• 取当前存在的若干个点\(a_1,\cdots,a_m\)，\(0\le m<i\)，任意两个点不属于同一连通块
• 新增点\(p_i\)向\(a_1,\cdots,a_m\)所在连通块中每一个点连一条边

给出一张\(n\le10^5\)个节点，\(m\le10^5\)条边的简单无向图，问是否可以用上述方法生成，若可以输出一组可行方案。

题解：

考虑倒着执行这个过程，每次选取一个连通块，然后从中取出一个度数等于连通块大小-1​的点（若没有则无解），这个点作为\(p_i\)，然后删去它，继续执行。

考虑任意时刻，不同的连通块是相互独立的，同一连通块中，如果存在合法的点，它一定是这个连通块中度数最大的（多个点任取一个），并且删去它之后会给这个连通块的每个节点度数减去一，度数大小的相对关系没有发生改变。

因此我们可以按度数从大到小的顺序来删点，连通性就从小到大做一次启发式合并的并查集，然后边撤销边处理即可。

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

E. String of CCPC

题目大意：

给出一个长度为\(n\le2\times10^5\)的由C和P两个字母组成的字符串。

定义字符串的价值为子串CCPC出现的次数。

现在可以任意次给字符串的某个位置添加一个字符，第\(i\)次操作的代价是\(i-1\).

最大化字符串的价值减去操作的代价和。

题解：

注意到添加一个字符最多增加一次出现，那么我最多只会执行两次操作。

令\(dp[i][j][u]\)表示在第\(i\)个位置执行了\(j\)次操作，在kmp上状态为\(u\)的最优值，直接枚举转移即可。

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

G. Numbers

题目大意：将 \(n\) 表示成 \(m\) 个非负整数之和，求它们或起来的最小值。

题解：贪心。注意到若 \(n>m(2^{k}-1)\)，那么答案的第 \(k\) 位必然是 \(1\)，那么我们尽可能多地在该位上填 \(1\)，再依次考虑后面的位即可。不知道为什么是对的。

H. Prime Set

题目大意：定义 prime set 为 \(\{i, j\}\), 其中 \(i\neq j\) 且 \(a_i+a_j\) 是质数。给定一个序列 \(\{a_i\}\)，你可以选出最多 \(k\) 个 prime set，使得他们的并集的大小最大。

题解：先不考虑 \(1+1=2\)，我们把序列按奇偶分成两部，然后连边求最大匹配。用匈牙利算法求最大匹配的时候，最后从 \(a_i=1\) 的 \(i\) 开始找增广路。然后把剩余的 \(1\) 两两连边。

每个匹配贡献 \(2\) 的答案，但如果匹配数还未达到 \(k\)，那么我们还可以把有边连接的未盖点也贡献答案。

I. Triangulation

题目大意：

二维平面上有\(n\le18\)个点，用线段连接点\(i\)和点\(j\)的代价为\(w_{i,j}\)，求最小代价的三角剖分，以及取到这个最小代价的方案数量。

题解：

随机选择平面使得不存在两个点\(x\)坐标相同。

考虑状压dp，对向上转移的折线进行状压，当从下凸壳转移到上凸壳时就遍历了所有三角剖分。

预处理所有不包含其它点的三角形，用这些三角形来进行转移。

• 折线可能加入一条边上方的一个点，同这条边构成三角形，形成的新折线多一个点

• 或者连接一个点左右的两个点（要求这条线段在被覆盖的点的上方）构成三角形，形成新折线少一个点

为了不重复，将枚举到折线上哪一个点（或边）计入状态，状态\(O(n\cdot 2^n)\)，转移\(O(n)\)，时间复杂度\(O(n^2\cdot 2^n)​\).

K. Diversity and Variance

题目大意：给定长度为 \(n\) 的序列 \(\{a_i\}\)，从中删掉 \(m\) 个元素，使得剩下元素的方差最大。有多种方案的时候，输出剩下元素的下标集合字典序最小的方案。

题解：把 \(\{a_i\}\) 升序排序，那么最大方差显然是一个前缀加一个后缀。特别的，除了 \(m=n-1\) 的情况，其余情况下前后缀均不为空。考虑最小字典序的方案。

我们把下标按照 \(\{a_i\}\) 升序排序，元素相同的时候，下标升序排序（记为 pre 数组），下标降序排序（记为 suf 数组）。用线段树来维护下标集合，两个域 seg1，seg2，分别记录当前最优解对应的下标集合，以及当前解对应的下标集合。如果更新最优解，那么把 seg2 整体拷贝到 seg1，这个可以打 lazy 标记。前缀增加一个，后缀减少一个的时候，在 seg2 中插入和删除一个元素，然后叶子节点记录 cmp = seg1 - seg2，回溯的时候优先取左儿子的比较结果。如果根结点有 cmp[1] = -1，表示 seg1 表示的集合在某个前缀的元素个数比 seg2 小，也即 seg1 的字典序大于 seg2。

有个细节，当前缀的最后一个元素等于后缀的第一个元素的时候，此时方案不合法（共享了同一个下标），我们不计算答案，可以证明不会影响最优解。方差的计算可以用 \(E(X^2)-(EX)^2\)。

L. One-Dimensional Maze

签到题。

M. Safest Buildings

签到题，case 分析。

Dirt Replay

B: -3 爆数组comb；模数2e9 加法爆int；预处理冗余被卡一倍常数

D: -1 答案是 No 的情况下直接 return，没有清空

H: -3 写错了；边界情况，输入全 1

L: -1 读入字符串下标错误

M: -1 少了一个情况