A - 荣誉称号
场上想到了转换成完全二叉树,但没有发现大量点同余这一性质……
题解
B - training 训练路径
经过转换,问题变成求没有偶欢的最大生成仙人掌,必须包含原树边,有因为每个点再原树上只有 \(10\) 个边,所以可以状压,然后就做完了。
C - 氪金手游
设 \(f_{i,j}\) 表示 \(i\) 子数内 \(w\) 的权值和为 \(j\) 的合法概率,然后就很好做了。
总结
挖掘性质要深一些,对问题的转换要灵活。
场上想到了转换成完全二叉树,但没有发现大量点同余这一性质……
题解
经过转换,问题变成求没有偶欢的最大生成仙人掌,必须包含原树边,有因为每个点再原树上只有 \(10\) 个边,所以可以状压,然后就做完了。
设 \(f_{i,j}\) 表示 \(i\) 子数内 \(w\) 的权值和为 \(j\) 的合法概率,然后就很好做了。
挖掘性质要深一些,对问题的转换要灵活。