2018 ACM-ICPC Asia Beijing Regional Contest

From EOJ Wiki
Revision as of 13:58, 19 December 2018 by Xiejiadong (talk | contribs) (→‎Problem C)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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.