codeforces round #297 题解

上古题解,感谢黄学长的悉·心·栽·培qwq

A. Vitaliy and Pie

贪心,遇到小写就将对应钥匙+1,遇到大写如果有钥匙就-1钥匙,没有钥匙就买一个(答案++)

B. Pasha and String

我:先记录一下不同的位置各翻转了多少次,同一区间翻转两次相当于没有进行任何操作,所以直接%2。然后模拟一下输出
hzwer:差分+前缀和记录翻转 传送门

C. Ilya and Sticks

贪心地选取尽可能长的木棒来组成矩形。
证明:对于a<=b<=c<=d,c*d+a*b >= a*d+c*b,c*d+a*b >= a*c+b*d

D. Arthur and Walls

D题的结论是四个格子里面有一个是”*”就把它删除,证法不明

E. Anya and Cubes

构造数据好恶心……写的不太优美= =
总结一下可能导致TLE的点:
1.滥用long long
2.递归传参太多
3.mp的查询操作,多了几乎一倍的计算量
4.没有“老司机的经验”:用奇怪的方法剪枝
折半搜索:搜索量太大,分解成两个局部分别求过程中的解,再组合在一起找最终解
对于这个问题:把所有的数据分为两组,分别求出可能组合出的所有值,再加在一起看是否=S。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注