這次的題總體上相對前三次偏簡單。由於實力有限，就分析前四題。
試題編號： 201503-1
試題名稱： 圖像旋轉
時間限制： 5.0s
內存限制： 256.0MB
問題描述：
問題描述
旋轉是圖像處理的基本操作，在這個問題中，你需要將一個圖像逆時針旋轉90度。
計算機中的圖像表示可以用一個矩陣來表示，為了旋轉一個圖像，只需要將對應的矩陣旋轉即可。
輸入格式
輸入的第一行包含兩個整數n, m，分別表示圖像矩陣的行數和列數。
接下來n行每行包含m個整數，表示輸入的圖像。
輸出格式
輸出m行，每行包含n個整數，表示原始矩陣逆時針旋轉90度後的矩陣。
樣例輸入
2 3
1 5 3
3 2 4
樣例輸出
3 4
5 2
1 3
評測用例規模與約定
1 ≤ n, m ≤ 1,000，矩陣中的數都是不超過1000的非負整數。
實(dou)力(bi)分析：逆時針旋轉90°就是將矩陣的第i行變為第i列，第j行變為第m+1-j列，分析出來就沒什麼問題了。其次很重要的就是輸出格式，每行的最後一個數字之後是沒有空格的。簽到題100分到手。
本人源碼：
試題名稱： 數字排序
時間限制： 1.0s
內存限制： 256.0MB
問題描述：
問題描述
給定n個整數，請統計出每個整數出現的次數，按出現次數從多到少的順序輸出。
輸入格式
輸入的第一行包含一個整數n，表示給定數字的個數。
第二行包含n個整數，相鄰的整數之間用一個空格分隔，表示所給定的整數。
輸出格式
輸出多行，每行包含兩個整數，分別表示一個給定的整數和它出現的次數。按出現次數遞減的順序輸出。如果兩個整數出現的次數一樣多，則先輸出值較小的，然後輸出值較大的。
樣例輸入
12
5 2 3 3 1 3 4 2 5 2 3 5
樣例輸出
3 4
2 3
5 3
1 1
4 1
評測用例規模與約定
1 ≤ n ≤ 1000，給出的數都是不超過1000的非負整數。
實(dou)力(bi)分析：這題主要是結構體的二級排序吧（反正我是這樣做的），用好algorithm裡的sort()，把過程模擬下就行了。由於給出的數是非負整數，所以0也要考慮進去，並且輸入的數不一定小於n，所以在排序時應該sort(a, a+1005, cmp)。
本人源碼：
試題編號：
201503-3
試題名稱： 節日
時間限制： 1.0s
內存限制： 256.0MB
問題描述：
問題描述
有一類節日的日期並不是固定的，而是以“a月的第b個星期c”的形式定下來的，比如說母親節就定為每年的五月的第二個星期日。
現在，給你a，b，c和y1, y2(1850 ≤ y1, y2 ≤ 2050)，希望你輸出從公元y1年到公元y2年間的每年的a月的第b個星期c的日期。
提示：關於閏年的規則：年份是400的整數倍時是閏年，否則年份是4的倍數並且不是100的倍數時是閏年，其他年份都不是閏年。例如1900年就不是閏年，而2000年是閏年。
為了方便你推算，已知1850年1月1日是星期二。
輸入格式
輸入包含恰好一行，有五個整數a, b, c, y1, y2。其中c=1, 2, ……, 6, 7分別表示星期一、二、……、六、日。
輸出格式
對於y1和y2之間的每一個年份，包括y1和y2，按照年份從小到大的順序輸出一行。
如果該年的a月第b個星期c確實存在，則以"yyyy/mm/dd"的格式輸出，即輸出四位數的年份，兩位數的月份，兩位數的日期，中間用斜槓“/”分隔，位數不足時前補零。
如果該年的a月第b個星期c並不存在，則輸出"none"（不包含雙引號)。
樣例輸入
5 2 7 2014 2015
樣例輸出
2014/05/11
2015/05/10
評測用例規模與約定
所有評測用例都滿足：1 ≤ a ≤ 12，1 ≤ b ≤ 5，1 ≤ c ≤ 7，1850 ≤ y1, y2 ≤ 2050。
實(dou)力(bi)分析：有點麻煩的模擬題。更像小學的奧數題，總之把這題邏輯思路搞清楚了，一般過了樣例就可以拿滿分了。（l = min(y1), r = max(y2)也許純屬我的強迫症吧。。畢竟已經說了y1到y2年之間）
本人源碼：
試題編號： 201503-4
試題名稱： 網絡延時
時間限制： 1.0s
內存限制： 256.0MB
問題描述：
問題描述
給定一個公司的網絡，由n台交換機和m台終端電腦組成，交換機與交換機、交換機與電腦之間使用網絡連接。交換機按層級設置，編號為1的交換機為根交換
機，層級為1。其他的交換機都連接到一台比自己上一層的交換機上，其層級為對應交換機的層級加1。所有的終端電腦都直接連接到交換機上。
當信息在電腦、交換機之間傳遞時，每一步只能通過自己傳遞到自己所連接的另一台電腦或交換機。請問，電腦與電腦之間傳遞消息、或者電腦與交換機之間傳遞消息、或者交換機與交換機之間傳遞消息最多需要多少步。
輸入格式
輸入的第一行包含兩個整數n, m，分別表示交換機的台數和終端電腦的台數。
第二行包含n - 1個整數，分別表示第2、3、……、n台交換機所連接的比自己上一層的交換機的編號。第i台交換機所連接的上一層的交換機編號一定比自己的編號小。
第三行包含m個整數，分別表示第1、2、……、m台終端電腦所連接的交換機的編號。
輸出格式
輸出一個整數，表示消息傳遞最多需要的步數。
樣例輸入
4 2
1 1 3
2 1
樣例輸出
4
樣例說明
樣例的網絡連接模式如下，其中圓圈表示交換機，方框表示電腦：
其中電腦1與交換機4之間的消息傳遞花費的時間最長，為4個單位時間。
樣例輸入
4 4
1 2 2
3 4 4 4
樣例輸出
4
樣例說明
樣例的網絡連接模式如下：
其中電腦1與電腦4之間的消息傳遞花費的時間最長，為4個單位時間。
評測用例規模與約定
前30%的評測用例滿足：n ≤ 5, m ≤ 5。
前50%的評測用例滿足：n ≤ 20, m ≤ 20。
前70%的評測用例滿足：n ≤ 100, m ≤ 100。
所有評測用例都滿足：1 ≤ n ≤ 10000，1 ≤ m ≤ 10000。
實(dou)力(bi)分析：圖有
n+m個頂點，n+m-1條邊，頂點之間兩兩連通，很容易看出來這是一棵樹。問題抽象後就是求樹中相距最遠的兩個葉子結點間的距離，這個距離又叫做樹的直
徑。那天剛好帶了求樹的直徑的模版過去，所以沒動多少腦子就寫完了。不過這題只拿了70分，模版的時間復雜度O(|V|+|E|)應該沒什麼問題，然後就
想起了考試那天使用了cin來輸入，在最後30%比較大輸入量的評測用例中超時了，欲哭無淚，還是對大輸入量不夠敏感。模版的思路就是先dfs找出距離根
結點0最遠的葉子結點u，然後再對u一次dfs找出距離u最遠的葉子結點。
本人源碼：
試題編號： 201503-5
試題名稱： 最小花費
時間限制： 4.0s
內存限制： 256.0MB
問題描述：
問題描述
C國共有n個城市。有n-1條雙向道路，每條道路連接兩個城市，任意兩個城市之間能互相到達。小R來到C國旅行，他共規劃了m條旅行的路線，第i條旅
行路線的起點是si，終點是ti。在旅行過程中，小R每行走一單位長度的路需要吃一單位的食物。C國的食物只能在各個城市中買到，而且不同城市的食物價格
可能不同。
然而，小R不希望在旅行中為了購買較低價的糧食而繞遠路，因此他總會選擇最近的路走。現在，請你計算小R規劃的每條旅行路線的最小花費是多少。
輸入格式
第一行包含2個整數n和m。
第二行包含n個整數。第i個整數wi表示城市i的食物價格。
接下來n-1行，每行包括3個整數u, v, e，表示城市u和城市v之間有一條長為e的雙向道路。
接下來m行，每行包含2個整數si和ti，分別表示一條旅行路線的起點和終點。
輸出格式
輸出m行，分別代表每一條旅行方案的最小花費。
樣例輸入
6 4
1 7 3 2 5 6
1 2 4
1 3 5
2 4 1
3 5 2
3 6 1
2 5
4 6
6 4
5 6
樣例輸出
35
16
26
13
樣例說明
對於第一條路線，小R會經過2->1->3->5。其中在城市2處以7的價格購買4單位糧食，到城市1時全部吃完，並用1的價格購買7單位糧食，然後到達終點。
評測用例規模與約定
前10%的評測用例滿足：n, m ≤ 20, wi ≤ 20；
前30%的評測用例滿足：n, m ≤ 200；
另有40%的評測用例滿足：一個城市至多與其它兩個城市相連。
所有評測用例都滿足：1 ≤ n, m ≤ 105，1 ≤ wi ≤ 106，1 ≤ e ≤ 10000。
實(dou)力(bi)分(mai)析(meng)：看到時間限制是4s的那一刻對於做這道題我是拒絕的。不過前30%數據范圍比較小，說說思路吧。先從si開始dfs找到通向ti的所有通路，然後dp找出最小花費。
事實證明寫題解是件體力活，寫完千萬不要忘記保存，否則會重寫一遍。。。
最後，吹一年的370鎮樓。
