今天考试内容比较没有头绪,第一道题看样子是序列上的dp,好像又有后效性,就很无奈。干脆写了随机化,最后拿了50分。正解确实是dp,裸的dp能拿50分,如果用Lowerbound和线段树来初始化,用线段树转移状态,就能拿到满分。时间复杂度为$O(n\log_2n)$,要注意一些细节,改了很久。

9-21
今天上午做了三题:
Run 最小生成树+倍增,可能是倍增写错了,爆零,需要继续调试。后来发现倍增确实写错了,但是没有再次调试这道题。
Nim 涉及到博弈论,不会做。正解是奇数行的亦或值是否为1
Toy 应该是树形dp,我写了暴力。正解是选或不选这个点,如果不选这个点,子节点就必须有选的
下午:
Sequence 正解是O(n)算法,我只想到