2018 ICPC Mid-Central Regional

Problem A

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

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 (+)

Problem I

Unsolved.

Problem J

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

Problem K

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