AT_ABC286C 题解

思路

观察题目可以发现 A 操作最多只能执行 $n$ 次，超过以后字符串又会回到初始状态。

首先考虑 A 操作如何实现，一种办法是将 $S$ 在原串后复制一遍，通过移动一个记录初始位置的指针（本文中为 $i$ ）来实现截取 $n$ 位字符。每次移动指针代价都为 $A$ 。

接下来考虑 B 操作的代价计算。我们可以判断之前截取的字符串是否为回文。~~回文字符串判断应该都会吧~~通过移动起始位置和结束位置指针，比较两指针对应的字符是否相同进行回文判断，每次遇到不同，总代价都加 $B$ 。

值得注意的是结束位置指针的取值。每次 A 操作执行完成，截取出的字符串末位下标为 $n+i-1$ ，在此基础上再减去起始位置即可。

回文判断部分代码：

/*i 为 A 操作中起始位置指针，t 为总代价*/
for(int j=0;j<n/2;j++)//回文判断循环变量只需到 n/2
{
int x=i+j;//起始位置
int y=n+i-1-j;//结束位置
if(s[x]!=s[y])
{
t+=b;
}
}

以 A 操作中起始位置指针作为外层循环变量，范围 $0\sim n-1$ ，内层循环为回文串判断。总时间复杂度 $O(n^2)$ 。

一些小细节

观察数据范围可知需使用 $\text{long long}$ ；
最大值可取值 $2^{62}$ 即 1ll<<62。

完整代码

#include<cstdio>
#include<string>
#include<iostream>
#define INF 1ll<<62
#define ll long long
#define int ll
using...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Makerlife 的小站
Makerlife 的小站
马上订阅 Makerlife 的小站 RSS 更新: https://blog.makerlife.top/atom.xml
AT_ABC286C 题解
2023年1月28日 17:01
洛谷题目传送门 | AT 原题传送门
思路
观察题目可以发现 A 操作最多只能执行  $n$  次，超过以后字符串又会回到初始状态。
首先考虑 A 操作如何实现，一种办法是将  $S$  在原串后复制一遍，通过移动一个记录初始位置的指针（本文中为  $i$ ）来实现截取  $n$  位字符。每次移动指针代价都为  $A$ 。
接下来考虑 B 操作的代价计算。我们可以判断之前截取的字符串是否为回文。回文字符串判断应该都会吧通过移动起始位置和结束位置指针，比较两指针对应的字符是否相同进行回文判断，每次遇到不同，总代价都加  $B$ 。
值得注意的是结束位置指针的取值。每次 A 操作执行完成，截取出的字符串末位下标为  $n+i-1$ ，在此基础上再减去起始位置即可。
回文判断部分代码：
1
2
3
4
5
6
7
8
9
10
/*i 为 A 操作中起始位置指针，t 为总代价*/
for(int j=0;j<n/2;j++)//回文判断循环变量只需到 n/2
{
int x=i+j;//起始位置
int y=n+i-1-j;//结束位置
if(s[x]!=s[y])
{
t+=b;
}
}
以 A 操作中起始位置指针作为外层循环变量，范围  $0\sim n-1$ ，内层循环为回文串判断。总时间复杂度  $O(n^2)$ 。
一些小细节
观察数据范围可知需使用  $\text{long long}$ ；
最大值可取值  $2^{62}$  即 1ll<<62。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<string>
#include<iostream>
#define INF 1ll<<62
#define ll long long
#define int ll
using...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Makerlife 的小站
Makerlife 的小站
马上订阅 Makerlife 的小站 RSS 更新: https://blog.makerlife.top/atom.xml
AT_ABC286C 题解
2023年1月28日 17:01
洛谷题目传送门 | AT 原题传送门
思路
观察题目可以发现 A 操作最多只能执行  $n$  次，超过以后字符串又会回到初始状态。
首先考虑 A 操作如何实现，一种办法是将  $S$  在原串后复制一遍，通过移动一个记录初始位置的指针（本文中为  $i$ ）来实现截取  $n$  位字符。每次移动指针代价都为  $A$ 。
接下来考虑 B 操作的代价计算。我们可以判断之前截取的字符串是否为回文。回文字符串判断应该都会吧通过移动起始位置和结束位置指针，比较两指针对应的字符是否相同进行回文判断，每次遇到不同，总代价都加  $B$ 。
值得注意的是结束位置指针的取值。每次 A 操作执行完成，截取出的字符串末位下标为  $n+i-1$ ，在此基础上再减去起始位置即可。
回文判断部分代码：
1
2
3
4
5
6
7
8
9
10
/*i 为 A 操作中起始位置指针，t 为总代价*/
for(int j=0;j<n/2;j++)//回文判断循环变量只需到 n/2
{
int x=i+j;//起始位置
int y=n+i-1-j;//结束位置
if(s[x]!=s[y])
{
t+=b;
}
}
以 A 操作中起始位置指针作为外层循环变量，范围  $0\sim n-1$ ，内层循环为回文串判断。总时间复杂度  $O(n^2)$ 。
一些小细节
观察数据范围可知需使用  $\text{long long}$ ；
最大值可取值  $2^{62}$  即 1ll<<62。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<string>
#include<iostream>
#define INF 1ll<<62
#define ll long long
#define int ll
using...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章