AT_ABC286C 题解
本文最后更新于 2024年9月7日 下午
思路
观察题目可以发现 A 操作最多只能执行 次,超过以后字符串又会回到初始状态。
首先考虑 A 操作如何实现,一种办法是将 在原串后复制一遍,通过移动一个记录初始位置的指针(本文中为 )来实现截取 位字符。每次移动指针代价都为 。
接下来考虑 B 操作的代价计算。我们可以判断之前截取的字符串是否为回文。回文字符串判断应该都会吧通过移动起始位置和结束位置指针,比较两指针对应的字符是否相同进行回文判断,每次遇到不同,总代价都加 。
值得注意的是结束位置指针的取值。每次 A 操作执行完成,截取出的字符串末位下标为 ,在此基础上再减去起始位置即可。
回文判断部分代码:
1 |
|
以 A 操作中起始位置指针作为外层循环变量,范围 ,内层循环为回文串判断。总时间复杂度 。
一些小细节
-
观察数据范围可知需使用 ;
-
最大值可取值 即
1ll<<62
。
完整代码
1 |
|
AT_ABC286C 题解
https://blog.makerlife.top/post/solution-ABC286C/