Difference between revisions of "2019 ICPC Xuzhou Onsite"
Line 95: | Line 95: | ||
− | 题意:定义 critical point 为树上点 $u, c(w) = \sum\limits_{v\in T}d(w,v), c(u) = min\{c(w)\}$ | + | 题意:定义 critical point 为树上点 $u, c(w) = \sum\limits_{v\in T}d(w,v), c(u) = min\{c(w)\}$,然后求有根树每个子树的 critical point |
题解:critical point 就是重心,考虑当前重心,一定在孩子子树重心到自己的路径上,二分(二分一阶导数,也就是移动一格的代价,也就是子树大小和子树外大小)就完事了 | 题解:critical point 就是重心,考虑当前重心,一定在孩子子树重心到自己的路径上,二分(二分一阶导数,也就是移动一格的代价,也就是子树大小和子树外大小)就完事了 |
Revision as of 07:47, 3 December 2019
Replay
Xiejiadong:
- 银川以后整个队伍就有一种任务达成的迹象。整个训练的状态极差。
- 开局前半小时甚至提交都没有。第一发提交 A 还 wa 了,第二发提交 A 又 wa 了,而且此时 Kilo 和 Weaver 在 A 和 C 疯狂交互上机,手里握着一个 F ,感觉这把要打 Cu 滚回去了。
- 可喜的是,前期三题过去以后,基本都是 1A 到了中后场,算是挽救了一把。
- 总算做到了一道纯字符串题。
- 左手东华,右手上大,上海三连坐。
- 完成了 “不丢脸” 的小目标。
- 恭喜蔡队出线。
Kilo_5723:
Weaver_zhu:
Problem A
Solved by Kilo_5723. 00:55 (+2)
Problem B
Unsolved.
Problem C
Solved by Weaver_zhu. 00:46 (+)
题意:判断区间素数密度大于 $\frac{1}{3}$ 题解:大的区间不要了,小的区间筛。开场写了 min25,又怕被卡常重构代码,其实不会卡
Problem D
Unsolved.
Problem E
Solved by Weaver_zhu. 02:30 (+)
题意:$Z = a_1! \times ... \times a_n!$ 求 最大的 $i$ 使得 $b_i=Z \times X^i$ 能整除 $Y$
题解:统计素数个数就完事了,据隔壁队说卡常,侥幸一遍过
Problem F
Solved by Xiejiadong. 01:26 (+)
题意:给出 $x$ 求任意一组解满足 $a^3+b^3+c^3=x$ 且 $|a|,|b|,|c|\le 5\cdot 10^3,0\le x\le 200$ 。
题解:考虑预处理出所有 $|a|,|b|\le 5\cdot 10^3$ 的情况,枚举所有的 $x$ ,再枚举 $c$ ,判断是否存在这样的 $a,b$ 。
直接用 map 是不大行的,无论是时间复杂度还是内存上本地都跑不出来,差点电脑死机了。
考虑用数组存下所有的情况,排序以后,再在其中二分。
打表直接输出即可。
Problem G
Unsolved.
Problem H
Solved by Kilo_5723. 03:57 (+1)
Problem I
Unsolved.
Problem J
Unsolved. (-5)
Problem K
Unsolved.
Problem L
Solved by Xiejiadong. 03:24 (+)
题意:给出一棵树,树上每个节点都有一个字母,每次可以选择一个节点,从它开始向他的父节点走,沿路记下字母。
每次询问给出一个节点以及走的步数,求整棵树上可以走出多少这样的字符串。
题解:考虑如果对于每一个节点变成向他的孩子走,题目就转换成了后缀的问题。
如果能够处理出来所有节点往下走的字符串,建立 SAM ,在其中做子串定位以及统计当前子串状态出现的次数就好了。
考虑到这是一个树,每次记录当前节点对应在广义 SAM 的节点编号,回溯的时候,暴力的跳父亲的 SAM 节点,在 insert 即可。
Problem M
Solved by Weaver_zhu && Kilo_5723. 01:50 (+)
题意:定义 critical point 为树上点 $u, c(w) = \sum\limits_{v\in T}d(w,v), c(u) = min\{c(w)\}$,然后求有根树每个子树的 critical point
题解:critical point 就是重心,考虑当前重心,一定在孩子子树重心到自己的路径上,二分(二分一阶导数,也就是移动一格的代价,也就是子树大小和子树外大小)就完事了