程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [POJ1743]Musical Themes 樂曲主題 後綴數組、 (也可以用hash+二分做的~)

[POJ1743]Musical Themes 樂曲主題 後綴數組、 (也可以用hash+二分做的~)

編輯:關於C++

題意:

 

1829: Musical Themes 樂曲主題

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 42 Solved: 15
[Submit][Status][Web Board]

Description

我們用N(1 <= N <=5000)個音符的序列來表示一首樂曲,每個音符都是1..88范圍內的整數,每個數表示鋼琴上的一個鍵。很不幸這種表示旋律的方法忽略了音符的時值,但這項編程任務是關於音高的,與時值無關。

許多作曲家圍繞一個重復出現的“主題”來構建樂曲。在我們的樂曲表示法中,“主題”是整個音符序列的一個子序列,它需要滿足如下條件:

  • 長度至少為5個音符
  • 在樂曲中重復出現(可能經過轉調,見下)
  • 重復出現的同一主題不能重疊

    “轉調”的意思是主題序列中每個音符都被加上或減去了同一個整數值。

    給定一段樂曲,計算其中最長主題的長度(即音符數)。

    Input

    輸出文件的第一行包含整數N。下面的每一行(最後一行可能除外)包含20個整數,表示音符序列。最後一行可能少於20個音符。

    Output

    輸出文件應只含一個整數,即最長主題的長度。如果樂曲中沒有主題,那麼輸出0。

    Sample Input

    3025 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 1882 78 74 70 66 67 64 60 65 80

    Sample Output

    5

    HINT

     

    樣例中這個長度為5的主題是輸入文件中第一行的最後5個音符和第二行開頭5個音符

     

    Source

    USACO

    Best Solution

    C C++ Pascal NULL 80643.wyfcyx
    (0ms,1100KB,2168B) 21804.Ares
    (72ms,292KB,561B)
    [Submit][Status][Web Board]
    

    Powered by LLQ. ?2012-2014 長春吉大附中實驗學校.

     

    題解:

    啊,寫個後綴數組,然後二分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;imid)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;
    }
    


     

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved