CF1929

CF1929 总结

Url:https://codeforces.com/contest/1929

Rating:https://codeforces.com/bestRatingChanges/12561378

C

误解了题意，以为赌场会配合他前面x次都输然后赢最后一场。原来赌场不会配合Sasha。他要分配最好策略，不论赌场怎么搞都能赚钱。

然后注意取整，本来想hack一个人，没hack到，其实hack本来就假了，要是hack反而掉standing。

D

无脑 dp

E

状压，建立虚树，发现不同状态个数 \(O(k)\) 个，然后dp即可。

此处使用虚树思想是难点，然后dp使用刷表法更为轻松。对于一个点对更新状态，可以树上差分 \(O(n)\)，不然暴力lca \(O(k^2)\)

F

F比E简单：二叉搜索树，将编号升序转换到值升序，建立单满射。然后对于不确定的区间差分，接着stars and bars。因为值域很大，再注意一下组合数转换，转换到len即可。后场策略确实出现问题，应当去看F而不是hack C题。场后C题无人hack成功。