22.10.31补卡 22CCPC桂林C题

Problem - C - Codeforces

这题题解是请教了学长之后才做出来的, 若是想看题解请看http://t.csdn.cn/unAyg

本篇文章只作为做题记录

写了一天半...感觉自己是不太适合写区域赛的题了, 还是多学学算法和数论好了

-----------------------------------------------------------------------------------------------------------------------

自己推了一个小时之后就不耐烦看题解了

 最后看学长题解, 自己一开始推了一半的结论其实是没错的...错在我没有坚持下来就看了题解

做法2没看懂, 所以使用了做法1的公式

我的思路是这样的, 分别记录操作1和操作2的 前缀和 和 前缀和之和 直接取最大值然后套公式输出, 错误代码示范

写了半天跑出来的结果是这样的

 跑去问队友lk, 他说把前面取模去掉了变成wa4, 很神奇, 然后我就疯狂的试取模, 发现了这一句

也就是说, 答案取模之后就不一定是最大值了! 改了半天结果还是

实在做的难受, 跑去问了学长, 学长好心写了篇题解, 一瞬间疑云消散...明白了做法1和做法2的真正意义...

假设操作1为A, 操作2为B

那么一共会有

AAA...A

AAA...B

AA...BB

..

BBB...B

m种序列

而真正意义上的最大, 是A和B操作各取一半 或 全取A的情况

做法1是计算了全部序列, 枚举B从哪里开始取, 取最大值 Om

做法2推出了 A和B操作各取一半 或 全取A的情况 这个结论 O1

---------------------------------------------------------------------------------------------------------------------------------

终于把这题ac了, 感觉学到了许多, 但确实目前阶段刷区域赛的题对于我来说还是太难了, 让我多学点算法明年战区域赛!

途中还了解了个费马小定理(还不能说会), 2的n次幂*ksm(2,mod-2)相当于2的n-1次幂