CERC 2018

Contest Info

date: 2019.01.14 14:10-19:10

opentrains 6316

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\).有一个棋子,可能是RookQueenBishopKnightKing五种之一,在位置\((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\) 颗的堆,那么先手必胜;如果恰有一堆,枚举先手的行动即可