題意:
我們用N(1 <= N <=5000)個音符的序列來表示一首樂曲,每個音符都是1..88范圍內的整數,每個數表示鋼琴上的一個鍵。很不幸這種表示旋律的方法忽略了音符的時值,但這項編程任務是關於音高的,與時值無關。
許多作曲家圍繞一個重復出現的“主題”來構建樂曲。在我們的樂曲表示法中,“主題”是整個音符序列的一個子序列,它需要滿足如下條件:
“轉調”的意思是主題序列中每個音符都被加上或減去了同一個整數值。
給定一段樂曲,計算其中最長主題的長度(即音符數)。
輸出文件的第一行包含整數N。下面的每一行(最後一行可能除外)包含20個整數,表示音符序列。最後一行可能少於20個音符。
輸出文件應只含一個整數,即最長主題的長度。如果樂曲中沒有主題,那麼輸出0。
樣例中這個長度為5的主題是輸入文件中第一行的最後5個音符和第二行開頭5個音符
USACO
題解:
啊,寫個後綴數組,然後二分check時根據height分組,使每一段都滿足height足夠長,掃一遍,如果裡面離的最遠兩個沒重合(sa的差足夠大),就return 1。。。
代碼:
#include#include #include #include #define N 21000 using namespace std; int s[N]; int sa[N],rank[N],h[N],n,m,len; int cnt[N],val[N],stk[N],_val[N],top; bool issame(int a,int b,int hl) { return val[a]==val[b]&& ((a+hl>=len&&b+hl>=len)||(a+hl =0;i--)sa[--cnt[val[i]]]=i; for(k=1;;k++) { top=0,hl=1<<(k-1); for(i=0;i =len)stk[top++]=sa[i]; for(i=0;i =hl)stk[top++]=sa[i]-hl; for(i=0;i =0;i--)sa[--cnt[val[stk[i]]]]=stk[i]; for(lim=i=0;i mid)return 1; } return 0; } int main() { // freopen("test.in","r",stdin); int i,j,k; scanf("%d",&len); scanf("%d",&s[0]); for(i=1;i >1; if(check(mid))l=mid; else r=mid-1; } if(ans>=4)printf("%d\n",ans+1);else puts("0"); return 0; }