[破碎的状态] [1] Hdu 4691(Failed)
其实我觉得代码是对的..
反正..
后缀数组写对了..
后面st表..
不管了..
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<time.h> #include<math.h> #include<memory> #include<vector> #include<bitset> #include<fstream> #include<stdio.h> #include<utility> #include<sstream> #include<string.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; char a[100005]; struct node { int x; int y; int id; friend bool operator < (const node &a,const node &b) { return a.y<b.y; } }; node b[100005]; int c[100005]; int m; void suffix_sort(int x) { if (x>m) return; int i; c[b[0].id]=0; for (i=1;i<m;i++) { if ((b[i].x!=b[i-1].x)||(b[i].y!=b[i-1].y)) { c[b[i].id]=c[b[i-1].id]+1; } else { c[b[i].id]=c[b[i-1].id]; } } for (i=0;i<m;i++) { b[i].x=c[b[i].id]; if (b[i].id+x<m) { b[i].y=c[b[i].id+x]; } else { b[i].y=-1; } } int last=0; for (i=1;i<m;i++) { if (b[i-1].x!=b[i].x) { sort(b+last,b+i); last=i; } } sort(b+last,b+m); suffix_sort(x*2); } int lcp[100005]; int st[100005][20]; int d[1<<20]; int get_lcp(int x,int y) { if (x>y) swap(x,y); if (x==y) return 1000000; int k=d[y-x]; return min(st[x][k],st[y-(1<<k)][k]); } int main() { #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif ios::sync_with_stdio(false); int i; for (i=0;i<19;i++) { int j; for (j=(1<<i);j<(1<<(i+1));j++) { d[j]=i; } } for (;;) { if (scanf("%s",a)==-1) break; int n; scanf("%d",&n); m=strlen(a); int i; for (i=0;i<m;i++) { b[i].id=i; b[i].x=0; b[i].y=a[i]; } sort(b,b+m); suffix_sort(1); int last=-1; for (i=0;i<m;i++) { if (b[i].x==m-1) continue; if ((i==0)||(lcp[i-1]==0)) { last=0; } else { last=lcp[i-1]-1; } lcp[i]=0; if (c[i]==0) continue; for (;;) { if (a[i+last]==a[last+b[c[i]-1].id]) { last++; } else { break; } } lcp[i]=last; } for (i=m-1;i>=0;i--) { int j; if (i==m-1) { st[i][0]=0; } else { st[i][0]=lcp[b[i+1].id]; } for (j=1;j<20;j++) { if (((1<<j)+i)>m) continue; st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } if (n==0) { cout<<"0 0\n"; continue; } int lastx,lasty; scanf("%d%d",&lastx,&lasty); long long sum1=n,sum2=n; sum1+=lasty-lastx; sum2+=lasty-lastx+2; for (i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); sum1+=y-x; int k=get_lcp(c[x],c[lastx]); k=min(k,lasty-lastx); k=min(k,y-x); lastx=x; lasty=y; sum2+=(y-x-k); sum2++; sum2++; if (k>=10) sum2++; if (k>=100) sum2++; if (k>=1000) sum2++; if (k>=10000) sum2++; if (k>=100000) sum2++; } cout<<sum1<<" "<<sum2<<'\n'; } return 0; }
Sep 26, 2022 01:33:12 AM
Hindi is a very important language subject to know in India and we are here to tell you why. In this article, NCERT Hindi Sample Paper Class 10 we will be discussing the importance of learning Hindi. From children to adults, everyone takes up a second language at some point in their life. With the ongoing situation, you could have not found a better time to learn a new language.Hindi is a very important language subject to know in India and we are here to tell you why. In this article