fzu2280 Magic(暴力+哈希预处理)

传送门

题意

q次操作，每次两种操作：

1 x y:将wx变成y

2 x：查询满足一下两个条件的字符串（①以字符串x为后缀②字符串值\(\le wx\)）

分析

对n个字符串预处理，设f[i][j]为第i个字符串0~j的子串哈希值。

再用v[i]记录以字符串i为后缀的字符串，统计的时候扫一遍

复杂度\(O(n^2+n*q)\)

trick

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

int t,n;

char s[1010][1010];

int a[1010],f[1010][1010],len[1010];

int q,judge,x,y;

vector<int>v[1010];//v[x][i]表示x是v[x][i]的后缀

int base[1010];

const int mod = 1000173169;

const int seed = 131;//取奇数质数 31 131

void init()

{

  base[0]=1;

  F(i,1,1000) base[i]=(ll)base[i-1]*seed%mod;

}

void op1()

{

  F(i,1,n)

  {

    f[i][0]=0;

    F(j,1,len[i]) f[i][j]=((ll)f[i][j-1]*seed%mod+s[i][j])%mod;

  }

}

int Hash(int x,int l,int r)

{

  return (f[x][r]-(ll)f[x][l-1]*base[r-l+1]%mod+mod)%mod;

}

void op2()

{

  F(i,1,n)

  {

    v[i].push_back(i);

    F(j,i+1,n)

    {

      if(len[i]==len[j])

      {

        if(Hash(i,1,len[i])==Hash(j,1,len[j])) v[i].push_back(j),v[j].push_back(i);

      }

      else if(len[i]>len[j])

      {

        if(Hash(i,len[i]-len[j]+1,len[i])==Hash(j,1,len[j])) v[j].push_back(i);

      }

      else

      {

        if(Hash(i,1,len[i])==Hash(j,len[j]-len[i]+1,len[j])) v[i].push_back(j);

        //printf("Hash[%d][%d]=%d\n", );

      }

    }

  }

}

int main()

{

  init();

  for(scanf("%d",&t);t--;)

  {

    scanf("%d",&n);

    F(i,1,n)

    {

          scanf("%s%d",s[i]+1,a+i);

          len[i]=strlen(s[i]+1);

          v[i].clear();

    }

  op1();

  op2();

  //F(i,1,n) printf("%d\n",v[i].size() );

  for(scanf("%d",&q);q--;)

  {

    scanf("%d",&judge);

    if(judge==1)

    {

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

      a[x]=y;

    }

    else

    {

      scanf("%d",&x);

      int sz=v[x].size(),sum=0;

      R(i,0,sz) if(a[v[x][i]]<=a[x]) sum++;

      printf("%d\n", sum);

    }

  }

}

}

巴特西

fzu2280 Magic(暴力+哈希预处理)

传送门

题意

分析

trick

代码

最新文章

热门文章