8-29

P8275 [USACO22OPEN] 262144 Revisited P

凌晨的时候楼上的小孩在拍球（听声音感觉像铁的，，，）总之没睡好
想了半天就想出来一个O(n^3)，si了
跑去看题解发现是黑题，释怀地si了

DP-trick : 把答案和状态交换

8-21

T1

转移跳 d -> 经典根号分治

T2

树形依赖关系，价值可能为负，要求每时每刻总利润>=0

考虑子树内DP，发现每个子操作序列可用 (w,v) 概括

1. v>0
2. 合并时存在 w从小到大 的全序关系

于是考虑堆维护所有可行 (w,v) ，按全序关系不断向上合并
根据全序关系，(w,v) 加入时所有更优的父节点和相邻节点必已归于一点（可能是根，或者某个 w 更大的节点）
并查集维护当前的合并关系

代码：
判 v 的时候判了 v>=0，于是相同的 f[y] 可能多次入队

T3

经典的 超必要->充分（归纳证明） : 拼出任意 1~a <-> 对于x[1,a]，<=x的数之和>=x
考虑扩展到 (1 ~ a,1 ~ b) ，<=x的数之和>=min(x,a)+min(x,b)
本质上是分两段判

代码：强制在线的操作没认真看，拍都拍不出来