Contest Info

date: 2019.01.13 13:10-18:10

practice link

Solutions

A. Edit Distance

题目大意：给定一个长度为 \(n\) 的 0/1 串 \(s\)，要求你构造一个相同长度的 0/1 串 \(t\)，使得它们的编辑距离大于 \(\frac{n}{2}\)。编辑可以是：插入、删除、替换。

题解：如果串 \(s\) 中 0 和 1 的个数不一样，那么我们构造一个串 \(t\) 全部是较少的那个字母即可。那么该字母至少要插入大于 \(\frac{n}{2}\) 次。

如果 0 和 1 的个数相同，那么 \(t_0\) 与 \(s_0\) 不同，剩下的位置取 \(s_0\)。证明只需要考虑 \(t_0\) 是由 \(s_0\) 替换得到，或者是在 \(s_0\) 前面插入得到，讨论一下即证得。

C. Smart Thief

题目大意：有 \(m\) 个字母，要求你构造一个串，使得其中至少有 \(k\le\min(10^{5},m^{n})\) 个本质不同的长度为 \(n\) 的子串，且长度最短。

题解：De_Bruijn_sequence

找有向图的欧拉回路用 Hierholzer’s Algorithm 来做，复杂度是 \(\mathcal{O}(|E|)=\mathcal{O}(m^n)\) 的。在 \(m^{n}\) 很大的时候，不能把整个欧拉回路找出来。只要正向路径和反向的栈里面有一个长度足够了即可停止搜索。

D. Icy Land

签到题。

E. Artilleries and Defensive Walls

题目大意：\(x\) 轴上方有 \(n\le40000\) 门火炮（点）和 \(m\le5\) 堵墙，它们互相严格不相交。\(x\) 轴下方有 \(q\le40000\) 个观察点。对每个观察点求出它能看到的火炮的数量。

题解：我们从反面计算被墙挡住的火炮的数量。

我们按所有墙的 \(y\) 坐标将火炮分为若干层，每层分别计算。对于每个观察点，以它为中心，将所有墙的端点极角排序。对于每个不相交的区域，我们可以用类似前缀和的方法来计数。我们注意到，每个前缀和所计算的区域，都至少经过某个墙的端点，因此我们可以转化为以墙的端点为中心极角排序来预处理前缀和。

时间复杂度 \(\mathcal{O}((n+q)m^{2}\log n)\)。

F. Popping Balloons

题目大意：在一场总共\(m\le10^9\)分钟的比赛中，两名选手\(A\)和\(B\)都按顺序做\(n\le10^5\)道题目。选手\(A\)和\(B\)完成第\(i\)道题目分别需要\(A_i\)和\(B_i\)分钟。每当选手完成一道题目，他将立即获得一个气球。选手\(A\)在拿到气球后，可以在任意时间把气球弄破发出巨大的声响干扰选手\(B\)，让选手\(B\)重新开始做当前的题目。问是否存在一种方案使得选手\(A\)完成的题目数量严格大于选手\(B\)，输出任意一种方案。

题解：

考虑贪心，首先选手\(A\)能完成的题目和拿到气球的时间都是固定的，假设他可以完成\(x\)道题目，则我们只考虑\(B\)完成前\(x\)道题目的过程。

假如某个时候，\(B\)完成前\(x\)道题目的时间大于了\(m\)，就完成了我们的目的，否则我们考虑依次去弄破气球。

设当前最早可以得到气球的时间为\(y\)，则\(y\)之前\(B\)已经完成的任务就没有办法影响了，否则我们可以影响的任务就是一个后缀，我们选择后缀中最大的\(B_i\)，在它要完成的瞬间进行干扰即可。

处理一下后缀最大值即可，时间复杂度\(O(n)\).

G. Go Make It Complete

题目大意：给出一个 \(n(n\leq 500)\) 个点 \(m(m\leq \frac{n(n-1)}{2})\) 条边的简单无向图，求一个最大的 \(k\) 满足：存在一个加边 \((u_i,v_i)\) 的顺序，使得 \(u_i\) 与 \(v_i\) 之间原本没有边，且 \(\text{deg}_{u_i}+\text{deg}_{v_i}\geq k\)，加完边之后图变成一个完全图。

题解：二分答案 \(k\)。建出反图，一开始找到满足端点度数之和不小于 \(k\) 的边，放进队列。然后依此将其删掉，并更新队列。实现的时候需要注意常数复杂度删边（与 vec[i][sz - 1] 交换）。复杂度感受了一下应该很小。

H. Lexical Sign Sequence

裸的数位 \(dp\)，用 set 维护当前有效的区间即可。

I. Lie Detector

签到题。

J. Future Generation

题目大意：给出\(n\le15\)个只有大写拉丁字母组成的字符串\(s_1,\cdots,s_n\)，且\(|s_i|\le15\).要构造一个字符串序列\(t_1,\cdots,t_n\)，满足\(t_i\)是\(s_i\)的非空子序列，且\(t_i\)的字典序严格小于\(t_{i+1}\)，问\(\sum|t_i|\)最大是多少。

题解：

对于每个字符串\(s_i\)，最多可能有\(2^{|s_i|}-1\)种不同的\(t_i\)，将它们基数排序，时间复杂度\(O(n^22^n)\)，空间复杂度\(O(n^22^n)\).

考虑\(dp[i][j]\)表示\(t_i\)取\(rk\)为\(j\)的可能时的最优值，维护前缀最大值转移即可，时间复杂度\(O(n^22^n)\).

K. Boomerangs

题目大意：给出一个简单无向图，让你在其中找出最多个回旋镖。回旋镖指的是两条恰有一个公共顶点的边 \((u,v),(v,w)\) 且 \(u\neq w\)。

题解：对每个连通块分别考虑。可以证明对于一个连通块，设边数为 \(m\)，那么一定可以找到 \(\lfloor \frac{m}{2} \rfloor\) 个回旋镖。考虑它的搜索树，只会有前向边和后向边。我们只考虑前向边。回溯的时候，我们把儿子两两组合成回旋镖，如果还剩下单个儿子，那么把它和父亲组成回旋镖。这里的儿子，指的是前向边的儿子，或者树边且不删掉父亲的儿子。

证明大概是，把连通块的奇度点连向一个新点。这个欧拉图可以拆成从新点开始的若干个偶环和至多一个奇环，偶环可以不浪费地对应回旋镖，奇环会浪费一条边。

L. Binary String

签到题。