算法訓練 關聯矩陣  
時間限制：1.0s   內存限制：512.0MB
   
問題描述
　　有一個n個結點m條邊的有向圖，請輸出他的關聯矩陣。
輸入格式
　　第一行兩個整數n、m，表示圖中結點和邊的數目。n<=100,m<=1000。
　　接下來m行，每行兩個整數a、b，表示圖中有(a,b)邊。
　　注意圖中可能含有重邊，但不會有自環。
輸出格式
　　輸出該圖的關聯矩陣，注意請勿改變邊和結點的順序。
樣例輸入
5 9
1 2
3 1
1 5
2 5
2 3
2 3
3 2
4 3
5 4
樣例輸出
1 -1 1 0 0 0 0 0 0
-1 0 0 1 1 1 -1 0 0
0 1 0 0 -1 -1 1 -1 0
0 0 0 0 0 0 0 1 -1
0 0 -1 -1 0 0 0 0 1

  算法訓練 送分啦   時間限制：1.0s   內存限制：512.0MB     問題描述　　這題想得分嗎？想，請輸出「yes」；不想，請輸出「no」。輸出格式　　輸出包括一行，為「yes」或「no」。

  算法訓練 操作格子  
時間限制：1.0s   內存限制：256.0MB
   
問題描述

有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。

  算法訓練 逆序對   時間限制：1.0s   內存限制：256.0MB     問題描述 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。

  算法訓練 安慰奶牛   時間限制：1.0s   內存限制：256.0MB     問題描述 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。

  算法訓練 最短路   時間限制：1.0s   內存限制：256.0MB     問題描述 給定一個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，保證從任意頂點都能到達其他所有頂點。

  算法訓練 結點選擇   時間限制：1.0s   內存限制：256.0MB     問題描述 有一棵 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的正整數。

  算法訓練 K好數   時間限制：1.0s   內存限制：256.0MB     問題描述 如果一個自然數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。

  算法訓練 最大最小公倍數   時間限制：1.0s   內存限制：256.0MB     問題描述 已知一個正整數N，問從1~N中任選出三個數，他們的最小公倍數最大可以為多少。
輸入格式 輸入一個正整數N。
輸出格式 輸出一個整數，表示你找到的最小公倍數。 樣例輸入 9 樣例輸出 504 數據規模與約定 1 <= N <= 106。

  算法訓練 區間k大數查詢   時間限制：1.0s   內存限制：256.0MB     問題描述 給定一個序列，每次詢問序列中第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)，序列中的數<=10^6。