問題名稱文件名輸入輸出時限分數
序列sequence.exe sequence . in sequence . out2s 100
連分式faction.exe事實。事實上。out1s100
word chain link.exe link . inlink . out 1s 100
大地測量裝置geo.exe geo . ingeo . out 1s 100
序列(sequence.exe)
問題描述
有壹個非減整數序列S1，S2，S3，...，sn+1 (si
比如S=(1，3，3，5)，那麽m=(2，3，4)。
現在我給妳序列M，我要妳找出S序列有多少個“M序列”是序列M。
輸入(順序輸入)
第壹行是整數n，
後面跟著n行，每壹行都有壹個整數mi。
輸出(序列輸出)
壹個整數，表示S序列中有多少個“M序列”是序列M。
樣品
順序。按順序。出來
三
2
五
九
四
示例說明:有以下四個系列可滿足要求:
2,2,8,10;
1,3,7,11;
0,4,6,12;
-1,5,5,13。
數據範圍
50%的數據n
100%數據2
連分數(faction.exe)
問題描述
辛迪新學了無理數，老師教了她壹個用有理數推無理數的方法:求這個無理數對應的無限循環連分式。
舉個例子，
我們可以取出壹層，兩層，三層，得到壹個有理數序列，...而忽略了連分式的其他部分，所以我們可以稱之為連分式的漸近分式序列。黃金分割數的漸近分數為1/1，1/2，2/3，3/5，5/8，8/13。
辛迪對連分數的形式特別感興趣。為了簡化，她要研究的連分數都是以下幾種形式:
她用壹個簡單的符號來表示這個連分數:。例如，黃金分割數的連分數縮寫為
對於每壹個這樣的連分數，都有壹個對應的漸近分數序列:a1/b？1，a2/b2，…現在辛迪的研究中有壹個連分式，她希望妳能幫她找到它的漸近分式序列的第m項。請以二進制群(am，bm)的形式給出答案，對於答案中的兩個數，只需輸出它們的模9973即可。
輸入(派系)
第壹行是整數n和m，分別代表連分式的循環段長度和所需漸近分式的項數。後面是n行，每壹行都有壹個整數pi，描述的是連分式。
輸出(派系.輸出)
由空格分隔的兩個整數am和bm。
樣品
派系。進派系。出派系
1 6
1 8 13
數據範圍
60%的數據，m
100%數據，n
單詞鏈(link.exe)
問題描述
給定壹個只包含小寫字母的英語單詞列表，每個單詞最多包含50個字母。
如果壹個表由壹個詞或多個詞組成，每個詞(除了最後壹個)都是它後面的詞的前綴，那麽這個表就叫做詞鏈。例如，以下單詞構成壹個單詞鏈:
我
（同Internationalorganizations）國際組織
整數
並且以下單詞不構成單詞鏈:
整數
拘留
請從給定的列表中選擇壹些單詞組成最長的單詞鏈。最長的單詞鏈是單詞數最多的單詞鏈。
數據確保給定單詞列表中的單詞互不相同，並且單詞按照字典順序排列。
輸入(鏈接輸入)
第壹行是整數n，表示單詞列表中的單詞數。
後面是n行，每行壹個字。
輸出(link.out)
表示最長單詞鏈長度的整數。
樣品
link.in link.out
五
我
（同Internationalorganizations）國際組織
整數
拘留
互聯網4
數據範圍
50%的數據，n
100%數據，n
大地測量裝置(geo.exe)
問題描述
圖G是沒有自環的無向連通圖，兩點之間至多有壹條邊。我們將頂點v和u的最短路徑定義為從v到u的邊數最少的路徑。v-u最短路徑包含的所有頂點稱為v-u的大地頂點，這些頂點的集合記為I(v，u)。
我們稱集合I(v，u)為測地集合。
比如下圖中，I(2，5)={2，3，4，5}，I(1，5)={1，3，5}，I(2，4)={2，4}。
給定壹個圖G和幾對點V，U，請分別求出I (v，U)。
輸入(地理位置)
在第壹行中，兩個整數n和m分別代表圖G(頂點數1-n)的頂點數和邊數。
後面是m條線，每條線有兩個整數A和B，表示頂點A和B之間有壹條無向邊..
線m+2有壹個整數k，代表給定點對數。
後面是k線，每壹行都有兩個整數v和u。
輸出(地理輸出)
***k行，每行對應輸入文件中的每個點對v，u，按照頂點數升序輸出I(v，u)。同壹行中的每個數字用空格隔開。
樣品
地理輸入地理輸出
5 6
1 2
1 3
2 3
2 4
3 5
4 5
三
2 5
5 1
2 4 2 3 4 5
1 3 5
2 4
數據範圍
100%數據，n
每個問題的簡要分析:
序列序列:
設S序列的第壹項為k，則下列各項可寫成關於k的多項式:
S1=k
S2=2*m1-k
S3=2*m2-2*m1+k
……
然後根據S序列的非減性質，有S1
所以有
k & lt=2*m1-k
2 * m 1-k & lt；=2*m2-2*m1+k
……
可以得到n個關於k的不等式，而且都是正則的，形式可以在O(n)時間內求解。
a & lt= k & lt=b
結果。
由於k的值與S序列壹壹對應，所以k (b-a)的值的個數就是滿足要求的S序列的個數。
事實繼續派:
本題目原創，重點講解遞歸，用矩陣乘法優化遞歸。
通過遞歸公式:
k = (m-1) mod n + 1
有空的
；
直接按照這個遞歸公式計算，復雜度O(m)預計得分60%。
上述遞歸公式對應的矩陣運算為:
所以有
其中c是(m mod n)部分的剩余矩陣的乘積。
由於計算矩陣冪的時間復雜度為O(logm)，所以算法總復雜度為O(n+logm)，估計得分為100%。
鏈接單詞鏈:
在本主題中，很容易使用動態編程。設f(i)表示前I個單詞可以構成包含I個單詞的最長單詞鏈。
F(i)=max{1，F(j)+1，當word[j]是word[i]的前綴時}
Ans=max{F(i)}
該算法復雜度為O(n2)，估計得分為50%。
其實這個問題有壹個很簡單的貪心算法。
用壹個棧來存儲以第I個字結尾的最長的字鏈，i+1字加在棧尾(通過彈出棧來存儲壹個字鏈)。
例如:
I堆棧:I
Int堆棧:ii int
整數堆棧:I int整數
Intern stack: i int intern(棧外整數)
互聯網堆棧:互聯網
可以證明，在插入第I個單詞後，當前在棧中的單詞鏈是包含第I個單詞的最長的單詞鏈。
這樣算法的復雜度是O(n)因為每個字進出棧壹次。
貪心算法的估計得分是100%。
大地測量裝置:
此題改編自北大上的壹道測試題，考查地圖的相關知識。該算法是從每個點開始，根據得到的BFS序列遞歸地展開BFS。
設min[i，j]是從I到j的最短路徑長度。
設f[i，j]表示從I到J的最短路徑所覆蓋的節點集，
F [i，j] = f [i，k] u {j} k = {1...n}和(min [i，k]+1 = min [i，j])和(k，j)存在。
對於每個輸入v，u對，只需輸出f[v，u]中的所有點。