题目连接:https://atcoder.jp/contests/abc242/tasks/abc242_e
翻译一下题目大意就是给定一个只包含大写字母的字符串S,输出所有字典序比S小且是回文串的字符串的数量
这道题直接枚举判断回文串不太好做而且会超时
我们可以从回文串入手,在S的基础上将前一般的子串翻转构造出一个回文串,这个回文串可能比S大,也可能比S小,
比如: S = "ABCZAZ", 那么我们第一步得到的回文串是: ABCCBA是比S字典序小的,那么这个回文串ABCCBA就是答案之一而且是字典序最大的
由于回文串是由前一半的字符串确定的,所以前一半字符串字典序小于ABC的字符串的数量就是答案(等于的情况后面再说)
那么如何求字典序小于ABC的的字符串的数量呢?
我们可以将只由大小字母构成的字符串看作一个26进制的数值, 那么这个26进制的数就是答案
比如:ABC的26进制值:0('A'-'A') * 26^2 + 1('B'-'A') * 26^1 + 2('C'-A') * 26^0 = 28
还有一些特殊情况:
- 如果S的长度是奇数,那么当取前一半字符串的时候将中间的一并带上,拼接另一半时将第一个字符再删掉就可以了
- 如果在S的基础上获得的回文串小于等于S,那么答案还要加1
代码:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a;i < b;i++)
#define per(i,a,b) for(int i = b - 1;i >= a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const int mod = 998244353;
int q;
int main() {
scanf("%d", &q);
rep(_,0,q) {
int n;
string s;
cin >> n >> s;
string ss = s.substr(0,(n+1)/2);
string ss2 = ss;
reverse(all(ss2));
if(n % 2) ss2.erase(ss2.begin());
ll c = 0;
rep(i,0,(int)ss.size()) {
c = (c * 26 + (ss[i] - 'A')) % mod;
}
if((ss + ss2) <= s) c = (c + 1) % mod;
printf("%lld\n", c);
}
return 0;
}
标签:26,int,ss2,ABC242,字符串,define,回文
From: https://www.cnblogs.com/junlin623/p/17048341.html