2014?編程之美挑戰賽 --- 資格賽真題
題目1 : 同構
-
1 3 1 2 2 3 2 1 2
樣例輸出 -
Case 1: NO
描述
給定2個樹A和B，保證A的節點個數>=B的節點個數。
現在你需要對樹A的邊進行二染色。
一個好的染色方案，指不存在一個樹A中的連通塊，同時滿足以下2個條件
1. 其中只有同色的邊
2. 和B同構。兩個樹同構是指，存在一個一一映射（既是單射又是滿射），將樹B的各節點映射到不同的樹A的節點，使得原來在樹B中相鄰的點，在映射后，仍相鄰。
問是否存在一種好的染色方案。
輸入
第一行一個整數T (1<=T<=10)，表示數據組數。
接下來是T組輸入數據，測試數據之間沒有空行。
每組數據格式如下：
第一行一個整數N ，表示樹A的節點總數。
接下來N-1行，每行2個數a, b (1 <= a, b <= N)表示樹A的節點a和b之間有一條邊。
接下來一行，一個整數M(1 <= M <= N)，表示樹B的節點總數。
接下來M-1行，每行2個數a, b (1 <= a, b <= M)表示樹B的節點a和b之間有一條邊。
輸出
對每組數據，先輸出“Case x: ”，x表示是第幾組數據，然后接“YES”/“NO”，表示是否存在所求的染色方案。
數據范圍
小數據：1 <= N <= 20
大數據：1 <= N <= 1000000
樣例解釋
無論如何染色，只要從A中挑一條邊就行了。
題目2 : 大神與三位小伙伴
-
2 1 3
樣例輸出 -
Case 1: 1 Case 2: 72
描述
L國是一個有著優美景色且物產豐富的國家，很多人都喜歡來這里旅游并且喜歡帶走一些紀念品，大神同學也不例外。距離開L國的時間越來越近了，大神同學正在煩惱給她可愛的小伙伴們帶什么紀念品好，現在擺在大神同學面前的有三類紀念品A, B, C可以選擇，每類紀念品各有N種。其中種類為A_i, B_i, C_i的紀念品價值均為i, 且分別有N+1-i個剩余。現在大神同學希望在三類紀念品中各挑選一件然后贈送給她的三名可愛的小伙伴，但是她又不希望恰好挑出來兩件價值相同的紀念品，因為這樣拿到相同價值紀念品的兩位小伙伴就會認為大神同學偏袒另一位小伙伴而不理睬她超過一星期。現在，大神同學希望你買到的三件紀念品能讓三位小伙伴都開心并且不和她鬧別扭，她想知道一共有多少種不同挑選的方法？
因為方案數可能非常大，大神同學希望知道挑選紀念品的方案數模10^9+7之后的答案。
輸入
第一行包括一個數T，表示數據的組數。
接下來包含T組數據，每組數據一行，包括一個整數N。
輸出
對于每組數據，輸出一行“Case x:?”，其中x表示每組數據的編號(從1開始)，后接一個數，表示模10^9+7后的選擇紀念品的方案數。
數據范圍
小數據：
1<=T<=10
1<=N<=100
大數據：
1<=T<=1000
1<=N<=10^18
樣例解釋
對于第二組數據，合法的方案有以下幾種，(X,Y,Z)表示選擇了A類紀念品中價值為X的，B類紀念品中價值為Y的，C類紀念品中價值為Z的。
(1,1,1): 3*3*3=27種
(1,2,3): 3*2*1=6種
(1,3,2): 3*1*2=6種
(2,1,3): 2*3*1=6種
(2,2,2): 2*2*2=8種
(2,3,1): 2*1*3=6種
(3,1,2): 1*3*2=6種
(3,2,1): 1*2*3=6種
(3,3,3): 1*1*1=1種
一共27+6+6+6+8+6+6+6+1=72種選擇紀念品的方案
注意，如(1,1,2), (2,3,3), (3,1,3)都因為恰好選擇了兩件價值相同的紀念品，所以并不是一種符合要求的紀念品選擇方法。
題目3 : 格格取數
-
2 3 3 1 2 3 3 1 2 2 3 1 5 5 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1
樣例輸出 -
Case 1: 3 Case 2: 5
描述
給你一個m x n (1 <= m, n <= 100)的矩陣A (0<=aij<=10000)，要求在矩陣中選擇一些數，要求每一行，每一列都至少選到了一個數，使得選出的數的和盡量的小。
輸入
多組測試數據。首先是數據組數T
對于每組測試數據，第1行是兩個正整數m, n，分別表示矩陣的行數和列數。
接下來的m行，每行n個整數，之間用一個空格分隔，表示矩陣A的元素。
輸出
每組數據輸出一行，表示選出的數的和的最小值。
數據范圍
小數據：1 <= m, n <= 5
大數據：1 <= m, n <= 100
提交頁面：
)
)
