题目传送门:http://pan.baidu.com/s/1pLvQmx1
离线版题目:http://paste.ubuntu.com/18302981/
数据传送门:http://pan.baidu.com/s/1dF0ovZj
这一道题,std是后缀树,然而被YYY踩了,居然一个Hash / SA就可捉QAQ
还是说正事吧。
对于每一次++,分两种情况讨论:
1)有至少一个数变成0:
对于这一种情况呢,明显,字典序最小的循环串的开头,只会在这些变成0的位置中产生
所以问题就变为:比较一些给定的字符串的大小。这个看起来也不是很能做的样子。
但如果我们只考虑两两比较,那么去掉这两个串的公共前缀,我们只需要比较一个字符就可以确定大小
所以拿SA / Hash处理出公共前缀后,比较单个字符的大小即可
2)没有数变成零:
对于这一种情况,答案不会变。水涨船高嘛!
于是这个题目就搞定啦!哎,这么简单!我这个纸张考试的时候怎么没有想到呢?QAQ
%%%YYY, Hash踩标程
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int MAXN = 200000+9; const int SGZ = 51000; int n,m,k,N,M,arr[MAXN],ord[MAXN],now,tot,ans; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline bool cmp_sort(const int a, const int b){ return arr[a] > arr[b]; } namespace Suffix_Array{ #define SA Suffix_Array int sa[MAXN],height[MAXN],t1[MAXN],t2[MAXN],bot[MAXN]; int *tmp,*rank,m; namespace Sparse_Table{ #define ST Sparse_Table int MN[MAXN][20]; inline void init(){ for (int i=1;i<=n;i++) MN[i][0]=height[i]; for (int k=1;k<=16;k++) for (int i=1;i<=n;i++) MN[i][k] = min(MN[i][k-1],MN[i+(1<<k-1)][k-1]); } inline int query(int l, int r){ if (l > r) swap(l,r); l++; int k=0,len=1,L=(r-l+1); while (len <= L/2) len*=2,k++; return min(MN[l][k],MN[r-len+1][k]); } }; inline void GetHeight(){ for (int i=1;i<=n;i++) if (rank[i]>1){ int sta = max(0,height[rank[i-1]]-1); int p1=i+sta, p2=sa[rank[i]-1]+sta; while (arr[p1++]==arr[p2++]) sta++; height[rank[i]] = sta; } } inline void build(){ tmp=t1; rank=t2; m=SGZ; for (int i=1;i<=m;i++) bot[i] = 0; for (int i=1;i<=n;i++) bot[tmp[i]=arr[i]+1]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=n;i;i--) sa[bot[tmp[i]]--] = i; rank[sa[1]] = m = 1; for (int i=2;i<=n;i++) rank[sa[i]] = (tmp[sa[i]]==tmp[sa[i-1]])?m:++m; for (int k=1;k<=n;k*=2){ int T=0; for (int i=n-k+1;i<=n;i++) tmp[++T] = i; for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k; for (int i=1;i<=m;i++) bot[i] = 0; for (int i=1;i<=n;i++) bot[rank[i]]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i]; swap(tmp,rank); rank[sa[1]] = m = 1; for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]]=m; else rank[sa[i]] = ++m; if (m >= n) break; } GetHeight(); ST::init(); } inline int query(int a, int b){ return ST::query(rank[a],rank[b]); } }; int main(){ freopen("cyclic.in","r",stdin); freopen("cyclic.out","w",stdout); scanf("%d%d%d",&N,&M,&k); for (int i=1;i<=N;i++) ord[i]=i, arr[i]=arr[i+N]=read(); n = N*2; now = M-1; tot=1; SA::build(); sort(ord+1,ord+1+N,cmp_sort); for (int i=1;i<=n;i++) if (SA::sa[i]<=N) {ans=SA::sa[i];break;} printf("%d\n",arr[ans+k-1]); for (int i=1;i<M;i++,now--){ if (tot <= N && arr[ord[tot]]==now){ ans = ord[tot++]; while (tot <= N && arr[ord[tot]]==now){ int same = SA::query(ans, ord[tot]); int t = (arr[ans+same]+i)%M-(arr[ord[tot]+same]+i)%M; if (t >= 0) ans = ord[tot]; tot++; } printf("%d\n",(arr[ans+k-1]+i)%M); } else printf("%d\n",(arr[ans+k-1]+i)%M); } return 0; }
好文章!666,学习了
Great awesome things here. I am very glad to peer your post. Thank you so much and i’m looking forward to contact you. Will you please drop me a mail?
I treasure the knowledge on your website. Many thanks!|
Appreciating the time and effort you put into your blog and detailed information you present. It’s good to come across a blog every once in a while that isn’t the same outdated rehashed material. Great read! I’ve saved your site and I’m including your RSS feeds to my Google account.