xjoi noip模拟赛46

t1:

模拟,卡题意坑了10分

t2:

首先nim游戏有一个性质

一个局面是必败态当且仅当这个局面所有xor起来等于0

于是就有O(nR^{2})的暴力dp

观察到信息可以合并

用快速幂优化到


O(log_n R^{2})


t3:

树形dp

f[i]表示以i为根的子树的答案

暴力转移复杂度O(nlen) len为链长度

用树剖可以做到O(n\lgn)

树剖还没有写出来..

暴力:

树剖:

待补

今天90+100+20

卡题意加忘记开两倍边,丢了20心痛..

发表评论

电子邮件地址不会被公开。 必填项已用*标注