Contest Info

date: 2019.01.14 14:10-19:10

practice link

Solutions

A. The ABCD Murderer

题目大意：有\(n\le3\times10^5\)个只有小写字母组成的单词，\(s_1,\cdots,s_n\)，\(\sum |s_i|\le3\times10^5\).每个单词可以用多次，且可以重叠，问要拼出目标串\(t\)（\(|t|\le3\times10^5\)）至少需要多少单词？

题解：考虑\(dp[i]\)为拼出前缀\(i\)至少需要多少单词，则最后一个单词一定是贪心的选可以放的最长的单词最优，假设这个单词长度为\(l\)，则\(dp[i]=\min_{j\in[i-l,i)} dp[j]+1\)，这个最长单词可以用AC自动机来求，时间复杂度\(O(\sum|s_i|\sigma+|t|\log{|t|})​\).

B. The Bridge on the River Kawaii

题目大意：有一个\(n\le10^5\)个点的无向图，\(q\le10^5\)次操作，每次操作可能是以下三种之一：

• 在当前没有边直接相连的两个点\(u\)和\(v\)之间添加一条边权为\(w\in[0,9]\)的无向边
• 断开当前有边直接相连的两个点\(u\)和\(v\)的连边
• 询问点\(u\)和\(v\)之间的最小瓶颈边，不连通输出-1

题解：枚举答案\(x\)，则操作3等价于最小的\(x\)满足只用边权不超过\(x\)的边将\(u\)和\(v\)连通。用动态树维护关于删除时间的最大生成树即可。时间复杂度\(O(W(n+q)\log{(n+q)})\).

C. Clockwork Range

签到题。

D. Reservoir Dog

不好意思我看不懂题。。

E. Trees Gump

题目大意：有一棵\(n\le1000\)的树，和二维平面上\(n\)个不存在三点共线的点，求一个树节点与平面上点的一一映射，使得这棵树可以被平面嵌入。

题解：任意选择一个顶点做为树的根，然后选择平面上水平序最小的点与其对应，将其它点按以它为中心的极角排序，将每个子树映射到与其数量相同的区间，然后递归下去即可。时间复杂度\(O(n^2\log{n})\).

递归下去的时候，可以用水平序最小的点作为中心来极角排序，也可以用极角序最小的点作为中心来极角排序，但是这个时候要注意不能用 atan2，而是要用叉积来判断，此时都在一个半平面内。

G. Shooter Island

题目大意：有一个\(50\times10^5\)的网格图，一开始全部格子都是障碍。之后\(q\le10^5\)次操作，或者将一个矩形变成非障碍点，或者询问两点是否可达（四连通）。

题解：用一个\(50\times10^5\)的并查集维护连通性，然后再用\(50\)个\(10^5\)的并查集当链表，每个位置开始往右最早的没有被用掉的\((x,i)\to(x,i+1)\)的边。则修改的时候，枚举每一行，暴力跳链表来加这些横向的边，总的复杂度是\(O(50\times10^5)\)。

但是光是这些边不足以表示完整的连通性，我们在暴力跳链表的同时，维护每个位置是否为障碍，检查当前位置的上下两个邻居是否已经是非障碍点，是则加边，总的复杂度不变。同理，还要检查这一行连续一段开始位置前一个和结束位置后一个。

有一个trick是，询问的两个点即使是同一个点，如果它是障碍，也是不可达的。

时间复杂度\(O(50\times10^5+50q)\)，空间复杂度\(O(50\times10^5)\).

H. The Lord of the Kings

题目大意：有一个\(n\times m\)的棋盘，\(1\le n,m\le15\).有一个棋子，可能是Rook、Queen、Bishop、Knight、King五种之一，在位置\((x,y)\)。给出\(1\le T\le10\)个不同于起点的不同位置，问要遍历这些位置至少要经过几个不同的格子（起点除外），如果无法遍历则输出-1.

题解：斯坦纳树裸题。令\(dp[s][i]\)为访问了集合\(s\)中的点且当前在点\(i\)时的最优值，将起点也当作必须访问的点，且计算贡献，最后统计答案的时候减去1即可。

初始值为\(dp[0][i]=1\)，\(dp[2^k][pos[k]]=1\)，其余为正无穷.

从小到大枚举\(s\)，枚举每个位置\(i\)，枚举\(s\)的真子集\(s_1\)，用\(dp[s_1][i]+dp[s\oplus s_1][i]-1\)更新\(dp[s][i]\)的初始值，然后用dijkstra跑\(s\)这一层的最短路更新即可。

时间复杂度\(O(2^{T+1}nm(n+m)\log{nm(n+m)}+3^{T+1}nm)\)，空间复杂度\(O(2^{T+1}nm)\).

I. The Silence of the Lamps

签到题。

J. Matrice

题目大意：给定一个 \(n\times m\) 的字符矩形。问有多少个由相同字符组成的直角等腰三角形（正方形抛去对角线的一半）。

题解：扫一遍。对每行，我们记录从这一列往前最长的三角形边长，下一列可以 \(\mathcal{O}(1)\) 转移。

K. Mirrority Report

镜面反射几何题。写过很多次了，随便写写就过了。

L. Game of Stones

题目大意：有 \(n\) 堆石子，两个人取石子，先手每次可以取 \(1\sim A\) 颗，后手每次取 \(1\sim B\) 颗，问胜负情况。

题解：设 \(x=\min(A,B)\)，首先把这个游戏当做每人都只能取 \(1\sim x\) 颗的平等游戏，那么显然 \(c\) 颗石子的 \(sg\) 为 \(c\mod{(x+1)}\)。

• 若 \(A=B\)，那么这就是上面说的游戏
• 若能取更多石子的人胜，那么他在原游戏中显然也胜利
• 否则，若 \(A>B\)，只要存在一堆石子 \(\ge x+1\) 颗，那么先手从这堆石子中取 \(x+1\) 颗，\(sg\) 值不变（仍为 \(0\)），变为上一种情况；若不存在，那么实际上是一个平等游戏
• 若 \(A<B\)，先手要防止后手通过上面一种情况获胜，如果至少两堆石子有至少 \(x+1\) 颗，那么先手必败；如果没有至少 \(x+1\) 颗的堆，那么先手必胜；如果恰有一堆，枚举先手的行动即可