2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by zerol. 00:07 (+)

温暖的签到。(介绍景点好评)

Problem B

Solved by kblack. 04:52 (+6)

题意:打怪兽,要求受伤最少,且操作序列字典序最小。

题解:显然总回合数已定,一个观察是肯定先打死一个,然后一定是最少的回合数,剩下的就是怎么打的问题。当先打 A 的时候,如果必须要借给 B,那么直接借最大量,否则就直接浪费掉,这样最前面的 B 最后。如果先打 B,可以在前面先打一会儿 A,控制在 A 需要借的量和 B 可以借出的量之间就好了。

kblack: 打!怪!兽!不!好!玩!

Problem C

Solved by zerol. 04:45 (+2)

题意:一开始 n×n 正方形棋盘上有 n 个互不攻击的車。然后有若干操作

1. 把所有車向一个方向推 d,不会被推出去,可能会被推到一个格子里。

2. 询问某个車的位置。

3. 询问有多少对車重叠。

题解:每行每列至多一个的作用就是少写一个数据结构(笑)。维护每个方向被挤压的数量,以及没被挤压的左上角的当前位置。重叠只可能发生在挤压构成的长方形的四个角上(长方形退化时要特判),也就是四块长方形区域内車的数量,由于范围只会扩张,所以可以用 set 维护。

Problem D

Solved by ultmaster. 01:13 (+)

题意:给一个弯道,求最小弯道宽度,使得贴着弯道内边缘和内切线飘移的车刚好能够卡过去。(车技惊人)

题解:二分答案,可以发现最难卡得地方就是那个甩尾的位置,把那个图划出来,上半段是一个分段函数大力讨论下就好了。

Problem E

Solved by zerol. 00:45 (+)

题意:求 $\min_{x \le n} \{\frac x {\sum_{i|x} \mu^2(i) \cdot i}\}$

题解:直接令 $x$ 是若干个最小的质数的积。

Problem F

Solved by ultmaster. 01:46 (+1)

Problem I

Solved by kblack. 00:52 (+)

温,咳咳咳,温暖的签,咳咳咳,签到。

Problem L

Solved by kblack. 03:09 (+)

题意:计数图上边的连通四元集合,画图好烦,用有机物了。

题解:形状分为戊烷,环丁烷,异戊烷,甲基环丙烷,新戊烷,加上修正错误的用五种计数。

第一类,枚举一个点 $u$,再枚两个相邻点对 $v, w$,$(d_v-1)(d_w-1)$,计数了一份戊烷,四份环丁烷,两份甲基环丙烷。

第二类,枚举一个点 $u$,枚举一个相邻点 $v$,$\binom{d_u-2}{2}(d_v-1)$,计数了一份异戊烷,两份甲基环丙烷。

第三类,枚举一个点 $u$,$\binom{d_u}{4}$ 计数了一份新戊烷。

现在我们要把多余的去掉。

第四类,使用四元环算法,每个对应一份环丁烷,去掉三份。

第五类,使用三元环算法,对于每个三元环 $(u, v, w)$,计数 $d_u + d_v + d_w -5$,对应一份环丙烷和一份甲基环丙烷,去掉三份。

完了。