hdu 4622 Reincarnation

时间：2021-10-13 11:48:02

http://acm.hdu.edu.cn/showproblem.php?pid=4622

用字典树把每一个字符串对应成一个整数 相同的字符串对应到相同的整数上

把所用的串对应的整数放在一个数组里 比如书字符串s[l...r]对应的整数是 k

那么二维数组 [l][r] 就等于k

假设一个对应好的二维数组  左下角是原点

3     4     5     2

2     3     4     0

1     6     0     0

2     0     0     0

这样求解 从l到r的不同字符串的个数 其实就是求 从[l][r] 到右下角所在的矩阵所包含不同整数的个数(不包括0)

这里需要一定的去重处理 处理后是

-1    0    1     1

0     1    1     0

1     1    0     0

1     0    0     0

然后一边dp就可以求出所有答案

注意常用的next[26]写法的字典树有可能超内存 要优化

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

using namespace std;

typedef long long ll;

typedef pair<double,double>ppd;

const double PI = acos(-1.);

const double eps = (1e-9);

const int N=2005;

const int M=2000000;

const int K=27;

char s[N];

int c[N][N];

int last[M];

struct node

{

    int head;

    int k;

}trie[M];

struct node1

{

    int j,next;

    char c;

}edge[M];

int num,cnt,I;

int add(char a,int &x)

{

    bool flag=false;

    for(int t=trie[x].head;t!=-1;t=edge[t].next)

    {

        if(edge[t].c==a)

        {flag=true;x=edge[t].j;break;}

    }

    if(flag==true)

    return trie[x].k;

    trie[cnt].head=-1;

    trie[cnt].k=num++;

    edge[I].c=a;

    edge[I].j=cnt;

    edge[I].next=trie[x].head;

    trie[x].head=I++;

    x=cnt++;

    return trie[x].k;

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        trie[0].head=-1;

        trie[0].k=-1;

        I=0;num=1,cnt=1;

        memset(c,0,sizeof(c));

        memset(last,-1,sizeof(last));

        scanf(" ");

        gets(s);

        int n=strlen(s);

        for(int j=0;j<n;++j)

        for(int i=j,t=0;i>=0;--i)

        {

            int x=i+1;

            int y=j+1;

            int k=add(s[i],t);

            if(last[k]==-1)

            {

                last[k]=x;

                ++c[x][y];

            }else if(last[k]<x)

            {

                ++c[x][y];

                --c[last[k]][y];

                last[k]=x;

            }

        }

        for(int j=1;j<=n;++j)

        for(int i=n;i>=1;--i)

        c[i][j]+=c[i][j-1]+c[i+1][j]-c[i+1][j-1];

        int q;

        scanf("%d",&q);

        while(q--)

        {

            int x,y;

            scanf("%d %d",&x,&y);

            printf("%d\n",c[x][y]);

        }

    }

    return 0;

}

相关文章