Difference between revisions of "Moscow Pre-Finals Workshop 2016 National Taiwan U Selection"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 31: | Line 31: | ||
考虑启发式合并,枚举小的一部分中的状态,在另一部分的 Trie 上贪心的跑。 | 考虑启发式合并,枚举小的一部分中的状态,在另一部分的 Trie 上贪心的跑。 | ||
− | $10^9$ 的数,二进制只开了 $ | + | $10^9$ 的数,二进制只开了 $20$ ,最后一个小时意识模糊,啥也没发现,背大锅。 |
== Problem C == | == Problem C == |
Revision as of 17:01, 8 May 2019
_
本来可以超 F0RE1GNERS 一题的, Xiejiadong 一番操作以后,差点签到都直接没了。
Problem A
Solved by Xiejiadong. 3:14 (+3)
题意:求一段子串里面子序列包含多少个不连续的 "easy" 。
题解:考虑倍增,用数组 $f[i][j]$ 表示位置 $i$ 之后的 $2^j$ 个 "easy" 的结束位置。
不需要考虑段与段之间连接的时候产生问题,这一点可以通过只考虑 "e" 作为开始的位置来证明。
暴力转移以后,每次贪心的取,不断的截取,获得答案即可。
明明可以暴力求幂的,偏要写快速幂,写了快速幂还写错了,身败名裂。
Problem B
Upsolved by Xiejiadong. (-3)
题意:求最小生成树,边权为两点值得异或。
题解:建立 Trie 。显然产生生成树的方式是子树中的点联通以后,再通过 lca 连接。
因为异或我们可以把长度补成一样的,所以只有最底层的叶子结点是有效的信息。
问题转换成了对于一个既有左孩子,又有右孩子的节点,需要在两边各找一个点,使得他们的异或结果是最小的。
考虑启发式合并,枚举小的一部分中的状态,在另一部分的 Trie 上贪心的跑。
$10^9$ 的数,二进制只开了 $20$ ,最后一个小时意识模糊,啥也没发现,背大锅。
Problem C
Unsolved.
Problem D
Solved by Kilo_5723. 2:41 (+1)
Problem E
Unsolved.
Problem F
Solved by Weaver_zhu. 0:25 (+)
Problem G
Unsolved.
Problem H
Unsolved. (-1)
Problem I
Solved by Weaver_zhu. 3:34 (+4)
Problem J
Solved by Kilo_5723. 0:53 (+4)