战绩:
100+80+60+72=312 rk4
T1
感觉作为签到有点难,考场一开始看了20分钟,先开了T2
卡住的原因是注意到异或并不具有结合律和分配律,那么如果我们要直接dp答案,是非常困难的
dp的本质是将相同类信息合并在一起处理
注意到异或最大值不超过128(不进位加法)
于是我们想到将异或和放到状态上,改为dp方案树,此时dp转移就很显然了
时间复杂度:\(O(nmV)\)
T2
先开的,想到了昨天的宝石,直接无脑写了,然后大样例对了,但是不会分析时间复杂度。考完了才发现是\(O(N^3)\)的
只需套用树上dp的一些小技巧,就可以降到\(n^2\)了
记\(f_{u,j}\)为点u子树中向上递增结束点为u的方案
\(g_{u,j}\)为点u子树中向上递减结束点为u的方案数
在lca处统计,用动态数组存状态
时间复杂度:\(O(n^2)\)