Difference between revisions of "2018 ACM-ICPC Asia Beijing Regional Contest"
Jump to navigation
Jump to search
(→Replay) |
Xiejiadong (talk | contribs) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 4: | Line 4: | ||
* 打崩了 | * 打崩了 | ||
| + | |||
| + | * 会做的题没时间做了 | ||
dreamcloud: | dreamcloud: | ||
| Line 36: | Line 38: | ||
Upsolved by oxx1108. (-11) | Upsolved by oxx1108. (-11) | ||
| − | |||
题意：求$1e9$下有多少本质不同的勾股数 | 题意：求$1e9$下有多少本质不同的勾股数 | ||
| − | |||
题解：有本原勾股数可以将式子化简为求有多少互素的奇数 x 和偶数 y 使得 $x ^ 2 + y ^ 2$ 小于等于 n。 | 题解：有本原勾股数可以将式子化简为求有多少互素的奇数 x 和偶数 y 使得 $x ^ 2 + y ^ 2$ 小于等于 n。 | ||
| − | |||
暴力将1e7一下的打表预处理。剩下的部分用莫比乌斯可以将互素的条件扔掉后再次分块将1e7一下的打表预处理，剩余的暴力计算。 | 暴力将1e7一下的打表预处理。剩下的部分用莫比乌斯可以将互素的条件扔掉后再次分块将1e7一下的打表预处理，剩余的暴力计算。 | ||
| − | + | 总计算量为 $10^7 + 10^7 + \frac{10^9}{10^7} * \sqrt{10^9}$ | |
| − | 总计算量为 | ||
== Problem D == | == Problem D == | ||
Latest revision as of 13:58, 19 December 2018
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.