【HDOJ6223】Infinite Fraction Path（后缀数组）

2021-05-23 10:30

阅读：492

标签：应该 signed set bre 字典序位置 long swap int

题意：

给一个长度为n的字符串s[0..n-1]，但i的后继不再是i+1，而是(i*i+1)%n，求所有长度为n的“子串”中，字典序最大的是谁

思路：后缀数组

因为前驱与后继的关系已经变化，就不能用下标直接加减

i的后继是唯一的，i的前驱却不一定

所以对于后继使用倍增，对于前驱每个位置暴力开队列存储，需要的时候再拿出来

在判断的地方稍作修改

  1 #include  2 #include  3 #includestring>
  4 #include  5 #include  6 #include
  7 #include  8 #includeset>
  9 #include 10 #include 11 #include 12 using namespace std;
 13 typedef long long ll;
 14 typedef unsigned int uint;
 15 typedef unsigned long long ull;
 16 typedef pairint,int> PII;
 17 typedef vectorint> VI;
 18 #define fi first
 19 #define se second 
 20 #define MP make_pair
 21 #define N   310000
 22 #define MOD 1000000007
 23 #define eps 1e-8 
 24 #define pi acos(-1)
 25 queueint> q[N];
 26 
 27 char ch[N];
 28 int n,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],Rank[N],
 29     f[N][19];
 30     
 31 
 32 int read()
 33 { 
 34    int v=0,f=1;
 35    char c=getchar();
 36    while(c48||57if(c==‘-‘) f=-1; c=getchar();}
 37    while(4857) v=(v3)+v+v+c-48,c=getchar();
 38    return v*f;
 39 }
 40 
 41 bool cmp(int *r,int a,int b,int l)
 42 {
 43     return r[a]==r[b]&&r[f[a][l]]==r[f[b][l]];
 44 //    return r[a]==r[b]&&r[a+l]==r[b+l]; 原来的写法 
 45 }
 46 
 47 void getsa(int *r,int *sa,int n,int m)
 48 {
 49 //    printf("\n");
 50     int *x=wa,*y=wb,p;
 51     int k=0; 
 52     for(int i=0;i;
 53     for(int i=1;i1];
 54     for(int i=n-1;i>=0;i--) sa[--wc[x[i]]]=i;
 55     for(int j=1,p=1;p2,m=p)
 56     {
 57         p=0;
 58         /*for(i=n-j;i 59         for(i=0;i 60          if(sa[i]>=j) y[p++]=sa[i]-j;
 61         */ //默认后继为i+1应该是这个写法 
 62     
 63         for(int i=0;i) q[f[i][k]].push(i);
 64         for(int i=0;i)
 65          while(!q[sa[i]].empty())
 66          {
 67              y[p++]=q[sa[i]].front();
 68              q[sa[i]].pop();
 69          }
 70         for(int i=0;ix[y[i]];
 71         for(int i=0;i0;
 72         for(int i=0;i; 
 73         for(int i=1;i1];
 74         for(int i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i];
 75         swap(x,y);
 76         p=1; x[sa[0]]=0;
 77         for(int i=1;i) 
 78          x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++;
 79         //printf("%d %d %d\n",k,j,p);
 80         k++;
 81         if(j>n) break; //加上这句就A了，应该都是N很大，D[i]相同的数据吧，名次的并列很多 
 82     }
 83 }    
 84     
 85 
 86 
 87 int main()
 88 {
 89     freopen("hdoj6223.in","r",stdin);
 90     freopen("hdoj6223.out","w",stdout);
 91     int cas;
 92     scanf("%d",&cas);
 93     for(int v=1;v)
 94     {
 95         printf("Case #%d: ",v);
 96         scanf("%d",&n);
 97          scanf("%s",ch);
 98          for(int i=0;i‘0‘+1;
 99          for(int i=0;i0]=(1LL*i*i+1)%n;
100      
101         for(int j=1;j18;j++)
102          for(int i=0;i1]][j-1]; 
103     
104          
105          
106          s[n]=0;
107          getsa(s,sa,n+1,20);
108         int k=sa[n];
109         for(int i=1;i)
110         {
111             printf("%c",ch[k]);
112             k=f[k][0];
113         }
114         printf("\n");
115         for(int i=0;i20,n);i++)
116         {
117                s[i]=sa[i]=wa[i]=wb[i]=wc[i]=wd[i]=
118               Rank[i]=0; 
119         } 
120     }
121     return 0;
122 }
123

【HDOJ6223】Infinite Fraction Path（后缀数组）

标签：应该 signed set bre 字典序位置 long swap int

原文地址：https://www.cnblogs.com/myx12345/p/9735730.html

上一篇：Python3 tkinter基础 Scale orient 横竖 resolution单步步长 length 长度 tickinterval 指示刻度

下一篇：spring学习五依赖注入的方式

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【HDOJ6223】Infinite Fraction Path（后缀数组）
文章链接：http://soscw.com/index.php/essay/88191.html

亲，登录后才可以留言！

【HDOJ6223】Infinite Fraction Path（后缀数组）

评论

热门文章

推荐文章

最新文章

置顶文章