2018 ICPC Mid-Central Regional

2018 ICPC Mid-Central Regional

Xiejiadong : 趁着队友还没睡醒，抢的一手签到题。

Problem A

Solved by Kilo_5723. 00:56:00 (+)

题意：给定平面上 $n$ 个点，前 $e$ 个点互相连通，除此之外有一些点互相连通，连接两个点的代价是两个点的欧几里得距离，求 $n$ 个点互相连通需要的最小代价。

题解：把所有连接的边的长度设为 $0$，求最小生成树。

Problem B

Solved by Xiejiadong. 00:03:24 (+)

题意：给出两个人的答题情况，已知第二个人对了几题，求第一个人最多过几题。

题解：让第一个人对的尽量多的策略是很显然的。假设第二个人对了 $a$ 题，如果第一个人和第二个人一样的答案有 $x$ 个，那么这部分答案至多能对 $min(x,a)$ ；

另一部分就是两个人答案不一样的时候，让第二个人尽量错，于是这部分答案至多能对 $min(n-x,n-a)$ 。

这两部分答案加起来即可。

Problem C

Solved by Weaver_zhu. 02:42:52 (+)

题意：maze $m\times n$ 大小，每个格子可以花费一定代价堵住，求花费最小的代价能然某个点走不到边界。

题解：裸的最小割，拆点入点到出点中间边连一条容量为花费的边。

不能放障碍变容量就是 inf，其余出点连到上下左右四个格子的入点。

根据最小割的定义就是去掉容量和最小的边使得图不联通，跑个最大流就行了。

Problem D

Solved by Xiejiadong. 00:22:46 (+)

温暖的签到。

Problem E

Solved by Weaver_zhu. 00:16:54 (+)

题意：求区间 $ \sum\sum[gcd(i,j)==1]$ 。

题解：枚举gcd，莫比乌斯反演。

凡是学过莫比乌斯练得基本都是这道题。

$G(x,n,m) \\= \sum\sum[x|gcd(i,j)] \\= (n/x)*(m/x)\\ = \sum\limits_{x|d}F(d,n,m), F(x,n,m) \\= \sum\limits_{d=1}^{n/x}\mu{(d)}G(x,n/d,m/d)$。

答案就是 $\sum\limits_{d=1}^{n}\mu(d)(n/d)(m/d)$ 。

分块加速即可。

Problem F

Solved by Xiejiadong. 00:29:33 (+)

题意：山羊在 $(x,y)$ 处，在 $(x_1,y_1),（x_2,y_2）$ 处有一个矩形，求山羊到矩形的最短距离。

题解：相当于求到四条线段的最短距离。

首先最短距离可能是到四个端点中的最小值，先求这四个距离。

其次，如果山羊所在的 $y$ 坐标在矩阵的 $y$ 坐标范围内，那么可能到边的直线距离更小，于是就再对到边的距离取 min ； 如果在 $x$ 坐标范围内，也一样处理。

Problem G

Solved by Xiejiadong. 01:33:13 (+)

题意：每个字母对应的位置可以对应不同的变换方式，求从状态 $A$ 到状态 $B$ 的最小变换次数。

题解：首先考虑状态最多有多少 ，状态最多是 $6^8\le 2\cdot 10^6$ ，于是可以考虑搜索。

显然每一次的代价都是 $1$ ，代价相同，直接 BFS 即可。

对于每一个状态，枚举每一个位置的转移，看是否出现过这个状态，没出现过直接更新即可。

理论最差时间复杂度 $O(6^8*8*8)$ 。

Problem H

Solved by Xiejiadong. 00:20:27 (+)

题意：求一个区间范围内，满足数字不包含 $0$ ，没有重复数字，且原数能被每个数字整除的数的数量。

题解：暴力枚举判断就完事了。

Problem I

Upsolved by Kilo_5723.

Problem J

Solved by Kilo_5723. 02:47:25 (+3)

Problem K

Solved by Weaver_zhu. 01:07:32 (+)

题意：求最长的字典序最小的重复子串。

题解：SA模板题。

后缀数组最大最先出现的高度数组的那个后缀的前缀就是我们要求的。

也可以用 SAM 做，利用字典序插入 SAM ，建立后缀树，在后缀树上找即可。