在家的又一场.
状态还是一般吧.
自己扔了 30 分.
T1
比较厉害的 \(dp\), 考场上想到了, 结果因为细节太多就没有写 (真的是多).
他其实就是个基环树 dp.
我们首先断掉环上某个边, 然后进行一次最大匹配的 \(dp\), 然后这样要求这个边必然不选.
另一种情况是这个必然选, 那么这条边终点的出边必然不选, 再次断那个出边 再 \(dp\) 一次得到答案.
考虑如何输出方案.
对于一个位置我们记录这个点的最大值出现在 \(0/1\) 上.
然后根据这个找到最佳方案所依赖的子节点方案.
即可输出方案了.
T2
是 hash 的题.
枚举答案区间中的颜色集合.
对每个位置开个桶, 记录一下当前位置的前缀和.
然后根据这些位置和集合中最后一个元素的前缀和的差进行 hash.
存放入 hash 表中即可, 对于某一个右端点快速的查询对应最优的左端点.
T3
被我用随机化过了, 有人写 2-sat, 也有搜索的.
随机化出序列, 然后贪心的加入两个集合, 就是枚举加入哪个集合使得当前答案更小即可.
这样多做几次
使得单个询问复杂度为 2e8 就能过了.
来源: http://www.bubuko.com/infodetail-3400004.html