Codeforces 159D Palindrome pairs

时间：2021-12-03 23:37:58

http://codeforces.com/problemset/problem/159/D

题目大意：

给出一个字符串，求取这个字符串中互相不覆盖的两个回文子串的对数。

思路:num[i]代表左端点在i这个位置的回文串个数，然后用树状数组维护sum[i],代表回文串右端点小于等于i的回文串数，总复杂度:O(n^2)

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #define ll long long

 ll c[],num[];

 int pd[][],n;

 char s[];

 int lowbit(int x){

     return x&(-x);

 }

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void add(int x){

     for (int i=x;i<=n;i+=lowbit(i)){

         c[i]++;

     }

 }

 int ask(int x){

     int res=;

     for (int i=x;i;i-=lowbit(i)){

         res+=c[i];

     }

     return res;

 }

 int main(){

     scanf("%s",s+);

     n=strlen(s+);

     for (int i=;i<=n;i++)

      pd[i][i]=,add(i),num[i]++;

     for (int i=;i<n;i++)

      if (s[i]==s[i+]) pd[i][i+]++,add(i+),num[i]++;

     for (int len=;len<=n;len++)

      for (int i=;i+len-<=n;i++){

         int j=i+len-;

         if (pd[i+][j-]&&s[i]==s[j]) pd[i][j]=,add(j),num[i]++;

      }

     ll ans=;

     for (int i=;i<=n;i++)

       ans+=ask(i-)*((ll)(num[i]));

     printf("%I64d\n",ans);

     return ;

 }

相关文章