2018 ACM-ICPC Asia Beijing Regional Contest

From EOJ Wiki
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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一下的打表预处理,剩余的暴力计算。

总计算量为 $10^7 + 10^7 + \frac{10^9}{10^7} * \sqrt{10^9}$

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.