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 mxn 大小,每个格子可以花费一定代价堵住,求花费最小的代价能然某个点走不到边界。

题解:裸的最小割,拆点入点到出点中间边连一条容量为花费的边。不能放障碍变容量就是 inf,其余出点连到上下左右四个格子的入点。根据最小割的定义就是去掉容量和最小的边使得图不联通,跑个最大流就行了

Problem D

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

Problem E

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

Problem F

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

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