CFR607

CFR607 div1

因为来晚了决定不会做C就跑路,猜个结论感性理解再举了挺多例子都没问题,但有点犹豫,慢吞吞写完就过了,暂时rk40显然是没意义的,然后前四题题面都巨长,慢吞吞看题面慢吞吞写,20minA+20minB,剩下1h自闭

然后A就光荣fst了,菜的真实.jpg

CF1280A Cut and Paste

请先思考后再展开

显然暴力维护str的前x位,code

光荣fst,原因是str=str+tmp;22这种极端情况可能执行n次,改成str+=tmp就过了,被教育了

CF1280B Beingawesomeism

请先思考后再展开

显然是个讨论题,从小到大判断

全P则无解,全A则0,否则上界是4

如果边界的四个块某个全A,则1

如果某行或列全A、四个角格有A,则2

边界有A则3

code

CF1280C Jeremy Bearimy

题意:给出一个大小为2k的边带权树,将点分为k对,问最小及最大路径和,$k \le 1e5$

请先思考后再展开

这种最优化问题我的第一想法是看看上下界,发现一条边如果$siz_{son}$奇肯定要选,而且选的次数不会超过$min(siz_{son},2k-siz_{son})$

画了些情况发现似乎都能达到,code

赛后想想怎么证,首先下界那个可以考虑从叶子开始做,如果父亲有其他叶子就和其他叶子匹配;上界的话,其实感性理解还是挺对的,暂时不会严谨证明

CF1280D Miss Punyverse

题意:给出一棵点带权树,问分割成m个联通块后,最大化权值和为正的联通块的数量,$n,m \le 3e3,\sum n \le 1e5$

请先思考后再展开

$dp(x,保留多少边,正块数)=x所在块能达到的最大和$,一般都是套个贪心,大胆猜测正块数这一维只存最大的

一如既往不会严谨证明,$O(n^2)$,code

CF1280E Kirchhoff’s Current Loss

咕咕咕

CF1280F Intergalactic Sliding Puzzle

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c9a4b97f.html
转载请注明出处,谢谢!