1、數列排序（數組 排序）
問題描述
給定一個長度為n的數列，將這個數列按從小到大的順序排列。1<=n<=200
輸入格式
第一行為一個整數n。
第二行包含n個整數，為待排序的數，每個整數的絕對值小于10000。
輸出格式
輸出一行，按從小到大的順序輸出排序后的數列。
樣例輸入
5
8 3 6 4 9
樣例輸出
3 4 6 8 9
#include<iostream.h>
{
int n,a;
cout<<”請輸入n，n是（1~200）之間的整數”;
cin>>n;
for(int i=0;i<n;i++)
{
}
}
2、十六進制轉八進制（進制轉換 字符 循環）
問題描述
給定n個十六進制正整數，輸出它們對應的八進制數。
輸入格式
輸入的第一行為一個正整數n （1<=n<=10）。
接下來n行，每行一個由09、大寫字母AF組成的字符串，表示要轉換的十六進制正整數，每個十六進制數長度不超過100000。
輸出格式
輸出n行，每行為輸入對應的八進制正整數。
注意
輸入的十六進制數不會有前導0，比如012A。
輸出的八進制數也不能有前導0。
樣例輸入
2
39
123ABC
樣例輸出
71
4435274
提示
先將十六進制數轉換成某進制數，再由某進制數轉換成八進制。
3、十六進制轉十進制（進制轉換 字符處理 判斷）
問題描述
從鍵盤輸入一個不超過8位的正的十六進制數字符串，將它轉換為正的十進制數后輸出。
注：十六進制數中的10~15分別用大寫的英文字母A、B、C、D、E、F表示。
樣例輸入
FFFF
樣例輸出
65535
4、十進制轉十六進制（循環 整除 求余 判斷）
問題描述
十六進制數是在程序設計時經常要使用到的一種整數的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16個符號，分別表示十進制數的0至15。十六進制的計數方法是滿16進1，所以十進制數16在十六進制中是10，而十進制的17在十六進制中是11，以此類推，十進制的30在十六進制中是1E。
給出一個非負整數，將它表示成十六進制的形式。
輸入格式
輸入包含一個非負整數a，表示要轉換的數。0<=a<=2147483647
輸出格式
輸出這個整數的16進制表示
樣例輸入
30
樣例輸出
1E
5、特殊回文數（回文數 循環 條件語句）
問題描述
123321是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的。
輸入一個正整數n， 編程求所有這樣的五位和六位十進制數，滿足各位數字之和等于n 。
輸入格式
輸入一行，包含一個正整數n。
輸出格式
按從小到大的順序輸出滿足條件的整數，每個整數占一行。
樣例輸入
52
樣例輸出
899998
989989
998899
6、回文數（循環 判斷 回文數）
問題描述
1221是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的，編程求所有這樣的四位十進制數。
輸出格式
按從小到大的順序輸出滿足條件的四位十進制數。
7、特殊的數字（循環 判斷 數位）
問題描述
153是一個非常特殊的數，它等于它的每位數字的立方和，即153=111+555+333。編程求所有滿足這種條件的三位十進制數。
輸出格式
按從小到大的順序輸出滿足條件的三位十進制數，每個數占一行。
8、楊輝三角形（基礎練習 二維數組）
問題描述
楊輝三角形又稱Pascal三角形，它的第i+1行是(a+b)i的展開式的系數。
它的一個重要性質是：三角形中的每個數字等于它兩肩上的數字相加。
下面給出了楊輝三角形的前4行：
1
1 1
1 2 1
1 3 3 1
給出n，輸出它的前n行。
輸入格式
輸入包含一個數n。
輸出格式
輸出楊輝三角形的前n行。每一行從這一行的第一個數開始依次輸出，中間使用一個空格分隔。請不要在前面輸出多余的空格。
樣例輸入
4
樣例輸出
1
1 1
1 2 1
1 3 3 1
數據規模與約定
1 <= n <= 34。
9、查找整數（循環 判斷）
問題描述
給出一個包含n個整數的數列，問整數a在數列中的第一次出現是第幾個。
輸入格式
第一行包含一個整數n。
第二行包含n個非負整數，為給定的數列，數列中的每個數都不大于10000。
第三行包含一個整數a，為待查找的數。
輸出格式
如果a在數列中出現了，輸出它第一次出現的位置(位置從1開始編號)，否則輸出-1。
樣例輸入
6
1 9 4 8 3 9
9
樣例輸出
2
數據規模與約定
1 <= n <= 1000。
10、數列特征（循環 最大值 最小值 累加）
問題描述
給出n個數，找出這n個數的最大值，最小值，和。
輸入格式
第一行為整數n，表示數的個數。
第二行有n個數，為給定的n個數，每個數的絕對值都小于10000。
輸出格式
輸出三行，每行一個整數。第一行表示這些數中的最大值，第二行表示這些數中的最小值，第三行表示這些數的和。
樣例輸入
5
1 3 -2 4 5
樣例輸出
5
-2
3
數據規模與約定
1 <= n <= 10000。
11、字母圖形（循環 字符串）
問題描述
利用字母可以組成一些美麗的圖形，下面給出了一個例子：
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
這是一個5行7列的圖形，請找出這個圖形的規律，并輸出一個n行m列的圖形。
輸入格式
輸入一行，包含兩個整數n和m，分別表示你要輸出的圖形的行數的列數。
輸出格式
輸出n行，每個m個字符，為你的圖形。
樣例輸入
5 7
樣例輸出
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
數據規模與約定
1 <= n, m <= 26。
12、01字串（循環）
問題描述
對于長度為5位的一個01串，每一位都可能是0或1，一共有32種可能。它們的前幾個是：
00000
00001
00010
00011
00100
請按從小到大的順序輸出這32種01串。
輸入格式
本試題沒有輸入。
輸出格式
輸出32行，按從小到大的順序每行一個長度為5的01串。
樣例輸出
00000
00001
00010
00011
<以下部分省略>
13、閏年判斷（條件判斷）
問題描述
給定一個年份，判斷這一年是不是閏年。
當以下情況之一滿足時，這一年是閏年：
- 年份是4的倍數而不是100的倍數；
- 年份是400的倍數。
其他的年份都不是閏年。
輸入格式
輸入包含一個整數y，表示當前的年份。
輸出格式
輸出一行，如果給定的年份是閏年，則輸出yes，否則輸出no。
說明：當試題指定你輸出一個字符串作為結果（比如本題的yes或者no，你需要嚴格按照試題中給定的大小寫，寫錯大小寫將不得分。
樣例輸入
2013
樣例輸出
no
樣例輸入
2016
樣例輸出
yes
數據規模與約定
1990 <= y <= 2050。
14、階乘計算（高精度）
問題描述
輸入一個正整數n，輸出n!的值。
其中n!=123*…*n。
算法描述
n!可能很大，而計算機能表示的整數范圍有限，需要使用高精度計算的方法。使用一個數組A來表示一個大整數a，A[0]表示a的個位，A[1]表示a的十位，依次類推。
將a乘以一個整數k變為將數組A的每一個元素都乘以k，請注意處理相應的進位。
首先將a設為1，然后乘2，乘3，當乘到n時，即得到了n!的值。
輸入格式
輸入包含一個正整數n，n<=1000。
輸出格式
輸出n!的準確值。
樣例輸入
10
樣例輸出
3628800
15、高精度加法（數組 高精度）
問題描述
輸入兩個整數a和b，輸出這兩個整數的和。a和b都不超過100位。
算法描述
由于a和b都比較大，所以不能直接使用語言中的標準數據類型來存儲。對于這種問題，一般使用數組來處理。
定義一個數組A，A[0]用于存儲a的個位，A[1]用于存儲a的十位，依此類推。同樣可以用一個數組B來存儲b。
計算c = a + b的時候，首先將A[0]與B[0]相加，如果有進位產生，則把進位（即和的十位數）存入r，把和的個位數存入C[0]，即C[0]等于(A[0]+B[0])%10。然后計算A[1]與B[1]相加，這時還應將低位進上來的值r也加起來，即C[1]應該是A[1]、B[1]和r三個數的和．如果又有進位產生，則仍可將新的進位存入到r中，和的個位存到C[1]中。依此類推，即可求出C的所有位。
最后將C輸出即可。
輸入格式
輸入包括兩行，第一行為一個非負整數a，第二行為一個非負整數b。兩個整數都不超過100位，兩數的最高位都不是0。
輸出格式
輸出一行，表示a + b的值。
樣例輸入
20100122201001221234567890
2010012220100122
樣例輸出
20100122203011233454668012
16、Huffuman樹（貪心 Huffuman）
問題描述
Huffman樹在編碼中有著廣泛的應用。在這里，我們只關心Huffman樹的構造過程。
給出一列數{pi}={p0, p1, …, pn-1}，用這列數構造Huffman樹的過程如下： - 找到{pi}中最小的兩個數，設為pa和pb，將pa和pb從{pi}中刪除掉，然后將它們的和加入到{pi}中。這個過程的費用記為pa + pb。
- 重復步驟1，直到{pi}中只剩下一個數。
在上面的操作過程中，把所有的費用相加，就得到了構造Huffman樹的總費用。
本題任務：對于給定的一個數列，現在請你求出用該數列構造Huffman樹的總費用。
例如，對于數列{pi}={5, 3, 8, 2, 9}，Huffman樹的構造過程如下： - 找到{5, 3, 8, 2, 9}中最小的兩個數，分別是2和3，從{pi}中刪除它們并將和5加入，得到{5, 8, 9, 5}，費用為5。
- 找到{5, 8, 9, 5}中最小的兩個數，分別是5和5，從{pi}中刪除它們并將和10加入，得到{8, 9, 10}，費用為10。
- 找到{8, 9, 10}中最小的兩個數，分別是8和9，從{pi}中刪除它們并將和17加入，得到{10, 17}，費用為17。
- 找到{10, 17}中最小的兩個數，分別是10和17，從{pi}中刪除它們并將和27加入，得到{27}，費用為27。
- 現在，數列中只剩下一個數27，構造過程結束，總費用為5+10+17+27=59。
輸入格式
輸入的第一行包含一個正整數n（n<=100）。
接下來是n個正整數，表示p0, p1, …, pn-1，每個數不超過1000。
輸出格式
輸出用這些數構造Huffman樹的總費用。
樣例輸入
5
5 3 8 2 9
樣例輸出
59
17、2n皇后問題（八皇后問題 搜索）
問題描述
給定一個nn的棋盤，棋盤中有一些位置不能放皇后。現在要向棋盤中放入n個黑皇后和n個白皇后，使任意的兩個黑皇后都不在同一行、同一列或同一條對角線上，任意的兩個白皇后都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小于等于8。
輸入格式
輸入的第一行為一個整數n，表示棋盤的大小。
接下來n行，每行n個0或1的整數，如果一個整數為1，表示對應的位置可以放皇后，如果一個整數為0，表示對應的位置不可以放皇后。
輸出格式
輸出一個整數，表示總共有多少種放法。
樣例輸入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
2
樣例輸入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
樣例輸出
0
18、報時助手（字符串 條件判斷）
問題描述
給定當前的時間，請用英文的讀法將它讀出來。
時間用時h和分m表示，在英文的讀法中，讀一個時間的方法是：
如果m為0，則將時讀出來，然后加上“o’clock”，如3:00讀作“three o’clock”。
如果m不為0，則將時讀出來，然后將分讀出來，如5:30讀作“five thirty”。
時和分的讀法使用的是英文數字的讀法，其中0~20讀作：
0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
30讀作thirty，40讀作forty，50讀作fifty。
對于大于20小于60的數字，首先讀整十的數，然后再加上個位數。如31首先讀30再加1的讀法，讀作“thirty one”。
按上面的規則21:54讀作“twenty one fifty four”，9:07讀作“nine seven”，0:15讀作“zero fifteen”。
輸入格式
輸入包含兩個非負整數h和m，表示時間的時和分。非零的數字前沒有前導0。h小于24，m小于60。
輸出格式
輸出時間時刻的英文。
樣例輸入
0 15
樣例輸出
zero fifteen
19、回形取數（二維數組 循環）
問題描述
回形取數就是沿矩陣的邊取數，若當前方向上無數可取或已經取過，則左轉90度。一開始位于矩陣左上角，方向向下。
輸入格式
輸入第一行是兩個不超過200的正整數m, n，表示矩陣的行和列。接下來m行每行n個整數，表示這個矩陣。
輸出格式
輸出只有一行，共mn個數，為輸入矩陣回形取數得到的結果。數之間用一個空格分隔，行末不要有多余的空格。
樣例輸入
3 3
1 2 3
4 5 6
7 8 9
樣例輸出
1 4 7 8 9 6 3 2 5
樣例輸入
3 2
1 2
3 4
5 6
樣例輸出
1 3 5 6 4 2
20、龜兔賽跑預測（數組 模擬）
問題描述
話說這個世界上有各種各樣的兔子和烏龜，但是研究發現，所有的兔子和烏龜都有一個共同的特點——喜歡賽跑。于是世界上各個角落都不斷在發生著烏龜和兔子的比賽，小華對此很感興趣，于是決定研究不同兔子和烏龜的賽跑。他發現，兔子雖然跑比烏龜快，但它們有眾所周知的毛病——驕傲且懶惰，于是在與烏龜的比賽中，一旦任一秒結束后兔子發現自己領先t米或以上，它們就會停下來休息s秒。對于不同的兔子，t，s的數值是不同的，但是所有的烏龜卻是一致——它們不到終點決不停止。
然而有些比賽相當漫長，全程觀看會耗費大量時間，而小華發現只要在每場比賽開始后記錄下兔子和烏龜的數據——兔子的速度v1（表示每秒兔子能跑v1米），烏龜的速度v2，以及兔子對應的t，s值，以及賽道的長度l——就能預測出比賽的結果。但是小華很懶，不想通過手工計算推測出比賽的結果，于是他找到了你——清華大學計算機系的高才生——請求幫助，請你寫一個程序，對于輸入的一場比賽的數據v1，v2，t，s，l，預測該場比賽的結果。
輸入格式
輸入只有一行，包含用空格隔開的五個正整數v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且為v1,v2的公倍數)
輸出格式
輸出包含兩行，第一行輸出比賽結果——一個大寫字母“T”或“R”或“D”，分別表示烏龜獲勝，兔子獲勝，或者兩者同時到達終點。
第二行輸出一個正整數，表示獲勝者（或者雙方同時）到達終點所耗費的時間（秒數）。
樣例輸入
10 5 5 2 20
樣例輸出
D
4
樣例輸入
10 5 5 1 20
樣例輸出
R
3
樣例輸入
10 5 5 3 20
樣例輸出
T
4
21、芯片測試（算法基礎 統計 二維數組）
問題描述
有n（2≤n≤20）塊芯片，有好有壞，已知好芯片比壞芯片多。
每個芯片都能用來測試其他芯片。用好芯片測試其他芯片時，能正確給出被測試芯片是好還是壞。而用壞芯片測試其他芯片時，會隨機給出好或是壞的測試結果（即此結果與被測試芯片實際的好壞無關）。
給出所有芯片的測試結果，問哪些芯片是好芯片。
輸入格式
輸入數據第一行為一個整數n，表示芯片個數。
第二行到第n+1行為nn的一張表，每行n個數據。表中的每個數據為0或1，在這n行中的第i行第j列（1≤i, j≤n）的數據表示用第i塊芯片測試第j塊芯片時得到的測試結果，1表示好，0表示壞，i=j時一律為1（并不表示該芯片對本身的測試結果。芯片不能對本身進行測試）。
輸出格式
按從小到大的順序輸出所有好芯片的編號
樣例輸入
3
1 0 1
0 1 0
1 0 1
樣例輸出
1 3
22、FJ的字符串（字符串 遞歸）
問題描述
FJ在沙盤上寫了這樣一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
… …
你能找出其中的規律并寫所有的數列AN嗎？
輸入格式
僅有一個數：N ≤ 26。
輸出格式
請輸出相應的字符串AN，以一個換行符結束。輸出中不得含有多余的空格或換行、回車符。
樣例輸入
3
樣例輸出
ABACABA
23、Sine之舞（字符串 遞歸 遞推）
問題描述
最近FJ為他的奶牛們開設了數學分析課，FJ知道若要學好這門課，必須有一個好的三角函數基本功。所以他準備和奶牛們做一個“Sine之舞”的游戲，寓教于樂，提高奶牛們的計算能力。
不妨設
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想讓奶牛們計算Sn的值，請你幫助FJ打印出Sn的完整表達式，以方便奶牛們做題。
輸入格式
僅有一個數：N<201。
輸出格式
請輸出相應的表達式Sn，以一個換行符結束。輸出中不得含有多余的空格或換行、回車符。
樣例輸入
3
樣例輸出
((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1
24、數的讀法（判斷 函數）
問題描述
Tom教授正在給研究生講授一門關于基因的課程，有一件事情讓他頗為頭疼：一條染色體上有成千上萬個堿基對，它們從0開始編號，到幾百萬，幾千萬，甚至上億。
比如說，在對學生講解第1234567009號位置上的堿基時，光看著數字是很難準確的念出來的。
所以，他迫切地需要一個系統，然后當他輸入12 3456 7009時，會給出相應的念法：
十二億三千四百五十六萬七千零九
用漢語拼音表示為
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
這樣他只需要照著念就可以了。
你的任務是幫他設計這樣一個系統：給定一個阿拉伯數字串，你幫他按照中文讀寫的規范轉為漢語拼音字串，相鄰的兩個音節用一個空格符格開。
注意必須嚴格按照規范，比如說“10010”讀作“yi wan ling yi shi”而不是“yi wan ling shi”，“100000”讀作“shi wan”而不是“yi shi wan”，“2000”讀作“er qian”而不是“liang qian”。
輸入格式
有一個數字串，數值大小不超過2,000,000,000。
輸出格式
是一個由小寫英文字母，逗號和空格組成的字符串，表示該數的英文讀法。
樣例輸入
1234567009
樣例輸出
shi er yi san qian si bai wu shi liu wan qi qian ling jiu
25、完美的代價（貪心算法）
問題描述
回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。小龍龍認為回文串才是完美的。現在給你一個串，它不一定是回文的，請你計算最少的交換次數使得該串變成一個完美的回文串。
交換的定義是：交換兩個相鄰的字符
例如mamad
第一次交換 ad : mamda
第二次交換 md : madma
第三次交換 ma : madam (回文！完美！)
輸入格式
第一行是一個整數N，表示接下來的字符串的長度(N <= 8000)
第二行是一個字符串，長度為N.只包含小寫字母
輸出格式
如果可能，輸出最少的交換次數。
否則輸出Impossible
樣例輸入
5
mamad
樣例輸出
3
26、矩形面積交（判斷 線段交）
問題描述
平面上有兩個矩形，它們的邊平行于直角坐標系的X軸或Y軸。對于每個矩形，我們給出它的一對相對頂點的坐標，請你編程算出兩個矩形的交的面積。
輸入格式
輸入僅包含兩行，每行描述一個矩形。
在每行中，給出矩形的一對相對頂點的坐標，每個點的坐標都用兩個絕對值不超過10^7的實數表示。
輸出格式
輸出僅包含一個實數，為交的面積，保留到小數后兩位。
樣例輸入
1 1 3 3
2 2 4 4
樣例輸出
1.00
27、矩陣乘法（二維數組 循環 矩陣）
問題描述
給定一個N階矩陣A，輸出A的M次冪（M是非負整數）
例如：
A =
1 2
3 4
A的2次冪
7 10
15 22
輸入格式
第一行是一個正整數N、M（1<=N<=30, 0<=M<=5），表示矩陣A的階數和要求的冪數
接下來N行，每行N個絕對值不超過10的非負整數，描述矩陣A的值
輸出格式
輸出共N行，每行N個整數，表示A的M次冪所對應的矩陣。相鄰的數之間用一個空格隔開
樣例輸入
2 2
1 2
3 4
樣例輸出
7 10
15 22
28、分解質因數（質數分解 循環）
問題描述
求出區間[a,b]中所有整數的質因數分解。
輸入格式
輸入兩個整數a，b。
輸出格式
每行輸出一個數的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是從小到大的)(具體可看樣例)
樣例輸入
3 10
樣例輸出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先篩出所有素數，然后再分解。
數據規模和約定
2<=a<=b<=10000
29、字符串對比（字符串 大小寫）
問題描述
給定兩個僅由大寫字母或小寫字母組成的字符串(長度介于1到10之間)，它們之間的關系是以下4中情況之一：
1：兩個字符串長度不等。比如 Beijing 和 Hebei
2：兩個字符串不僅長度相等，而且相應位置上的字符完全一致(區分大小寫)，比如 Beijing 和 Beijing
3：兩個字符串長度相等，相應位置上的字符僅在不區分大小寫的前提下才能達到完全一致（也就是說，它并不滿足情況2）。比如 beijing 和 BEIjing
4：兩個字符串長度相等，但是即使是不區分大小寫也不能使這兩個字符串一致。比如 Beijing 和 Nanjing
編程判斷輸入的兩個字符串之間的關系屬于這四類中的哪一類，給出所屬的類的編號。
輸入格式
包括兩行，每行都是一個字符串
輸出格式
僅有一個數字，表明這兩個字符串的關系編號
樣例輸入
BEIjing
beiJing
樣例輸出
3
30、時間轉換(取余 數字字符混合輸出)
問題描述
給定一個以秒為單位的時間t，要求用“::”的格式來表示這個時間。表示時間，表示分鐘，而表示秒，它們都是整數且沒有前導的“0”。例如，若t=0，則應輸出是“0:0:0”；若t=3661，則輸出“1:1:1”。
輸入格式
輸入只有一行，是一個整數t（0<=t<=86399）。
輸出格式
輸出只有一行，是以“::”的格式所表示的時間，不包括引號。
樣例輸入
0
樣例輸出
0:0:0
樣例輸入
5436
樣例輸出
1:30:36
31、操作格子（線段樹）
問題描述
有n個格子，從左到右放成一排，編號為1-n。
共有m次操作，有3種操作類型：
1.修改一個格子的權值，
2.求連續一段格子權值和，
3.求連續一段格子的最大值。
對于每個2、3操作輸出你所求出的結果。
輸入格式
第一行2個整數n，m。
接下來一行n個整數表示n個格子的初始權值。
接下來m行，每行3個整數p,x,y，p表示操作類型，p=1時表示修改格子x的權值為y，p=2時表示求區間[x,y]內格子權值和，p=3時表示求區間[x,y]內格子最大的權值。
輸出格式
有若干行，行數等于p=2或3的操作總數。
每行1個整數，對應了每個p=2或3操作的結果。
樣例輸入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
樣例輸出
6
3
數據規模與約定
對于20%的數據n <= 100，m <= 200。
對于50%的數據n <= 5000，m <= 5000。
對于100%的數據1 <= n <= 100000，m <= 100000，0 <= 格子權值 <= 10000。
32、逆序對（平衡二叉樹）
問題描述
Alice是一個讓人非常愉躍的人!他總是去學習一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序對的快樂當中，他已近學會了如何求逆序對對數，動態維護逆序對對數等等題目，他認為把這些題讓你做簡直是太沒追求了，于是，經過一天的思考和完善，Alice終于拿出了一道他認為差不多的題目：
有一顆2n-1個節點的二叉樹，它有恰好n個葉子節點，每個節點上寫了一個整數。如果將這棵樹的所有葉子節點上的數從左到右寫下來，便得到一個序列a[1]…a[n]。現在想讓這個序列中的逆序對數量最少，但唯一的操作就是選樹上一個非葉子節點，將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優方案下，該序列的逆序對數最少有多少。
Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時間內完成。
輸入格式
第一行一個整數n。
下面每行，一個數x。
如果x=0，表示這個節點非葉子節點，遞歸地向下讀入其左孩子和右孩子的信息，如果x≠0，表示這個節點是葉子節點，權值為x。
輸出格式
輸出一個整數，表示最少有多少逆序對。
樣例輸入
3
0
0
3
1
2
樣例輸出
1
數據規模與約定
對于20%的數據，n <= 5000。
對于100%的數據，1 <= n <= 200000，0 <= a[i]<2^31。
33、安慰奶牛（最小生成樹）
問題描述
Farmer John變得非常懶，他不想再繼續維護供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續地編號為1到N。每一個牧場都是一個奶牛的家。FJ計劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因為她們的交通系統被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達第i個牧場的時候(即使你已經到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務。假設Farmer John采納了你的建議，請計算出使所有奶牛都被安慰的最少時間。
輸入格式
第1行包含兩個整數N和P。
接下來N行，每行包含一個整數Ci。
接下來P行，每行包含三個整數Sj, Ej和Lj。
輸出格式
輸出一個整數, 所需要的總時間(包含和在你所在的牧場的奶牛的兩次談話時間)。
樣例輸入
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
樣例輸出
176
數據規模與約定
5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。
34、最短路（最短路）
問題描述
給定一個n個頂點，m條邊的有向圖（其中某些邊權可能為負，但保證沒有負環）。請你計算從1號點到其他點的最短路（頂點從1到n編號）。
輸入格式
第一行兩個整數n, m。
接下來的m行，每行有三個整數u, v, l，表示u到v有一條長度為l的邊。
輸出格式
共n-1行，第i行表示1號點到i+1號點的最短路。
樣例輸入
3 3
1 2 -1
2 3 -1
3 1 2
樣例輸出
-1
-2
數據規模與約定
對于10%的數據，n = 2，m = 2。
對于30%的數據，n <= 5，m <= 10。
對于100%的數據，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點都能到達其他所有頂點。
35、結點選擇（樹形動態規劃）
問題描述
有一棵 n 個節點的樹，樹上每個節點都有一個正整數權值。如果一個點被選擇了，那么在樹上和它相鄰的點都不能被選擇。求選出的點的權值和最大是多少？
輸入格式
第一行包含一個整數 n 。
接下來的一行包含 n 個正整數，第 i 個正整數代表點 i 的權值。
接下來一共 n-1 行，每行描述樹上的一條邊。
輸出格式
輸出一個整數，代表選出的點的權值和的最大值。
樣例輸入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
樣例輸出
12
樣例說明
選擇3、4、5號點，權值和為 3+4+5 = 12 。
數據規模與約定
對于20%的數據， n <= 20。
對于50%的數據， n <= 1000。
對于100%的數據， n <= 100000。
權值均為不超過1000的正整數。
36、K好數（動態規劃）
問題描述
如果一個自然數N的K進制表示中任意的相鄰的兩位都不是相鄰的數字，那么我們就說這個數是K好數。求L位K進制數中K好數的數目。例如K = 4，L = 2的時候，所有K好數為11、13、20、22、30、31、33 共7個。由于這個數目很大，請你輸出它對1000000007取模后的值。
輸入格式
輸入包含兩個正整數，K和L。
輸出格式
輸出一個整數，表示答案對1000000007取模后的值。
樣例輸入
4 2
樣例輸出
7
數據規模與約定
對于30%的數據，KL <= 106；
對于50%的數據，K <= 16， L <= 10；
對于100%的數據，1 <= K,L <= 100。
37、最大最小公倍數（貪心）
問題描述
已知一個正整數N，問從1~N-1中任選出三個數，他們的最小公倍數最大可以為多少。
輸入格式
輸入一個正整數N。
輸出格式
輸出一個整數，表示你找到的最小公倍數。
樣例輸入
9
樣例輸出
504
數據規模與約定
1 <= N <= 106。
38、區間k大數查詢（排序 查找）
問題描述
給定一個序列，每次詢問序列中第l個數到第r個數中第K大的數是哪個。
輸入格式
第一行包含一個數n，表示序列長度。
第二行包含n個正整數，表示給定的序列。
第三個包含一個正整數m，表示詢問個數。
接下來m行，每行三個數l,r,K，表示詢問序列從左往右第l個數到第r個數中，從大往小第K大的數是哪個。序列元素從1開始標號。
輸出格式
總共輸出m行，每行一個數，表示詢問的答案。
樣例輸入
5
1 2 3 4 5
2
1 5 2
2 3 2
樣例輸出
4
2
數據規模與約定
對于30%的數據，n,m<=100；
對于100%的數據，n,m<=1000；
保證k<=(r-l+1)，序列中的數<=106。
39、區間k大數查詢（排序 查找）
問題描述
給定一個序列，每次詢問序列中第l個數到第r個數中第K大的數是哪個。
輸入格式
第一行包含一個數n，表示序列長度。
第二行包含n個正整數，表示給定的序列。
第三個包含一個正整數m，表示詢問個數。
接下來m行，每行三個數l,r,K，表示詢問序列從左往右第l個數到第r個數中，從大往小第K大的數是哪個。序列元素從1開始標號。
輸出格式
總共輸出m行，每行一個數，表示詢問的答案。
樣例輸入
5
1 2 3 4 5
2
1 5 2
2 3 2
樣例輸出
4
2
數據規模與約定
對于30%的數據，n,m<=100；
對于100%的數據，n,m<=1000；
保證k<=(r-l+1)，序列中的數<=106。
40、接水問題（模擬）
問題描述
學校里有一個水房，水房里一共裝有m 個龍頭可供同學們打開水，每個龍頭每秒鐘的 供水量相等，均為1。 現在有n 名同學準備接水，他們的初始接水順序已經確定。將這些同學按接水順序從1 到n 編號，i 號同學的接水量為wi。接水開始時，1 到m 號同學各占一個水龍頭，并同時打 開水龍頭接水。當其中某名同學j 完成其接水量要求wj 后，下一名排隊等候接水的同學k 馬上接替j 同學的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即 j 同學第x 秒結束時完成接水，則k 同學第x+1 秒立刻開始接水。若當前接水人數n’不足m， 則只有n’個龍頭供水，其它m?n’個龍頭關閉。 現在給出n 名同學的接水量，按照上述接水規則，問所有同學都接完水需要多少秒。
輸入格式
第1 行2 個整數n 和m，用一個空格隔開，分別表示接水人數和龍頭個數。 第2 行n 個整數w1、w2、……、wn，每兩個整數之間用一個空格隔開，wi 表示i 號同 學的接水量。
輸出格式
輸出只有一行，1 個整數，表示接水所需的總時間。
樣例輸入
5 3
4 4 1 2 1
樣例輸出
4
樣例輸入
8 4
23 71 87 32 70 93 80 76
樣例輸出
163
輸入輸出樣例 1 說明
第1 秒，3 人接水。第1 秒結束時，1、2、3 號同學每人的已接水量為1，3 號同學接完
水，4 號同學接替3 號同學開始接水。
第2 秒，3 人接水。第2 秒結束時，1、2 號同學每人的已接水量為2，4 號同學的已接
水量為1。
第3 秒，3 人接水。第3 秒結束時，1、2 號同學每人的已接水量為3，4 號同學的已接
水量為2。4 號同學接完水，5 號同學接替4 號同學開始接水。
第4 秒，3 人接水。第4 秒結束時，1、2 號同學每人的已接水量為4，5 號同學的已接
水量為1。1、2、5 號同學接完水，即所有人完成接水。
總接水時間為4 秒。
數據規模和約定
1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；
1 ≤ wi ≤ 100。
41、Hankson的趣味題（數論）
問題描述
Hanks 博士是BT (Bio-Tech，生物技術) 領域的知名專家，他的兒子名叫Hankson。現 在，剛剛放學回家的Hankson 正在思考一個有趣的問題。 今天在課堂上，老師講解了如何求兩個正整數c1 和c2 的最大公約數和最小公倍數。現 在Hankson 認為自己已經熟練地掌握了這些知識，他開始思考一個“求公約數”和“求公 倍數”之類問題的“逆問題”，這個問題是這樣的：已知正整數a0,a1,b0,b1，設某未知正整 數x 滿足： 1． x 和a0 的最大公約數是a1； 2． x 和b0 的最小公倍數是b1。 Hankson 的“逆問題”就是求出滿足條件的正整數x。但稍加思索之后，他發現這樣的 x 并不唯一，甚至可能不存在。因此他轉而開始考慮如何求解滿足條件的x 的個數。請你幫 助他編程求解這個問題。
輸入格式
輸入第一行為一個正整數n，表示有n 組輸入數據。
接下來的n 行每 行一組輸入數據，為四個正整數a0，a1，b0，b1，每兩個整數之間用一個空格隔開。輸入 數據保證a0 能被a1 整除，b1 能被b0 整除。
輸出格式
輸出共n 行。每組輸入數據的輸出結果占一行，為一個整數。
對于每組數據：若不存在這樣的 x，請輸出0； 若存在這樣的 x，請輸出滿足條件的x 的個數；
樣例輸入
2
41 1 96 288
95 1 37 1776
樣例輸出
6
2
樣例說明
第一組輸入數據，x 可以是9、18、36、72、144、288，共有6 個。
第二組輸入數據，x 可以是48、1776，共有2 個。
數據規模和約定
對于 50%的數據，保證有1≤a0，a1，b0，b1≤10000 且n≤100。
對于 100%的數據，保證有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。
42、傳紙條（動態規劃）
問題描述
小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。一次素質拓展活動中，班上同學安排做成一個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標(1,1)，小軒坐在矩陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。
在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。
還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用0表示），可以用一個0-100的自然數來表示，數越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度只和最大。現在，請你幫助小淵和小軒找到這樣的兩條路徑。
輸入格式
輸入第一行有2個用空格隔開的整數m和n，表示班里有m行n列（1<=m,n<=50）。
接下來的m行是一個mn的矩陣，矩陣中第i行j列的整數表示坐在第i行j列的學生的好心程度。每行的n個整數之間用空格隔開。
輸出格式
輸出一行，包含一個整數，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。
樣例輸入
3 3
0 3 9
2 8 5
5 7 0
樣例輸出
34
數據規模和約定
30%的數據滿足：1<=m,n<=10
100%的數據滿足：1<=m,n<=50
43、傳球游戲（動態規劃）
問題描述
上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。
游戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節目。
聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，并假設小蠻為1號，球傳了3次回到小蠻手里的方式有1->2->3->1和1->3->2->1，共2種。
輸入格式
共一行，有兩個用空格隔開的整數n，m（3<=n<=30，1<=m<=30）。
輸出格式
t共一行，有一個整數，表示符合題意的方法數。
樣例輸入
3 3
樣例輸出
2
數據規模和約定
40%的數據滿足：3<=n<=30，1<=m<=20
100%的數據滿足：3<=n<=30，1<=m<=30
44、紀念品分組（貪心 排序）
問題描述
元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發放工作。為使得參加晚會的同學所獲得的紀念品價值 相對均衡，他要把購來的紀念品根據價格進行分組，但每組最多只能包括兩件紀念品，并且每組紀念品的價格之和不能超過一個給定的整數。為了保證在盡量短的時 間內發完所有紀念品，樂樂希望分組的數目最少。
你的任務是寫一個程序，找出所有分組方案中分組數最少的一種，輸出最少的分組數目。
輸入格式
輸入包含n+2行：
第1行包括一個整數w，為每組紀念品價格之和的上限。
第2行為一個整數n，表示購來的紀念品的總件數。
第3~n+2行每行包含一個正整數pi (5 <= pi <= w)，表示所對應紀念品的價格。
輸出格式
輸出僅一行，包含一個整數，即最少的分組數目。
樣例輸入
100
9
90
20
20
30
50
60
70
80
90
樣例輸出
6
數據規模和約定
50%的數據滿足：1 <= n <= 15
100%的數據滿足：1 <= n <= 30000, 80 <= w <= 200
45、數列（數學 進制）
問題描述
給定一個正整數k(3≤k≤15),把所有k的方冪及所有有限個互不相等的k的方冪之和構成一個遞增的序列，例如，當k=3時，這個序列是：
1，3，4，9，10，12，13，…
（該序列實際上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
請你求出這個序列的第N項的值（用10進制數表示）。
例如，對于k=3，N=100，正確答案應該是981。
輸入格式
只有1行，為2個正整數，用一個空格隔開：
k N
（k、N的含義與上述的問題描述一致，且3≤k≤15，10≤N≤1000）。
輸出格式
計算結果，是一個正整數（在所有的測試數據中，結果均不超過2.1109）。（整數前不要有空格和其他符號）。
樣例輸入
3 100
樣例輸出
981
46、JAM計數法（組合生成）
問題描述
Jam是個喜歡標新立異的科學怪人。他不使用阿拉伯數字計數，而是使用小寫英文字母計數，他覺得這樣做，會使世界更加豐富多彩。在他的計數法中，每個數字的位數都是相同的（使用相同個數的字母），英文字母按原先的順序，排在前面的字母小于排在它后面的字母。我們把這樣的“數字”稱為Jam數字。在Jam數字中，每個字母互不相同，而且從左到右是嚴格遞增的。每次，Jam還指定使用字母的范圍，例如，從2到10，表示只能使用{b,c,d,e,f,g,h,i,j}這些字母。如果再規定位數為5，那么，緊接在Jam數字“bdfij”之后的數字應該是“bdghi”。（如果我們用U、V依次表示Jam數字“bdfij”與“bdghi”，則U<V< span>，且不存在Jam數字P，使U<P<V< span>）。你的任務是：對于從文件讀入的一個Jam數字，按順序輸出緊接在后面的5個Jam數字，如果后面沒有那么多Jam數字，那么有幾個就輸出幾個。
輸入格式
有2行，第1行為3個正整數，用一個空格隔開：
s t w
（其中s為所使用的最小的字母的序號，t為所使用的最大的字母的序號。w為數字的位數，這3個數滿足：1≤s<T≤26, 2≤w≤t-s ）
第2行為具有w個小寫字母的字符串，為一個符合要求的Jam數字。
所給的數據都是正確的，不必驗證。
輸出格式
最多為5行，為緊接在輸入的Jam數字后面的5個Jam數字，如果后面沒有那么多Jam數字，那么有幾個就輸出幾個。每行只輸出一個Jam數字，是由w個小寫字母組成的字符串，不要有多余的空格。
樣例輸入
2 10 5
bdfij
樣例輸出
bdghi
bdghj
bdgij
bdhij
befgh
47、開心的金明（01背包 動態規劃）
問題描述
金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎 么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規定了一 個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N元（可以等于N元）的前提 下，使每件物品的價格與重要度的乘積的總和最大。
設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為 j1，j2，……，jk，則所求的總和為：
v[j1]w[j1]+v[j2]w[j2]+ …+v[jk]w[jk]。（其中為乘號）
請 你幫助金明設計一個滿足要求的購物單。
輸入格式
輸入文件 的第1行，為兩個正整數，用一個空格隔開：
N m
（其中N（<30000）表示總錢 數，m（<25）為希望購買物品的個數。）
從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有2個非負整數
v p
（其中v表示該物品的價格(v<=10000)，p表示該物品的重要度(1~5)）
輸出格式
輸出文件只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<100000000）。
樣例輸入
1000 5
800 2
400 5
300 5
400 3
200 2
樣例輸出
3900
數據規模和約定
48、入學考試（0/1背包 動態規劃）
問題描述
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”
如果你是辰辰，你能完成這個任務嗎？
輸入格式
第一行有兩個整數T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示采摘某株草藥的時間和這株草藥的價值。
輸出格式
包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
樣例輸入
70 3
71 100
69 1
1 2
樣例輸出
3
數據規模和約定
對于30%的數據，M <= 10；
對于全部的數據，M <= 100。
49、校門外的樹（區間處理）
問題描述
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數 軸上的每個整數點，即0，1，2，……，L，都種有一棵樹。
由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已 知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹 都移走后，馬路上還有多少棵樹。
輸入格式
輸入文件的第一行有兩個整數L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點 和終止點的坐標。
輸出格式
輸出文件包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目。
樣例輸入
500 3
150 300
100 200
470 471
樣例輸出
298
數據規模和約定
對于20%的數據，區域之間沒有重合的部分；
對于其它的數據，區域之間有重合的情況。
50、星際交流（排列生成算法）
問題描述
人類終于登上了火星的土地并且見到了神秘的火星人。人類和火星人都無法理解對方的語言，但是我們的科學家發明了一種用數字交流的方法。這種交流方法是這樣 的，首先，火星人把一個非常大的數字告訴人類科學家，科學家破解這個數字的含義后，再把一個很小的數字加到這個大數上面，把結果告訴火星人，作為人類的回 答。
火星人用一種非常簡單的方式來表示數字——掰手指。火星人只有一只手，但這只手上有成千上萬的手指，這些手指排成一列，分別編號為1，2，3……。火星人的任意兩根手指都能隨意交換位置，他們就是通過這方法計數的。
一個火星人用一個人類的手演示了如何用手指計數。如果把五根手指——拇指、食指、中指、無名指和小指分別編號為1，2，3，4和5，當它們按正常順序排列 時，形成了5位數12345，當你交換無名指和小指的位置時，會形成5位數12354，當你把五個手指的順序完全顛倒時，會形成54321，在所有能夠形 成的120個5位數中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指時能夠形成的6個 3位數和它們代表的數字：
三進制數
123
132
213
231
312
321
代表的數字
1
2
3
4
5
6
現在你有幸成為了第一個和火星人交流的地球人。一個火星人會讓你看他的手指，科學家會告訴你要加上去的很小的數。你的任務是，把火星人用手指表示的數與科 學家告訴你的數相加，并根據相加的結果改變火星人手指的排列順序。輸入數據保證這個結果不會超出火星人手指能表示的范圍。
輸入格式
包括三行，第一行有一個正整數N，表示火星人手指的數目（1 <= N <= 10000）。第二行是一個正整數M，表示要加上去的小整數（1 <= M <= 100）。下一行是1到N這N個整數的一個排列，用空格隔開，表示火星人手指的排列順序。
輸出格式
只有一行，這一行含有N個整數，表示改變后的火星人手指的排列順序。每兩個相鄰的數中間用一個空格分開，不能有多余的空格。
樣例輸入
5
3
1 2 3 4 5
樣例輸出
1 2 4 5 3
數據規模和約定
對于30%的數據，N<=15；
對于60%的數據，N<=50；
對于全部的數據，N<=10000；
21、FBI樹（樹 遍歷）
問題描述
我們可以把由“0”和“1”組成的字符串分為三類：全“0”串稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。
FBI樹是一種二叉樹，它的結點類型也包括F結點，B結點和I結點三種。由一個長度為2N的“01”串S可以構造出一棵FBI樹T，遞歸的構造方法如下：
1)T的根結點為R，其類型與串S的類型相同；
2)若串S的長度大于1，將串S從中間分開，分為等長的左右子串S1和S2；由左子串S1構造R的左子樹T1，由右子串S2構造R的右子樹T2。
現在給定一個長度為2N的“01”串，請用上述構造方法構造出一棵FBI樹，并輸出它的后序遍歷序列。
輸入格式
第一行是一個整數N（0 <= N <= 10），第二行是一個長度為2N的“01”串。
輸出格式
包括一行，這一行只包含一個字符串，即FBI樹的后序遍歷序列。
樣例輸入
3
10001011
樣例輸出
IBFBBBFIBFIIIFF
數據規模和約定
對于40%的數據，N <= 2；
對于全部的數據，N <= 10。
注：
[1] 二叉樹：二叉樹是結點的有限集合，這個集合或為空集，或由一個根結點和兩棵不相交的二叉樹組成。這兩棵不相交的二叉樹分別稱為這個根結點的左子樹和右子樹。
[2] 后序遍歷：后序遍歷是深度優先遍歷二叉樹的一種方法，它的遞歸定義是：先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根。
51、麥森數（二分 高精度）
問題描述
形如2P-1的素數稱為麥森數，這時P一定也是個素數。但反過來不一定，即如果P是個素數，2P-1不一定也是素數。到1998年底，人們已找到了37個麥森數。最大的一個是P=3021377，它有909526位。麥森數有許多重要應用，它與完全數密切相關。
任務：從文件中輸入P（1000<P<3100000），計算2P-1的位數和最后500位數字（用十進制高精度數表示）
輸入格式
文件中只包含一個整數P（1000<P<3100000）
輸出格式
第一行：十進制高精度數2P-1的位數。
第2-11行：十進制高精度數2P-1的最后500位數字。（每行輸出50位，共輸出10行，不足500位時高位補0）
不必驗證2P-1與P是否為素數。
樣例輸入
1279
樣例輸出
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
52、Car的旅行路線（最短路）
問題描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每個城市都有四個飛機場，分別位于一個矩形的四個頂點上，同一個城市中兩個機場之間有一 條筆直的高速鐵路，第I個城市中高速鐵路了的單位里程價格為Ti，任意兩個不同城市的機場之間均有航線，所有航線單位里程的價格均為t。
那么Car應如何安排到城市B的路線才能盡可能的節省花費呢?她發現這并不是一個簡單的問題，于是她來向你請教。
找出一條從城市A到B的旅游路線，出發和到達城市中的機場可以任意選取，要求總的花費最少。
輸入格式
的第一行有四個正整數s，t，A，B。
S表示城市的個數，t表示飛機單位里程的價格，A，B分別為城市A，B的序號，(1<=A，B<=S)。
接下來有S行，其中第I行均有7個正整數xi1，yi1，xi2，yi2，xi3，yi3，Ti，這當中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分別是第I個城市中任意三個機場的坐標，T I為第I個城市高速鐵路單位里程的價格。
輸出格式
共有n行，每行一個數據對應測試數據，保留一位小數。
樣例輸入
1
1 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
樣例輸出
47.55
數據規模和約定
0<S<=100，
53、統計單詞個數（字符串）
問題描述
給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串以每行20個字母的方式輸入，且保證每行一定為20個)。要求將此字母串分成k份 (1<k<=40)，且每份中包含的單詞個數加起來總數最大(每份中包含的單詞可以部分重疊。當選用一個單詞之后，其第一個字母不能再用。例 如字符串this中可包含this和is，選用this之后就不能包含th)。
單詞在給出的一個不超過6個單詞的字典中。
要求輸出最大的個數。
輸入格式
第一行有二個正整數(p，k)
p表示字串的行數;
k表示分為k個部分。
接下來的p行，每行均有20個字符。
再接下來有一個正整數s，表示字典中單詞個數。(1<=s<=6)
接下來的s行，每行均有一個單詞。
輸出格式
每行一個整數，分別對應每組測試數據的相應結果。
樣例輸入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
樣例輸出
7
數據規模和約定
長度不超過200，1<k<=40，字典中的單詞數不超過6。
54、一元三次方程求解（解方程）
問題描述
有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(a，b，c，d 均為實數)，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求三個實根。。
輸入格式
四個實數：a，b，c，d
輸出格式
由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數點后2位
樣例輸入
1 -5 -4 20
樣例輸出
-2.00 2.00 5.00
數據規模和約定
|a|，|b|，|c|，|d|<=10
55、數的劃分（動態規劃）
問題描述
將整數n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。
例如：n=7，k=3，下面三種分法被認為是相同的。
1，1，5; 1，5，1; 5，1，1;
問有多少種不同的分法。
輸入格式
n，k
輸出格式
一個整數，即不同的分法
樣例輸入
7 3
樣例輸出
4 {四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}
數據規模和約定
6<n<=200，2<=k<=6
56、裝箱問題（動態規劃）
問題描述
有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30），每個物品有一個體積（正整數）。
要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。
輸入格式
第一行為一個整數，表示箱子容量；
第二行為一個整數，表示有n個物品；
接下來n行，每行一個整數表示這n個物品的各自體積。
輸出格式
一個整數，表示箱子剩余空間。
樣例輸入
24
6
8
3
12
7
9
7
樣例輸出
0
57、求先序排列（遞歸）
問題描述
給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結點用不同的大寫字母表示，長度<=8）。
輸入格式
兩行，每行一個字符串，分別表示中序和后序排列
輸出格式
一個字符串，表示所求先序排列
樣例輸入
BADC
BDCA
樣例輸出
ABCD
58、方格取數（動態規劃）
問題描述
設有NN的方格圖(N<=10),我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。
某人從圖的左上角的A 點(1,1)出發，可以向下行走，也可以向右走，直到到達右下角的B點(N,N)。在走過的路上，他可以取走方格中的數（取走后的方格中將變為數字0）。
此人從A點到B 點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
輸入格式
輸入的第一行為一個整數N（表示NN的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的0表示輸入結束。
輸出格式
只需輸出一個整數，表示2條路徑上取得的最大的和。
樣例輸入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
樣例輸出
67
59、單詞接龍（搜索）
問題描述
單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如 beast和astonish，如果接成一條龍則變為beastonish，另外相鄰的兩部分不能存在包含關系，例如at 和 atide 間不能相連。
輸入格式
輸入的第一行為一個單獨的整數n (n<=20)表示單詞數，以下n 行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在.
輸出格式
只需輸出以此字母開頭的最長的“龍”的長度
樣例輸入
5
at
touch
cheat
choose
tact
a
樣例輸出
23
樣例說明
連成的“龍”為atoucheatactactouchoose
60、乘積最大（動態規劃）
問題描述
今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場別開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
設有一個長度為N的數字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：
有一個數字串：312， 當N=3，K=1時會有以下兩種分法：
312=36
312=62
這時，符合題目要求的結果是：31*2=62
現在，請你幫助你的好朋友XZ設計一個程序，求得正確的答案。
輸入格式
程序的輸入共有兩行：
第一行共有2個自然數N，K（6≤N≤40，1≤K≤6）
第二行是一個長度為N的數字串。
輸出格式
輸出所求得的最大乘積（一個自然數）。
樣例輸入
4 2
1231
樣例輸出
62
61、進制轉換（進制轉換）
問題描述
我們可以用這樣的方式來表示一個十進制數： 將每個阿拉伯數字乘以一個以該數字所處位置的（值減１）為指數，以１０為底數的冪之和的形式。例如：１２３可表示為 １＊１０２＋２＊１０１＋３＊１００這樣的形式。
與之相似的，對二進制數來說，也可表示成每個二進制數碼乘以一個以該數字所處位置的（值－１）為指數，以２為底數的冪之和的形式。一般說來，任何一個正整數Ｒ或一個負整數－Ｒ都可以被選來作為一個數制系統的基數。如果是以Ｒ或－Ｒ為基數，則需要用到的數碼為 ０，１，．．．．Ｒ－１。例如，當Ｒ＝７時，所需用到的數碼是０，１，２，３，４，５和６，這與其是Ｒ或－Ｒ無關。如果作為基數的數絕對值超過１０，則為了表示這些數碼，通常使用英文字母來表示那些大于９的數碼。例如對１６進制數來說，用Ａ表示１０，用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。
在負進制數中是用－Ｒ 作為基數，例如－１５（十進制）相當于１１０００１（－２進制），并且它可以被表示為２的冪級數的和數：
１１０００１＝１＊（－２）５＋１＊（－２）４＋０＊（－２）３＋０＊（－２）２＋
０＊（－２）１ ＋１＊（－２）０
設計一個程序，讀入一個十進制數和一個負進制數的基數, 并將此十進制數轉換為此負進制下的數： －Ｒ∈｛－２，－３，－４，．．．，－２０｝
輸入格式
一行兩個數，第一個是十進制數Ｎ（－32768＜＝Ｎ＜＝32767）， 第二個是負進制數的基數－Ｒ。
輸出格式
輸出所求負進制數及其基數，若此基數超過１０，則參照１６進制的方式處理。（格式參照樣例）
樣例輸入
30000 -2
樣例輸出
30000=11011010101110000(base-2)
樣例輸入
-20000 -2
樣例輸出
-20000=1111011000100000(base-2)
樣例輸入
28800 -16
樣例輸出
28800=19180(base-16)
樣例輸入
-25000 -16
樣例輸出
-25000=7FB8(base-16)
62、旅行家的預算（貪心）
問題描述
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱是空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發點每升汽油價格P和沿途油站數N（N可以為零），油站i離出發點的距離Di、每升汽油價格Pi（i=1，2，……N）。計算結果四舍五入至小數點后兩位。如果無法到達目的地，則輸出“No Solution”。
輸入格式
第一行為4個實數D1、C、D2、P與一個非負整數N；
接下來N行，每行兩個實數Di、Pi。
輸出格式
如果可以到達目的地，輸出一個實數（四舍五入至小數點后兩位），表示最小費用；否則輸出“No Solution”（不含引號）。
樣例輸入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
樣例輸出
26.95
63、回文數（模擬 高精度計算）
問題描述
若一個數（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數。
例如：給定一個10進制數56，將56加65（即把56從右向左讀），得到121是一個回文數。
又如：對于10進制數87：
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數4884。
寫一個程序，給定一個N（2<=N<=10或N=16）進制數M（其中16進制數字為0-9與A-F），求最少經過幾步可以得到回文數。
如果在30步以內（包含30步）不可能得到回文數，則輸出“Impossible!”
輸入格式
兩行，N與M
輸出格式
如果能在30步以內得到回文數，輸出“STEP=xx”（不含引號），其中xx是步數；否則輸出一行”Impossible!”（不含引號）
樣例輸入
9
87
樣例輸出
STEP=6
64、攔截導彈（貪心 動態規劃）
問題描述
某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
輸入格式
一行，為導彈依次飛來的高度
輸出格式
兩行，分別是最多能攔截的導彈數與要攔截所有導彈最少要配備的系統數
樣例輸入
389 207 155 300 299 170 158 65
樣例輸出
6
2
65、冪方分解（遞歸）
問題描述
任何一個正整數都可以用2的冪次方表示。例如：
137=27+23+20
同時約定方次用括號來表示，即ab 可表示為a（b）。
由此可知，137可表示為：
2（7）+2（3）+2（0）
進一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示為：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=210 +28 +25 +2+1
所以1315最后可表示為：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
輸入格式
輸入包含一個正整數N（N<=20000），為要求分解的整數。
輸出格式
程序輸出包含一行字符串，為符合約定的n的0，2表示（在表示中不能有空格）
66、瓷磚鋪放（遞歸）
問題描述
有一長度為N(1<=Ｎ<=10)的地板，給定兩種不同瓷磚：一種長度為1，另一種長度為2，數目不限。要將這個長度為N的地板鋪滿，一共有多少種不同的鋪法？
例如，長度為4的地面一共有如下5種鋪法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
編程用遞歸的方法求解上述問題。
輸入格式
只有一個數N，代表地板的長度
輸出格式
輸出一個數，代表所有不同的瓷磚鋪放方法的總數
樣例輸入
4
樣例輸出
5
67、集合運算（數組 排序）
問題描述
給出兩個整數集合A、B，求出他們的交集、并集以及B在A中的余集。
輸入格式
第一行為一個整數n，表示集合A中的元素個數。
第二行有n個互不相同的用空格隔開的整數，表示集合A中的元素。
第三行為一個整數m，表示集合B中的元素個數。
第四行有m個互不相同的用空格隔開的整數，表示集合B中的元素。
集合中的所有元素均為int范圍內的整數，n、m<=1000。
輸出格式
第一行按從小到大的順序輸出A、B交集中的所有元素。
第二行按從小到大的順序輸出A、B并集中的所有元素。
第三行按從小到大的順序輸出B在A中的余集中的所有元素。
樣例輸入
5
1 2 3 4 5
5
2 4 6 8 10
樣例輸出
2 4
1 2 3 4 5 6 8 10
1 3 5
樣例輸入
4
1 2 3 4
3
5 6 7
樣例輸出
1 2 3 4 5 6 7
1 2 3 4
68、擺動序列（動態規劃）
問題描述
如果一個序列滿足下面的性質，我們就將它稱為擺動序列： - 序列中的所有數都是不大于k的正整數；
- 序列中至少有兩個數。
- 序列中的數兩兩不相等；
- 如果第i – 1個數比第i – 2個數大，則第i個數比第i – 2個數小；如果第i – 1個數比第i – 2個數小，則第i個數比第i – 2個數大。
比如，當k = 3時，有下面幾個這樣的序列：
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
一共有8種，給定k，請求出滿足上面要求的序列的個數。
輸入格式
輸入包含了一個整數k。（k<=20）
輸出格式
輸出一個整數，表示滿足要求的序列個數。
樣例輸入
3
樣例輸出
8
69、最小方差生成樹（最小生成樹）
問題描述
給定帶權無向圖，求出一顆方差最小的生成樹。
輸入格式
輸入多組測試數據。第一行為N,M，依次是點數和邊數。接下來M行，每行三個整數U,V,W，代表連接U,V的邊，和權值W。保證圖連通。n=m=0標志著測試文件的結束。
輸出格式
對于每組數據，輸出最小方差，四舍五入到0.01。輸出格式按照樣例。
樣例輸入
4 5
1 2 1
2 3 2
3 4 2
4 1 1
2 4 3
4 6
1 2 1
2 3 2
3 4 3
4 1 1
2 4 3
1 3 3
0 0
樣例輸出
Case 1: 0.22
Case 2: 0.00
數據規模與約定
1<=U,V<=N<=50,N-1<=M<=1000,0<=W<=50。數據不超過5組。
70、道路和航路（最短路）
問題描述
農夫約翰正在針對一個新區域的牛奶配送合同進行研究。他打算分發牛奶到T個城鎮（標號為1…T），這些城鎮通過R條標號為（1…R）的道路和P條標號為（1…P）的航路相連。
每一條公路i或者航路i表示成連接城鎮Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代價為Ci。每一條公路，Ci的范圍為0<=Ci<=10,000；由于奇怪的運營策略，每一條航路的Ci可能為負的，也就是-10,000<=Ci<=10,000。
每一條公路都是雙向的，正向和反向的花費是一樣的，都是非負的。
每一條航路都根據輸入的Ai和Bi進行從Ai->Bi的單向通行。實際上，如果現在有一條航路是從Ai到Bi的話，那么意味著肯定沒有通行方案從Bi回到Ai。
農夫約翰想把他那優良的牛奶從配送中心送到各個城鎮，當然希望代價越小越好，你可以幫助他嘛？配送中心位于城鎮S中（1<=S<=T）。
輸入格式
輸入的第一行包含四個用空格隔開的整數T，R，P，S。
接下來R行，描述公路信息，每行包含三個整數，分別表示Ai，Bi和Ci。
接下來P行，描述航路信息，每行包含三個整數，分別表示Ai，Bi和Ci。
輸出格式
輸出T行，分別表示從城鎮S到每個城市的最小花費，如果到不了的話輸出NO PATH。
樣例輸入
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
樣例輸出
NO PATH
NO PATH
5
0
-95
-100
數據規模與約定
對于20%的數據，T<=100，R<=500，P<=500；
對于30%的數據，R<=1000，R<=10000，P<=3000；
對于100%的數據，1<=T<=25000，1<=R<=50000，1<=P<=50000。
71、金屬采集（樹形動態規劃）
問題描述
人類在火星上發現了一種新的金屬！這些金屬分布在一些奇怪的地方，不妨叫它節點好了。一些節點之間有道路相連，所有的節點和道路形成了一棵樹。一共有 n 個節點，這些節點被編號為 1~n 。人類將 k 個機器人送上了火星，目的是采集這些金屬。這些機器人都被送到了一個指定的著落點， S 號節點。每個機器人在著落之后，必須沿著道路行走。當機器人到達一個節點時，它會采集這個節點蘊藏的所有金屬礦。當機器人完成自己的任務之后，可以從任意一個節點返回地球。當然，回到地球的機器人就無法再到火星去了。我們已經提前測量出了每條道路的信息，包括它的兩個端點 x 和 y，以及通過這條道路需要花費的能量 w 。我們想花費盡量少的能量采集所有節點的金屬，這個任務就交給你了。
輸入格式
第一行包含三個整數 n, S 和 k ，分別代表節點個數、著落點編號，和機器人個數。
接下來一共 n-1 行，每行描述一條道路。一行含有三個整數 x, y 和 w ，代表在 x 號節點和 y 號節點之間有一條道路，通過需要花費 w 個單位的能量。所有道路都可以雙向通行。
輸出格式
輸出一個整數，代表采集所有節點的金屬所需要的最少能量。
樣例輸入
6 1 3
1 2 1
2 3 1
2 4 1000
2 5 1000
1 6 1000
樣例輸出
3004
樣例說明
所有機器人在 1 號節點著陸。
第一個機器人的行走路徑為 1->6 ，在 6 號節點返回地球，花費能量為1000。
第二個機器人的行走路徑為 1->2->3->2->4 ，在 4 號節點返回地球，花費能量為1003。
第一個機器人的行走路徑為 1->2->5 ，在 5 號節點返回地球，花費能量為1001。
數據規模與約定
本題有10個測試點。
對于測試點 1~2 ， n <= 10 ， k <= 5 。
對于測試點 3 ， n <= 100000 ， k = 1 。
對于測試點 4 ， n <= 1000 ， k = 2 。
對于測試點 5~6 ， n <= 1000 ， k <= 10 。
對于測試點 7~10 ， n <= 100000 ， k <= 10 。
道路的能量 w 均為不超過 1000 的正整數。
72、矩陣翻轉（枚舉 貪心）
問題描述
Ciel有一個NN的矩陣，每個格子里都有一個整數。
N是一個奇數，設X = (N+1)/2。Ciel每次都可以做這樣的一次操作：他從矩陣選出一個XX的子矩陣，并將這個子矩陣中的所有整數都乘以-1。
現在問你經過一些操作之后，矩陣中所有數的和最大可以為多少。
輸入格式
第一行為一個正整數N。
接下來N行每行有N個整數，表示初始矩陣中的數字。每個數的絕對值不超過1000。
輸出格式
輸出一個整數，表示操作后矩陣中所有數之和的最大值。
樣例輸入
3
-1 -1 1
-1 1 -1
1 -1 -1
樣例輸出
9
數據規模與約定
1 <= N <= 33，且N為奇數。
73、兩條直線（排序）
問題描述
給定平面上n個點。
求兩條直線，這兩條直線互相垂直，而且它們與x軸的夾角為45度，并且n個點中離這兩條直線的曼哈頓距離的最大值最小。
兩點之間的曼哈頓距離定義為橫坐標的差的絕對值與縱坐標的差的絕對值之和，一個點到兩條直線的曼哈頓距離是指該點到兩條直線上的所有點的曼哈頓距離中的最小值。
輸入格式
第一行包含一個數n。
接下來n行，每行包含兩個整數，表示n個點的坐標（橫縱坐標的絕對值小于109）。
輸出格式
輸出一個值，表示最小的最大曼哈頓距離的值，保留一位小數。
樣例輸入
4
1 0
0 1
2 1
1 2
樣例輸出
1.0
數據規模與約定
對于30%的數據，n<=100。
對于另外30%的數據，坐標范的絕對值小于100。
對于100%的數據，n<=105。
74、冒泡排序計數（組合）
考慮冒泡排序的一種實現。
bubble-sort (A[], n)
round = 0
while A is not sortedround := round + 1
for i := 1 to n - 1if (A[i] > A[i + 1])
swap(A[i], A[i + 1])
求1 … n的排列中，有多少個排列使得A被掃描了K遍，亦即算法結束時round == K。
答案模20100713輸出。
輸入格式
輸入包含多組數據。每組數據為一行兩個整數N，K。
輸出格式
對每組數據，輸出一行一個整數表示答案。
樣例輸入
3
3 0
3 1
3 2
樣例輸出
1
3
2
數據規模和約定
T <= 10 ^ 5。
1 <= K < N < 10 ^ 6。
75、子集選取（組合）
問題描述
一個有N個元素的集合有2N個不同子集（包含空集），現在要在這2N個集合中取出若干集合（至少一個），使得它們的交集的元素個數為K，求取法的方案數，答案模1000000007。
輸入格式
輸入一行兩個整數N，K。
輸出格式
輸出一個整數表示答案。
樣例輸入
3 2
樣例輸出
6
數據規模和約定
1 <= K <= N <= 10 ^ 6。
76、郵票面值設計（搜索）
問題描述
給定一個信封，最多只允許粘貼N張郵票，計算在給定K（N+K≤13）種郵票的情況下（假定所有的郵票數量都足夠），如何設計郵票的面值，能得到最大值MAX，使在1～MAX之間的每一個郵資值都能得到。
例如，N=3，K=2，如果面值分別為1分、4分，則在1分～6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）；如果面值分別為1分、3分，則在1分～7分之間的每一個郵資值都能得到。可以驗證當N=3，K=2時，7分就是可以得到的連續的郵資最大值，所以MAX=7，面值分別為1分、3分。
輸入格式
一行，兩個數N、K
輸出格式
兩行，第一行升序輸出設計的郵票面值，第二行輸出“MAX=xx”（不含引號），其中xx為所求的能得到的連續郵資最大值。
樣例輸入
3 2
樣例輸出
1 3
MAX=7
77、公式求值（組合數學）
問題描述
輸入n, m, k，輸出下面公式的值。
其中C_n^m是組合數，表示在n個人的集合中選出m個人組成一個集合的方案數。組合數的計算公式如下。
輸入格式
輸入的第一行包含一個整數n；第二行包含一個整數m，第三行包含一個整數k。
輸出格式
計算上面公式的值，由于答案非常大，請輸出這個值除以999101的余數。
樣例輸入
3
1
3
樣例輸出
162
樣例輸入
20
10
10
樣例輸出
359316
數據規模和約定
對于10%的數據，n≤10，k≤3；
對于20%的數據，n≤20，k≤3；
對于30%的數據，n≤1000，k≤5；
對于40%的數據，n≤10^7，k≤10；
對于60%的數據，n≤10^15，k ≤100；
對于70%的數據，n≤10^100，k≤200；
對于80%的數據，n≤10^500，k ≤500；
對于100%的數據，n在十進制下不超過1000位，即1≤n<10^1000，1≤k≤1000，同時0≤m≤n，k≤n。
提示
999101是一個質數；
當n位數比較多時，絕大多數情況下答案都是0，但評測的時候會選取一些答案不是0的數據；
78、九宮重排（搜索）
問題描述
如下面第一個圖的九宮格中，放著 1~8 的數字卡片，還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經過若干次移動，可以形成第二個圖所示的局面。
我們把第一個圖的局面記為：12345678.
把第二個圖的局面記為：123.46758
顯然是按從上到下，從左到右的順序記錄數字，空格記為句點。
本題目的任務是已知九宮的初態和終態，求最少經過多少步的移動可以到達。如果無論多少步都無法到達，則輸出-1。
輸入格式
輸入第一行包含九宮的初態，第二行包含九宮的終態。
輸出格式
輸出最少的步數，如果不存在方案，則輸出-1。
樣例輸入
12345678.
123.46758
樣例輸出
3
樣例輸入
13524678.
46758123.
樣例輸出
22
79、車輪軸跡（計算幾何）
問題描述
棟棟每天騎自行車回家需要經過一條狹長的林蔭道。道路由于年久失修，變得非常不平整。雖然棟棟每次都很顛簸，但他仍把騎車經過林蔭道當成一種樂趣。
由于顛簸，棟棟騎車回家的路徑是一條上下起伏的曲線，棟棟想知道，他回家的這條曲線的長度究竟是多長呢？更準確的，棟棟想知道從林蔭道的起點到林蔭道的終點，他的車前輪的軸（圓心）經過的路徑的長度。
棟棟對路面進行了測量。他把道路簡化成一條條長短不等的直線段，這些直線段首尾相連，且位于同一平面內。并在該平面內建立了一個直角坐標系，把所有線段的端點坐標都計算好。
假設棟棟的自行車在行進的過程中前輪一直是貼著路面前進的。
上圖給出了一個簡單的路面的例子，其中藍色實線為路面，紅色虛線為車輪軸經過的路徑。在這個例子中，棟棟的前輪軸從A點出發，水平走到B點，然后繞著地面的F點到C點（繞出一個圓弧），再沿直線下坡到D點，最后水平走到E點，在這個圖中地面的坐標依次為：(0, 0), (2, 0), (4, -1), (6, -1)，前輪半徑為1.50，前輪軸前進的距離依次為：
AB=2.0000；弧長BC=0.6955；CD=1.8820；DE=1.6459。
總長度為6.2233。
下圖給出了一個較為復雜的路面的例子，在這個例子中，車輪在第一個下坡還沒下完時（D點）就開始上坡了，之后在坡的頂點要從E繞一個較大的圓弧到F點。這個圖中前輪的半徑為1，每一段的長度依次為：
AB=3.0000；弧長BC=0.9828；CD=1.1913；DE=2.6848；弧長EF=2.6224； FG=2.4415；GH=2.2792。
總長度為15.2021。
現在給出了車輪的半徑和路面的描述，請求出車輪軸軌跡的總長度。
輸入格式
輸入的第一行包含一個整數n和一個實數r，用一個空格分隔，表示描述路面的坐標點數和車輪的半徑。
接下來n行，每個包含兩個實數，其中第i行的兩個實數x[i], y[i]表示描述路面的第i個點的坐標。
路面定義為所有路面坐標點順次連接起來的折線。給定的路面的一定滿足以下性質：
*第一個坐標點一定是(0, 0)；
*第一個點和第二個點的縱坐標相同；
*倒數第一個點和倒數第二個點的縱坐標相同；
*第一個點和第二個點的距離不少于車輪半徑；
*倒數第一個點和倒數第二個點的的距離不少于車輪半徑；
后一個坐標點的橫坐標大于前一個坐標點的橫坐標，即對于所有的i，x[i+1]>x[i]。
輸出格式
輸出一個實數，四舍五入保留兩個小數，表示車輪軸經過的總長度。
你的結果必須和參考答案一模一樣才能得分。數據保證答案精確值的小數點后第三位不是4或5。
樣例輸入
4 1.50
0.00 0.00
2.00 0.00
4.00 -1.00
6.00 -1.00
樣例輸出
6.22
樣例說明
這個樣例對應第一個圖。
樣例輸入
6 1.00
0.00 0.00
3.00 0.00
5.00 -3.00
6.00 2.00
7.00 -1.00
10.00 -1.00
樣例輸出
15.20
樣例說明
這個樣例對應第二個圖
數據規模和約定
對于20%的數據，n=4；
對于40%的數據，n≤10；
對于100%的數據，4≤n≤100，0.5≤r≤20.0，x[i] ≤2000.0，-2000.0≤y[i] ≤2000.0。
80、約數倍數選卡片（博弈論）
問題描述
閑暇時，福爾摩斯和華生玩一個游戲：
在N張卡片上寫有N個整數。兩人輪流拿走一張卡片。要求下一個人拿的數字一定是前一個人拿的數字的約數或倍數。例如，某次福爾摩斯拿走的卡片上寫著數字“6”，則接下來華生可以拿的數字包括：
1，2，3, 6，12，18，24 …
當輪到某一方拿卡片時，沒有滿足要求的卡片可選，則該方為輸方。
請你利用計算機的優勢計算一下，在已知所有卡片上的數字和可選哪些數字的條件下，怎樣選擇才能保證必勝！
當選多個數字都可以必勝時，輸出其中最小的數字。如果無論如何都會輸，則輸出-1。
輸入格式
輸入數據為2行。第一行是若干空格分開的整數（每個整數介于1~100間），表示當前剩余的所有卡片。
第二行也是若干空格分開的整數，表示可以選的數字。當然，第二行的數字必須完全包含在第一行的數字中。
輸出格式
程序則輸出必勝的招法！！
樣例輸入
2 3 6
3 6
樣例輸出
3
樣例輸入
1 2 2 3 3 4 5
3 4 5
樣例輸出
4
81、農場陽光（計算幾何）
問題描述
X星球十分特殊，它的自轉速度與公轉速度相同，所以陽光總是以固定的角度照射。
最近，X星球為發展星際旅游業，把空間位置出租給Y國游客來曬太陽。每個租位是漂浮在空中的圓盤形彩云（圓盤與地面平行）。當然，這會遮擋住部分陽光，被遮擋的土地植物無法生長。
本題的任務是計算某個農場宜于作物生長的土地面積有多大。
輸入格式
輸入數據的第一行包含兩個整數a, b，表示某農場的長和寬分別是a和b，此時，該農場的范圍是由坐標(0, 0, 0), (a, 0, 0), (a, b, 0), (0, b, 0)圍成的矩形區域。
第二行包含一個實數g，表示陽光照射的角度。簡單起見，我們假設陽光光線是垂直于農場的寬的，此時正好和農場的長的夾角是g度，此時，空間中的一點(x, y, z)在地面的投影點應該是(x + z * ctg(g度), y, 0)，其中ctg(g度)表示g度對應的余切值。
第三行包含一個非負整數n，表示空中租位個數。
接下來 n 行，描述每個租位。其中第i行包含4個整數xi, yi, zi, ri，表示第i個租位彩云的圓心在(xi, yi, zi)位置，圓半徑為ri。
輸出格式
要求輸出一個實數，四舍五入保留兩位有效數字，表示農場里能長莊稼的土地的面積。
樣例輸入
10 10
90.0
1
5 5 10 5
樣例輸出
21.46
樣例輸入
8 8
90.0
1
4 4 10 5
樣例輸出
1.81
樣例輸入
20 10
45.0
2
5 0 5 5
8 6 14 6
樣例輸出
130.15
82、格子刷油漆（動態規劃）
問題描述
X國的一段古城墻的頂端可以看成 2N個格子組成的矩形（如下圖所示），現需要把這些格子刷上保護漆。
你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數），但不能移動到較遠的格子（因為油漆未干不能踩！）
比如：a d b c e f 就是合格的刷漆順序。
c e f d a b 是另一種合適的方案。
當已知 N 時，求總的方案數。當N較大時，結果會迅速增大，請把結果對 1000000007 (十億零七) 取模。
輸入格式
輸入數據為一個正整數（不大于1000）
輸出格式
輸出數據為一個正整數。
樣例輸入
2
樣例輸出
24
樣例輸入
3
樣例輸出
96
樣例輸入
22
樣例輸出
359635897
83、高僧斗法（博弈論）
問題描述
古時喪葬活動中經常請高僧做法事。儀式結束后，有時會有“高僧斗法”的趣味節目，以舒緩壓抑的氣氛。
節目大略步驟為：先用糧食（一般是稻米）在地上“畫”出若干級臺階（表示N級浮屠）。又有若干小和尚隨機地“站”在某個臺階上。最高一級臺階必須站人，其它任意。(如圖1所示)
兩位參加游戲的法師分別指揮某個小和尚向上走任意多級的臺階，但會被站在高級臺階上的小和尚阻擋，不能越過。兩個小和尚也不能站在同一臺階，也不能向低級臺階移動。
兩法師輪流發出指令，最后所有小和尚必然會都擠在高段臺階，再也不能向上移動。輪到哪個法師指揮時無法繼續移動，則游戲結束，該法師認輸。
對于已知的臺階數和小和尚的分布位置，請你計算先發指令的法師該如何決策才能保證勝出。
輸入格式
輸入數據為一行用空格分開的N個整數，表示小和尚的位置。臺階序號從1算起，所以最后一個小和尚的位置即是臺階的總數。（N<100, 臺階總數<1000）
輸出格式
輸出為一行用空格分開的兩個整數: A B, 表示把A位置的小和尚移動到B位置。若有多個解，輸出A值較小的解，若無解則輸出-1。
樣例輸入
1 5 9
樣例輸出
1 4
樣例輸入
1 5 8 10
樣例輸出
1 3
84、網絡尋路（構圖）
問題描述
X 國的一個網絡使用若干條線路連接若干個節點。節點間的通信是雙向的。某重要數據包，為了安全起見，必須恰好被轉發兩次到達目的地。該包可能在任意一個節點產生，我們需要知道該網絡中一共有多少種不同的轉發路徑。
源地址和目標地址可以相同，但中間節點必須不同。
如下圖所示的網絡。
1 -> 2 -> 3 -> 1 是允許的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
輸入格式
輸入數據的第一行為兩個整數N M，分別表示節點個數和連接線路的條數(1<=N<=10000; 0<=M<=100000)。
接下去有M行，每行為兩個整數 u 和 v，表示節點u 和 v 聯通(1<=u,v<=N , u!=v)。
輸入數據保證任意兩點最多只有一條邊連接，并且沒有自己連自己的邊，即不存在重邊和自環。
輸出格式
輸出一個整數，表示滿足要求的路徑條數。
樣例輸入1
3 3
1 2
2 3
1 3
樣例輸出1
6
樣例輸入2
4 4
1 2
2 3
3 1
1 4
樣例輸出2
10
85、危險系數（割點）
問題描述
抗日戰爭時期，冀中平原的地道戰曾發揮重要作用。
地道的多個站點間有通道連接，形成了龐大的網絡。但也有隱患，當敵人發現了某個站點后，其它站點間可能因此會失去聯系。
我們來定義一個危險系數DF(x,y)：
對于兩個站點x和y (x != y), 如果能找到一個站點z，當z被敵人破壞后，x和y不連通，那么我們稱z為關于x,y的關鍵點。相應的，對于任意一對站點x和y，危險系數DF(x,y)就表示為這兩點之間的關鍵點個數。
本題的任務是：已知網絡結構，求兩站點之間的危險系數。
輸入格式
輸入數據第一行包含2個整數n(2 <= n <= 1000), m(0 <= m <= 2000),分別代表站點數，通道數；
接下來m行，每行兩個整數 u,v (1 <= u, v <= n; u != v)代表一條通道；
最后1行，兩個數u,v，代表詢問兩點之間的危險系數DF(u, v)。
輸出格式
一個整數，如果詢問的兩點不連通則輸出-1.
樣例輸入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
樣例輸出
2
86、橫向打印二叉樹（排序二叉樹）
問題描述
二叉樹可以用于排序。其原理很簡單：對于一個排序二叉樹添加新節點時，先與根節點比較，若小則交給左子樹繼續處理，否則交給右子樹。
當遇到空子樹時，則把該節點放入那個位置。
比如，10 8 5 7 12 4 的輸入順序，應該建成二叉樹如下圖所示，其中.表示空白。
…|-12
10-|
…|-8-|
…|…|-7
…|-5-|
…|-4
本題目要求：根據已知的數字，建立排序二叉樹，并在標準輸出中橫向打印該二叉樹。
輸入格式
輸入數據為一行空格分開的N個整數。 N<100，每個數字不超過10000。
輸入數據中沒有重復的數字。
輸出格式
輸出該排序二叉樹的橫向表示。為了便于評卷程序比對空格的數目，請把空格用句點代替：
樣例輸入1
10 5 20
樣例輸出1
…|-20
10-|
…|-5
樣例輸入2
5 10 20 8 4 7
樣例輸出2
…|-20
…|-10-|
…|…|-8-|
…|…|-7
5-|
…|-4
87、幸運數（堆）
問題描述
幸運數是波蘭數學家烏拉姆命名的。它采用與生成素數類似的“篩法”生成
。
首先從1開始寫出自然數1,2,3,4,5,6,…
1 就是第一個幸運數。
我們從2這個數開始。把所有序號能被2整除的項刪除，變為：
1 _ 3 _ 5 _ 7 _ 9 …
把它們縮緊，重新記序，為：
1 3 5 7 9 … 。這時，3為第2個幸運數，然后把所有能被3整除的序號位置的數刪去。注意，是序號位置，不是那個數本身能否被3整除!! 刪除的應該是5，11, 17, …
此時7為第3個幸運數，然后再刪去序號位置能被7整除的(19,39,…)
最后剩下的序列類似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …
輸入格式
輸入兩個正整數m n, 用空格分開 (m < n < 10001000)
輸出格式
程序輸出 位于m和n之間的幸運數的個數（不包含m和n）。
樣例輸入1
1 20
樣例輸出1
5
樣例輸入2
30 69
樣例輸出2
8
88、大臣的旅費（深度優先遍歷）
問題描述
很久以前，T王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接首都和王國內的各大城市。
為節省經費，T國的大臣們經過思考，制定了一套優秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達。同時，如果不重復經過大城市，從首都到達每個大城市的方案都是唯一的。
J是T國重要大臣，他巡查于各大城市之間，體察民情。所以，從一個城市馬不停蹄地到另一個城市成了J最常做的事情。他有一個錢袋，用于存放往來城市間的路費。
聰明的J發現，如果不在某個城市停下來修整，在連續行進過程中，他所花的路費與他已走過的距離有關，在走第x千米到第x+1千米這一千米中（x是整數），他花費的路費是x+10這么多。也就是說走1千米花費11，走2千米要花費23。
J大臣想知道：他從某一個城市出發，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？
輸入格式
輸入的第一行包含一個整數n，表示包括首都在內的T王國的城市數
城市從1開始依次編號，1號城市為首都。
接下來n-1行，描述T國的高速路（T國的高速路一定是n-1條）
每行三個整數Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。
輸出格式
輸出一個整數，表示大臣J最多花費的路費是多少。
樣例輸入1
5
1 2 2
1 3 1
2 4 5
2 5 4
樣例輸出1
135
輸出格式
大臣J從城市4到城市5要花費135的路費。
89、買不到的數目（數論 動態規劃）
問題描述
小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。
小朋友來買糖的時候，他就用這兩種包裝來組合。當然有些糖果數目是無法組合出來的，比如要買 10 顆糖。
你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數量是17。大于17的任何數字都可以用4和7組合出來。
本題的要求就是在已知兩個包裝的數量時，求最大不能組合出的數字。
輸入格式
兩個正整數，表示每種包裝中糖的顆數(都不多于1000)
輸出格式
一個正整數，表示最大不能買到的糖數
樣例輸入1
4 7
樣例輸出1
17
樣例輸入2
3 5
樣例輸出2
7
90、連號區間數（并查集）
問題描述
小明這些天一直在思考這樣一個奇怪而有趣的問題：
在1~N的某個全排列中有多少個連號區間呢？這里所說的連號區間的定義是：
如果區間[L, R] 里的所有元素（即此排列的第L個到第R個元素）遞增排序后能得到一個長度為R-L+1的“連續”數列，則稱這個區間連號區間。
當N很小的時候，小明可以很快地算出答案，但是當N變大的時候，問題就不是那么簡單了，現在小明需要你的幫助。
輸入格式
第一行是一個正整數N (1 <= N <= 50000), 表示全排列的規模。
第二行是N個不同的數字Pi(1 <= Pi <= N)， 表示這N個數字的某一全排列。
輸出格式
輸出一個整數，表示不同連號區間的數目。
樣例輸入1
4
3 2 4 1
樣例輸出1
7
樣例輸入2
5
3 4 2 5 1
樣例輸出2
9
91、翻硬幣（貪心）
問題描述
小明正在玩一個“翻硬幣”的游戲。
桌上放著排成一排的若干硬幣。我們用 * 表示正面，用 o 表示反面（是小寫字母，不是零）。
比如，可能情形是：oooooo
如果同時翻轉左邊的兩個硬幣，則變為：oooo***oooo
現在小明的問題是：如果已知了初始狀態和要達到的目標狀態，每次只能同時翻轉相鄰的兩個硬幣,那么對特定的局面，最少要翻動多少次呢？
我們約定：把翻動相鄰的兩個硬幣叫做一步操作，那么要求：
輸入格式
兩行等長的字符串，分別表示初始狀態和要達到的目標狀態。每行的長度<1000
輸出格式
一個整數，表示最小操作步數。
樣例輸入1
oo
樣例輸出1
5
92、錯誤票據（排序）
問題描述
某涉密單位下發了某種票據，并要在年終全部收回。
每張票據有唯一的ID號。全年所有票據的ID號是連續的，但ID的開始數碼是隨機選定的。
因為工作人員疏忽，在錄入ID號的時候發生了一處錯誤，造成了某個ID斷號，另外一個ID重號。
你的任務是通過編程，找出斷號的ID和重號的ID。
假設斷號不可能發生在最大和最小號。
輸入格式
要求程序首先輸入一個整數N(N<100)表示后面數據行數。
接著讀入N行數據。
每行數據長度不等，是用空格分開的若干個（不大于100個）正整數（不大于100000），請注意行內和行末可能有多余的空格，你的程序需要能處理這些空格。
每個整數代表一個ID號。
輸出格式
要求程序輸出1行，含兩個整數m n，用空格分隔。
其中，m表示斷號ID，n表示重號ID
樣例輸入1
2
5 6 8 11 9?
10 12 9
樣例輸出1
7 9
93、剪格子（搜索）
問題描述
如下圖所示，3 x 3 的格子中填寫了一些整數。
±-–±-+
|10 1|52|
±-***–+
|20|30 1|
******–+
| 1| 2| 3|
±-±-±-+
我們沿著圖中的星號線剪開，得到兩個部分，每個部分的數字和都是60。
本題的要求就是請你編程判定：對給定的m x n 的格子中的整數，是否可以分割為兩個部分，使得這兩個區域的數字和相等。
如果存在多種解答，請輸出包含左上角格子的那個區域包含的格子的最小數目。
如果無法分割，則輸出 0。
輸入格式
程序先讀入兩個整數 m n 用空格分割 (m,n<10)。
表示表格的寬度和高度。
接下來是n行，每行m個正整數，用空格分開。每個整數不大于10000。
輸出格式
輸出一個整數，表示在所有解中，包含左上角的分割區可能包含的最小的格子數目。
樣例輸入1
3 3
10 1 52
20 30 1
1 2 3
樣例輸出1
3
樣例輸入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
樣例輸出2
10
94、帶分數（搜索）
問題描述
100 可以表示為帶分數的形式：100 = 3 + 69258 / 714。
還可以表示為：100 = 82 + 3546 / 197。
注意特征：帶分數中，數字1~9分別出現且只出現一次（不包含0）。
類似這樣的帶分數，100 有 11 種表示法。
輸入格式
從標準輸入讀入一個正整數N (N<10001000)
輸出格式
程序輸出該數字用數碼1~9不重復不遺漏地組成帶分數表示的全部種數。
注意：不要求輸出每個表示，只統計有多少表示法！
樣例輸入1
100
樣例輸出1
11
樣例輸入2
105
樣例輸出2
6
95、打印十字圖（文字圖形）
問題描述
小明為某機構設計了一個十字型的徽標（并非紅十字會啊），如下所示：
…$$$$$$$$$$$KaTeX parse error: Can't use function '$' in math mode at position 6: .. ..$?...........$.. . . .$$$$$$ . . .$
. . . ... ...… . . . ... ...
. . . . . .$ . . . . . .
. . .… . . . ... ...… . . .
. . ..$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?. . . ..$
. . .. . . . ... ...… . . ..$
. . .. . . .$$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?.$.$ $.$.$...$.… . . ..$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?.$ $.$...$...$.… . . .$$ . . . . . .
. . . ... ...… . . . ... ...
$ . . .$$$$$ . . .$
… . . . . . . . . . . . ........... ...........…
…$$$$$$$$$$$ . . 對方同時也需要在電腦 d o s 窗口中以字符的形式輸出該標志，并能任意控制層數。輸入格式一個正整數 n ( n < 30 ) 表示要求打印圖形的層數。輸出格式對應包圍層數的該標志。樣例輸入 11 樣例輸出 1.. .. 對方同時也需要在電腦dos窗口中以字符的形式輸出該標志，并能任意控制層數。 輸入格式 一個正整數 n (n<30) 表示要求打印圖形的層數。 輸出格式 對應包圍層數的該標志。 樣例輸入1 1 樣例輸出1 .. ..對方同時也需要在電腦dos窗口中以字符的形式輸出該標志，并能任意控制層數。輸入格式一個正整數n(n<30)表示要求打印圖形的層數。輸出格式對應包圍層數的該標志。樣例輸入11樣例輸出1..$KaTeX parse error: Can't use function '$' in math mode at position 6: .. ..$?...$.. . . ..$KaTeX parse error: Can't use function '$' in math mode at position 2: $?...$...$ $.$KaTeX parse error: Can't use function '$' in math mode at position 2: .$? $...$...$ . . ..$KaTeX parse error: Can't use function '$' in math mode at position 4: ..$?...$.. ..$ . . 樣例輸入 23 樣例輸出 2.. .. 樣例輸入2 3 樣例輸出2 .. ..樣例輸入23樣例輸出2..$$$$$$$$$KaTeX parse error: Can't use function '$' in math mode at position 6: .. ..$?...........$.. . . .$$$$$$ . . .$
. . . ... ...… . . . ... ...
. . . . . .$ . . . . . .
. . .… . . . ... ...… . . .
. . ..$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?. . . ..$
. . .. . . . ... ...… . . ..$
. . .. . . .$$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?.$.$ $.$.$...$.… . . ..$KaTeX parse error: Can't use function '$' in math mode at position 2: .$?.$ $.$...$...$.… . . .$$ . . . . . .
. . . ... ...… . . . ... ...
$ . . .$$$$$ . . .$
… . . . . . . . . . . . ........... ...........…
…$$$$$$$$$$$$$…
提示
請仔細觀察樣例，尤其要注意句點的數量和輸出位置。
96、核桃的數量（最小公倍數）
問題描述
小張是軟件項目經理，他帶領3個開發組。工期緊，今天都在加班呢。為鼓舞士氣，小張打算給每個組發一袋核桃（據傳言能補腦）。他的要求是：
- 各組的核桃數量必須相同
- 各組內必須能平分核桃（當然是不能打碎的）
- 盡量提供滿足1,2條件的最小數量（節約鬧革命嘛）
輸入格式
輸入包含三個正整數a, b, c，表示每個組正在加班的人數，用空格分開（a,b,c<30）
輸出格式
輸出一個正整數，表示每袋核桃的數量。
樣例輸入1
2 4 5
樣例輸出1
20
樣例輸入2
3 1 1
樣例輸出2
3
、date_add()、datediff() 詳解-文中有示例幫助理解)
)
