Contest Info

date: 2017.08.13 10:30-15:30

practice link

Solutions

A. Grandpa’s Walk

题目大意：给出一个 \(n\times m(n,m\leq50)\) 的网格图。每个格子上有一个数字，可以从一个格子走到另一个与它四连通的格子当且仅当目标格子中的数字严格小于当前数字，问图中有多少条路径是不可拓展的。

题解：直接根据题意搜索即可。

B. Let’s Go Green

题目大意：给出一棵树，每条边上有一个整数表示这条边恰需要被覆盖的次数。求最少要多少条路径才能满足。

题解：我们考虑树上每个点作为路径端点的次数，所有的次数加起来除以 \(2\) 显然就是答案了。对于一个点，我们记 \(max\) 表示该点连的边中最大的覆盖次数，记 \(sum\) 表示该点相连的边的覆盖次数之和。

• 如果 \(max \geq sum-max\)，那么我们可以将从 \(max\) 所在边走过来的路径全部经过其他的边。最终还剩余 \(max-(sum-max)\) 条路径无法继续走，所以此时该点的贡献为 \(max-(sum-max)\)。
• 否则，我们还是将其他边走过来的路径，全部分配到 \(max\) 所在边。最后剩余的 \((sum-max)-max\) 条路径，全部内部两两分配。所以此时的贡献为 \(((sum-max)-max)\text{mod } 2\)。

C. Stop Growing!

签到题

D. Retrenchment

题目大意：给你平面上若干个点。每次询问给你一个简单多边形，再给你若干个询问点，对每个询问点回答离该询问点最近和次近的在简单多边形中的点的编号。

题解：由于多边形边数很少，计算几何部分只需要套模板暴力判断每个点是否在该多边形中就可以了。然后对多边形内部的点建一棵 KD-Tree，询问的时候去 KD-Tree 上搜索。KD-Tree 每个节点记一下最小的能覆盖子树中所有点的矩形，然后搜索的时候用询问的点到这个实心矩形的距离估算一下子树中的最小距离，如果这个估算的距离比当前的次小值还要大，那么这棵子树都不需要搜索了。

（弊队两人合写一道题越来越熟练了啊）

E. Bee Tower

题目大意：有 \(n\leq50\) 座塔排成一条直线。塔 \(i\) 的坐标为 \(p_i\)，高度为 \(h_i\)，高度最高的塔是目标塔。在任意时刻你可以从一个塔 \(i\) 跳到相邻的塔 \(j\)，当且仅当 \(|p_i-p_j|\leq W \land p_j\leq p_i+H\)，\(H\) 和 \(W\) 是给定的常数。你可以随时从地面跳上塔 \(i\) 或者从塔 \(i\) 跳到地面，当且仅当 \(h_i \leq H\)。并且由于你非常的勇，你可以移动一些塔，将塔 \(i\) 移动到坐标 \(x\) 的花费为 \(h_i \times |x-p_i|\)。你不可以移动目标塔，只有在地面上时才可以移动塔，并且不能改变塔的相对顺序。你要从地面上跳到任意一座目标塔，判断是否无解，如果有解输出最小花费。

题解：枚举要跳上哪一个目标塔。令 \(f[i][j]\) 表示要从塔 \(i\) 跳上目标塔，且塔 \(i\) 被移动到了位置 \(j\)，的最小花费。假设目标塔的编号为 \(x\)，初值 \(f[x][p_x]=0,f[x][j\not=p_x]= \infty\)。

当 \(i<x\) 时，有转移方程：

\[ f[i][j]=\min\limits_{j<k\leq p_x,k-j\leq W,h_{i+1}\leq h_i+H}\{f[i+1][k]\}+h_i\times|p_i-x| \]

当 \(i>x\) 时类似。当前枚举的目标塔 \(x\) 的最小花费为 \(\min\limits_{h_i\leq H}\{f[i][j]\}\)。复杂度 \(\mathcal{O}(nPWcnt_x)\)，其中 \(cnt_x\) 为目标塔的个数，\(P\) 为坐标的范围。

F. Knots

题目大意：给出一个绳结，保证每个重叠的部分只有上下两个绳子。判断该绳结是否可以通过对一个环形绳子，进行 Self loop 和 Passing 两种操作得到（具体细节和图示看原题）。

题解：我们先离散出所有的关键点，记录它所处的位置（上下），以及它对应的关键点，然后建立双向链表。我们考虑不断地进行 Self loop 和 Passing 的逆操作，如果可以回复至环形绳子，那么显然是可以的。

判断 Self loop 即为，\(i\) 和 \(right_i\) 互为上下两部分，并且互为对方的对应的点。判断 Passing 即为， \(i\) 和 \(right_i\) 同在上（下），并且它们对应的关键点也相邻。一旦找到这两种关系，我们就将相关的关键点删掉，然后继续寻找即可。

具体的正确性证明，大概是从这两种操作的任意次数任意顺序的组合都是可逆的这点入手，这里略过。

G. Unique Path

题目大意：给出一个 \(n\leq10^4\) 个点 \(m\leq10^5\) 条边的简单无向图。问图中有多少个点对 \((u,v)\) 满足 \(u<v\) 且从 \(u\) 到 \(v\) 有且只有一条边不重的路径。两条路径是不同的当且仅当存在一条边属于一条路径且不属于另一条路径。

题解：显然如果经过了一个点数大于 \(2\) 的边双连通分量，那么在双连通分量分量内至少有两条不同的路径。那么将图中所有的点数大于 \(2\) 的边双连通分量找出来，将其中的点从图中删去，那么剩下的图中任意两点之间至多只有一条路径，用并查集处理一下就好。

I. Tiling

题目大意：给你一个无穷大的网格，再给你三个向量，这些向量的任意线性组合（系数为整数）处有一个点，让你求出满足平移后能够覆盖整个网格且每个恰好含有一个点的图形面积的最小值。

题解：设三个向量为 \((x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})\) 。显然我们把横坐标都除以 \(gcd(x_{1},x_{2},x_{3})\) ，纵坐标都除以 \(gcd(y_{1},y_{2},y_{3})\) 后，求出答案再乘以 \(gcd(x_{1},x_{2},x_{3})\cdot gcd(y_{1},y_{2},y_{3})\) 与原答案是相等的。

设处理后的向量为 \((x'_{1},y'_{1}),(x'_{2},y'_{2}),(x'_{3},y'_{3})\) ，满足 \(gcd(x'_{1},x'_{2},x'_{3})=gcd(y'_{1},y'_{2},y'_{3})=1\) 。我们考虑这三个向量在两个坐标轴上能组合出什么。 设 \(a=x'_{1}y'_{2}-x'_{2}y'_{1},b=x'_{1}y'_{3}-x'_{3}y'_{1},c=x'_{2}y'_{3}-x'_{3}y'_{2}\) 。不妨考虑 \(y\) 轴，它们两两可以组合出的是 \(\displaystyle (0,\frac{a}{gcd(x'_{1},x'_{2})}),(0,\frac{b}{gcd(x'_{1},x'_{3})}),(0,\frac{c}{gcd(x'_{2},x'_{3})})\) 的倍数，因此它们三个可以组合出的是 \(\displaystyle (0,gcd(\frac{a}{gcd(x'_{1},x'_{2})},\frac{b}{gcd(x'_{1},x'_{3})},\frac{c}{gcd(x'_{2},x'_{3})}))\) 的倍数。

下面证明 \(\displaystyle gcd(\frac{a}{gcd(x'_{1},x'_{2})},\frac{b}{gcd(x'_{1},x'_{3})},\frac{c}{gcd(x'_{2},x'_{3})})=gcd(a,b,c)\) 。注意到 \(\displaystyle a=\frac{bx'_{2}-cx'_{1}}{x_{3}}\) ，设 \(gcd(a,b,c)=u\cdot v\) ，其中 \(\displaystyle u=\max_{d|gcd(a,b,c),gcd(d,x'_{1},x'_{2})=1}d\)：

\[\begin{aligned} &\because gcd(u,x1,x2)=1, u\mid a\\ &\therefore u\mid \frac{a}{gcd(x'_{1},x'_{2})}\\ &\because v\mid b,v\mid c\\ &\therefore v\mid \left(b\frac{x'_{2}}{gcd(x'_{1},x’_{2})}-c\frac{x'_{2}}{gcd(x'_{1},x’_{2})} \right)\\ &\because gcd(v,x'_{3})=1\\ &\therefore v\mid \frac{b\frac{x'_{2}}{gcd(x'_{1},x’_{2})}-c\frac{x'_{2}}{gcd(x'_{1},x’_{2})}}{x'_{3}}\\ &即 v\mid \frac{a}{gcd(x'_{1},x'_{2})}\\ &\because gcd(u,v)=1\\ &\therefore gcd(a,b,c)\mid \frac{a}{gcd(x'_{1},x'_{2})} \end{aligned} \]

同理有 \(\displaystyle gcd(a,b,c)|\frac{b}{gcd(x'_{1},x'_{3})},gcd(a,b,c)|\frac{c}{gcd(x'_{2},x'_{3})}\) ，故 \(\displaystyle gcd(\frac{a}{gcd(x'_{1},x'_{2})},\frac{b}{gcd(x'_{1},x'_{3})},\frac{c}{gcd(x'_{2},x'_{3})})=gcd(a,b,c)\) 。即 \(y\) 轴上可以组合出的是 \((0,gcd(a,b,c))\) 的倍数，同理 \(x\) 轴上可以组合出的是 \((gcd(a,b,c),0)\) 的倍数。我们取 \([0,gcd(a,b,c)-1]^{2}\) 的一个矩形，容易知道这个矩形平移后可以覆盖整个平面。考虑这个矩形内部，根据上面的结论和裴蜀定理易证每一行每一列有且仅有一个点，故所求面积至少是 \(\displaystyle \frac{gcd^{2}(a,b,c)}{gcd(a,b,c)}=gcd(a,b,c)\) （否则显然不能铺满整个平面），而这个值可以通过对每个点选取它上方 \(1\times gcd(a,b,c)\) 的矩形取到。故答案为：

\[ ans=gcd(a,b,c)\cdot gcd(x_{1},x_{2},x_{3})\cdot gcd(y_{1},y_{2},y_{3})\\ 记 gcd(x_{1},x_{2},x_{3})=x_{0},gcd(y_{1},y_{2},y_{3})=y_{0},有:\\ \begin{aligned} ans&=gcd(ax_{0}y_{0},bx_{0}y_{0},cx_{0}y_{0})\\ &=gcd(x_{1}y_{2}-x_{2}y_{1},x_{1}y_{3}-x_{3}y_{1},x_{2}y_{3}-x_{3}y_{2}) \end{aligned} \]

J. Perfect Matching

题目大意：给出 \(n\) 个字符串 \(\{s_i\}\)。询问将它们两两拼接起来有多少个回文串。

题解：预处理每个字符串的基于进制的前缀 hash。然后暴力枚举所有组合，hash 判断是否为回文串即可。