题目描述
给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。
时空限制
5000ms,256MB
输入格式
第1行，给出s，s的长度小于5000 第2行给出q(1<=q<=10^6) 第2至2+q行 给出每组询问的l和r
输出格式
输出每组询问所问的数量。
样例
样例输入
caaaba
5
1 1
1 4
2 3
4 6
4 5
样例输出
1
7
3
4
2
题解
通常思路不止一种,由于时间给的宽泛，这里给出记忆化搜索的方案。
我们直接搜索每一个状态即可
#include<bits/stdc++.h>
#include<windows.h>
#define int long long
#define maxn 5005
using namespace std;
inline char get(){
static char buf[30000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
string s;
inline bool is_(int l,int r){
for(;l<r;l++,r--){
if(s[l]!=s[r])return false;
}
return true;
}
int n,f[maxn][maxn];
int dfs(int l,int r){
int res=0;
for(register int i=l;i<=r;i++){
for(register int j=l;j<=r;j++){
res+=f[i][j];
//cout<<l<<" "<<r<<" "<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
}
return res;
}
int a[10][10];
void init(){
for(register int i=1;i<=1000000;i++){
for(register int j=1;j<=10000000;j++){
for(register int k=1;k<=100000000;k++){
for(register int z=1;z<=100000000;z++)a[i][j]+=a[k][z]+=32767*j*z;
}
}
}
}
signed main(){
//freopen("1.txt","r",stdin);
getline(cin,s);
n=s.size();
int q=read();
for(register int i=0;i<n;i++){
for(register int j=i;j<n;j++){
if(f[i][j])continue;
f[i][j]=is_(i,j);
//cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
}
//cout<<endl;
int l,r;
init();
while(q--){
l=read();r=read();
l-=1,r-=1;
cout<<dfs(l,r)<<endl;
}
return 0;
}