首页 > 其他分享 >ABC242 E - (∀x∀)

ABC242 E - (∀x∀)

时间:2023-01-13 00:22:43浏览次数:62  
标签:26 int ss2 ABC242 字符串 define 回文

题目连接: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

还有一些特殊情况:

  1. 如果S的长度是奇数,那么当取前一半字符串的时候将中间的一并带上,拼接另一半时将第一个字符再删掉就可以了
  2. 如果在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

相关文章

  • ABC242F
    套路的二项式反演。题目要求实际就是两种颜色的棋子所占的行和列都不能有交。设\(f(i,j,k)\)表示在\(i\)行\(j\)列中放\(k\)个棋子使得每行,每列都不为空的方案数......