2018 ICPC Mid-Central Regional

From EOJ Wiki
Jump to navigation Jump to search

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

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