[nk] 牛客月赛51 G计算题

前言

t a g : tag : tag:字符串 回文串 hash 二分 难 传送门 :

题意 :

你有一个长度为 n n n的字符串，你可以选择删除一段后缀（可以为空），然后修改剩余串中的一个字符，使其变成回文串。请问最后能生成多少种可能的回文串。 需要保证整个过程中的字符集仅包含小写字母。其中修改操作必须修改，但可将字符修改为原字符。

思路 : 我们可以将剩余字符串分为三类 本身就是回文,差两个回文,差很多回文

对于本身就是回文的 如果是奇数长度那么贡献 + 26 +26 +26,否则贡献 + 1 +1 +1

对于差一个回文的 因为奇数中间必然不可能非回文的,所以奇数==偶数情况。写几下可知贡献 + 2 +2 +2

下面就是判断是否回文

显然我们可以先计算 哈希数组 当正反 哈希相等的时候就是回文

那么如何判断差一个回文呢

我们这里可以通过 二分

取中间点为起点,然后二分长度

当 m i d − l e n , m i d + l e n mid-len,mid+len mid−len,mid+len的哈希值相等是时候,显然不是,继续二分

因此具有单调性

超级难写 code :

// Problem: 计算题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11228/G
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define ull long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr