2018 ACM-ICPC Asia Beijing Regional Contest

Replay

oxx1108:

dreamcloud:

Xiejiadong:

• 北大的肯德基真好吃。

• 签到罚时，甩锅

• 气球是氦气球，好评，不过气球怎么老是漏气啊

• 餐券用到用不完，甚至还送了隔壁队90多

Problem A

Solved by Xiejiadong. 0:56:37(+2)

A题两发罚时的锅我不背。 签到题。 每次新加一条边，判断是否成环即可。

Problem B

Solved by Xiejiadong. 3:25:16(+1)

题意：提取文本中的所有数字，如果行末是数字，第二行的行首是数字的，应该连起来。

题解：模拟。全是细节。

Problem C

Upsolved by oxx1108. (-11)

题意：求$1e9$下有多少本质不同的勾股数

题解：有本原勾股数可以将式子化简为求有多少互素的奇数 x 和偶数 y 使得 $x ^ 2 + y ^ 2$ 小于等于 n。

暴力将1e7一下的打表预处理。剩下的部分用莫比乌斯可以将互素的条件扔掉后再次分块将1e7一下的打表预处理，剩余的暴力计算。

总计算量为 1e7 + 1e7 + (1e9 / 1e7) * sqrt（1e9）

Problem D

Solved by oxx1108. 1:56:26(+1)

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by dreamcloud. 4:48:24(+)

题意：一个模式串相对于原串是好的，当且仅当他是原串的子串，或者子串修改某一个字母，给出模式串和原串的长度，求原串的方案数。

题解：拿模式串和模式串修改一位作为所有的模板串，建立AC自动机，然后在上面跑dp。

$f[i][j]$表示已经用了$i$位，当前匹配到AC自动机上的$j$位的方案树，暴力地向孩子节点转移。

最后统计所有叶子结点的方案数即可。

Problem I

Solved by dreamcloud. 3:54:24(+3)

Problem J

Unsolved.