首页 > 其他分享 >CF245H Queries for Number of Palindromes

CF245H Queries for Number of Palindromes

时间:2023-02-24 00:55:24浏览次数:43  
标签:Palindromes return int Number vis CF245H include pal

对字符串s,多次询问,给你两个数L和R,问在字符串区间l到r的字串中,包含多少回文串。

 

#include <iostream>
#include<queue> 
#include <cstring>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
 const int N =5003;
 
 int vis[N][N],pal[N][N];
 int f[N][N];
 string s;
 int n;
 int test(int a,int b){
     if(a>=b) return 1;
     if(s[a]!=s[b]) return 0;
     if(vis[a][b]) return pal[a][b];
     vis[a][b]=1;
     
     return pal[a][b]=test(a+1,b-1);
 }
 void solve(){
 	int i,j,tes;
 	cin>>s>>tes; n=s.size(); 
 	s=" "+s;
 	
 	for(int i=1;i<=n;i++)	f[i][i]=1;						
	for(int i=1;i<=n-1;i++)	f[i][i+1]=(s[i]==s[i+1]?3:2);
 	
 	for(i=n-2;i>=1;i--)
 	 for(j=i+2;j<=n;j++)
 	  f[i][j]=(f[i+1][j]+f[i][j-1]-f[i+1][j-1]+(test(i,j)?1:0));
 	
 	while(tes--){
 		int x,y;
 		cin>>x>>y;
 		cout<<f[x][y]<<endl;
 	}
 }
 signed main(){
     IOS;
     solve();
 }
 
 

 

标签:Palindromes,return,int,Number,vis,CF245H,include,pal
From: https://www.cnblogs.com/towboa/p/17149980.html

相关文章