#49: 解題報告:歌詞搜尋


810848 (路過)

School : 一中
ID : 96
IP address : [162.158.119.113]
Last Login :
2021-04-17 17:30:36
c035. ii.歌詞搜尋$(Chorus)$ -- 臺中一中電腦資訊研習社 | From: [162.158.119.123] | Post Date : 2021-01-08 18:00

這一題有一點複雜,不過已經有提醒過題目不是照難度排的拉~

 

首先:是基礎的輸入,getline,還有EOF不要忘了,很重要~

我們可以用列舉法解決這個問題,我們假設第i~j行歌詞是副歌,那我們先把i~j行的歌詞全部加起來變成一個大字串S,之後我們列舉大小是j-i+1的所有連續句子(除了i~j以外),然後加起來變成另一個字串T,如果S = T,我們就確定S是個有重複過的字串了,最後只要從中挑出j-i+1(句數)最大的就是副歌了~

 

為了降低程式的複雜性可以用一個技巧:我們由大~小列舉句數C,然後列舉i,此時j = i+C-1,這樣有甚麼好處呢?因為當我們找到低一個有重複的S時,他的句數一定最大(不然更大的一定先被找到),所以直接輸出S然後直接結束程式即可(return 0),然後由於要直接輸出S,所以句跟句之間記得加上換行符號比較方便,當然從i跑到j輸出也是可以。還有在各種比賽中:最後一句的換行通常放了也不會怎樣,所以不需擔心多一個換行(某NXXC還硬是要我們換行)。

 

還有一件小趣事:本題的測試資料都是真的歌曲喔~

收錄曲(節錄):

青花瓷

Take on Me

Something Just Like This

Never Gonna Give You Up

Maps

......

 

 
ZeroJudge Forum