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.

题意：给定多边形，在多边形内随机选两个点，求两点间曼哈顿距离的期望。

题解：由于期望的可加性，可以把所求的期望分成横坐标上的期望和纵坐标上的期望分别求解再求和。横纵坐标只要镜像翻转再做一次就等价，所以只需要考虑如何在横坐标上做。

因为只考虑横坐标的差，我们可以把多边形上的点映射到 $x$ 轴，可以得到分段函数 $F(x)$ 代表多边形上的点落到 $x$ 轴上各处的概率，也就是分布的概率密度函数。我们设多边形映射到 $x$ 轴上后最左侧的坐标是 $l$，最右侧是 $r$。

因为无论在凸包里怎么选，两个点钟第一个在第二个左侧的概率都是 $0.5$，所以可以只考虑第二个点落在第一个点左侧的情况，最后翻倍。如果确定了第一个点落在了 $x$ 处，那么第二个点能做出的总贡献就是 $\int_{y=l}^xF(y)(x-y){\rm d}y$。那么，总贡献就是 $\int_{x=l}^rF(x) \cdot \int_{y=l}^xF(y)(x-y){\rm d}y{\rm d}x$。

Problem J

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

题意：有 $n$ 个单位，最初 $a,b=0$，每个单位可以花费一些代价使 $a$ 增加 $x_i$，$b$ 增加 $y_i$，总收益是所有的 $a \cdot b$，给出最大代价，求最大收益。

题解：将所有的代价都分给各个单位，会获得一系列 $(X_i,Y_i)$，把它们列在平面上，那么所有的方案的 $(a,b)$ 一定落在这些点的凸包内，最优解一定落在凸包上的点或者边上，在凸包上枚举求解。

Problem K

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

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

题解：SA模板题。

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

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