CF245H Queries for Number of Pal

题目描述

给你一个字符串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;
}