1、背景 Background TYVJ八月月賽提高組第1題測試點數(shù)目：5測試點分值：20--內存限制：128M--時間限制：1s描述 Description 　　定義如下括號匹配序列：　　　　1．空序列是匹配序列；　　　　2．如果S是匹配序列，那么(S),[S],{S}和也是匹配序列；　　　　3．如果A和B都是匹配序列，那么AB也是匹配序列。

2、　　例如，下面的字符串都是匹配序列：　　　　()，[]，(())，([])，()[]，()[()]，{{}}，([]{{}})，　　而以下幾個則不是：　　　　(，[，]，)(，())，([()，<<，{(})，)　　序列中可能包含通配符，含義如下：　　　　/匹配任意1個左括號　　　　#匹配任意2個左括號　　　　@匹配任意4個左括號　　　　?匹配任意8個左括號　　　　匹配任意1個右括號　　　　*匹配任意2個右括號　　　　&匹配任意4個右括號　　　　!匹配任意8個右括號　　現(xiàn)在，給你一些由"("、")"、"["、"]"、"{"、"}"、""和通配符構成的序列，你要做的，是判斷該序列是否為匹配序列。

(資料圖片僅供參考)

3、輸入格式 Input Format 第一行：一個正整數(shù)N，表示測試數(shù)據(jù)組數(shù)； 接下來N行：每行一個括號序列(長度不超過L)。

4、輸出格式 Output Format 共N行：對于每一個括號序列，判斷其是否匹配。

5、對于不匹配的序列，直接輸出FALSE。

6、對于匹配的序列，輸出用單一空格隔開的3個信息：　　第一個信息為TRUE　　第二個信息為括號的最大深度(層數(shù))　　第三個信息為達到最大深度的次數(shù)詳見樣例樣例輸入 Sample Input [復制數(shù)據(jù)] 2{()}@{})))>([})樣例輸出 Sample Output [復制數(shù)據(jù)] TRUE 5 2FALSE注釋 Hint 樣例解釋：對于第一組數(shù)據(jù)，@相當于<(((，是匹配的，括號的最大深度為5，該深度出現(xiàn)了2次。

7、對于第二組數(shù)據(jù)，[和}不匹配。

8、數(shù)據(jù)規(guī)模：對于20%的數(shù)據(jù)，有N=1，0

9、近日，令島民們振奮的消息傳來：S國的專家要為他們修建電網?。?！孤島上共有N個村莊，發(fā)電站要建在第K個村莊中。

10、S國的專家要在N個村莊間修建M條輸電線路，但由于地理原因，M條線路無法保證每個村莊都與第K個村莊(建有發(fā)電站)直接相連，同樣，也不一定能保證每個村莊都與第K個村莊間接相連(假設A與B直接相連，B與C直接相連，那么A與C間接相連)。

11、然而，由于S國的專家智商實在太“高”了，以至于設計出了許多冗余線路。

12、現(xiàn)給出第i條線路兩個端點Ui,Vi(分別表示線路連接的兩個村莊,Ui!=Vi)和長度Li，請你幫島民算一下：如果電網可以覆蓋全島，最少需要多長的電線；若不能，有多少個村莊無電可用。

13、注意：0<=冗余線路數(shù)目

14、輸入格式 Input Format 第一行：N M K接下來M行：Ui Vi Li具體含義見題目描述輸出格式 Output Format 如果電網可以覆蓋全島，輸出最少需要的電線長度；若不能，輸出無電可用的村莊的個數(shù)。

15、 樣例輸入 Sample Input [復制數(shù)據(jù)] 【樣例1】5 5 11 2 12 3 13 4 14 5 15 1 1【樣例2】5 5 11 2 11 2 21 2 33 4 15 4 2樣例輸出 Sample Output [復制數(shù)據(jù)] 【樣例1】4【樣例2】3注釋 Hint 樣例解釋：對于樣例一，電網可以覆蓋全島，最短長度為4；對于樣例二，電網無法覆蓋3,4,5這3個村莊。

16、數(shù)據(jù)范圍：對于20%的數(shù)據(jù)，有117、 背景 Background TYVJ八月月賽提高組第3題測試點數(shù)目：10測試點分值：10--內存限制：128M--時間限制：1s描述 Description 黃金礦工是一個經典的小游戲，它可以鍛煉人的反應能力。18、該游戲中，可以通過“挖礦”獲得積分并不斷升級。

19、玩家可以在線玩flash版黃金礦工，也可以下載后玩單機版黃金礦工。

20、目前，黃金礦工小游戲有多個版本，例如黃金礦工雙人版，黃金礦工單人版等。

21、Jimmy是一位黃金礦工，他所在的金礦是一個n*n的矩形區(qū)域（俯視），區(qū)域內有黃金、石頭和TNT，由一個n*n的矩陣描述。

22、黃金的價值對應矩陣中的正值，石頭的價值對應矩陣中的負值，TNT由0表示。

23、換句話說，挖到黃金賺錢，石頭虧損，如果挖到TNT就掛了~_~Jimmy租到的挖礦工具很特別，它的形狀是一個長寬任意（均為正整數(shù)）的矩形，可以取走被該工具覆蓋的矩形區(qū)域內的所有物品，但如果該區(qū)域內有TNT，該工具將被炸毀，此時Jimmy將不得不賠償?shù)V主+∞元！?。⌒枰⒁獾氖?，該工具只能在金礦范圍內使用（即不得超出金礦邊界），且租金為每次十元。

24、現(xiàn)在，Jimmy想知道，如果他至多只有一次租用該工具的機會，他能獲得的最大收益是多少。

25、當然，如果Jimmy租用該工具無論如何都會虧損，他可以不租用，此時收益為0.輸入格式 Input Format 第一行：一個整數(shù)n接下來n行，每行n個整數(shù)（絕對值<100），為題目中所描述的矩陣。

26、輸出格式 Output Format 一個數(shù)，即Jimmy所能獲得的最大收益。

27、 TYVJ八月月賽提高組第4題樣例輸入 Sample Input [復制數(shù)據(jù)] 30 -1 -10 -12 0-19 0 0樣例輸出 Sample Output [復制數(shù)據(jù)] 0注釋 Hint 樣例解釋：無論Jimmy怎么挖礦，挖到的不是石頭，就是TNT，總之無論如何都會虧損，所以選擇不租用工具，收益為0數(shù)據(jù)范圍：對于30%的數(shù)據(jù)：0

28、來到GF身邊，他發(fā)現(xiàn)GF身上綁著一把連有炸彈的密碼雙鎖。

29、密碼雙鎖由兩把子鎖組成，每把子鎖都有對應的密碼。

30、只有連續(xù)正確輸入兩把子鎖的密碼，鎖才能解開，否則連在鎖上的炸彈就會爆炸，NPY和他的GF就升天了?。ㄆ鋵峃PY是很想去西天和GF結婚的，只是他的GF還想多活幾年。

31、）子鎖一分為A,B兩種類型，鎖上有兩個提示信息：第一個信息表示本子鎖的類型（”A”或”B”之一）；第二個信息為N，具體含義見下文。

32、對于任意一種類型的子鎖一，只有輸入正確的密碼P才能打開，否則炸彈會爆炸…… 那么P是什么呢？？？原來，P就是下述序列的第N項（起始項為第1項，共無窮多項）。

33、子鎖一序列的前幾項如下： A型子鎖一對應的序列=0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,…B型子鎖一對應的序列=0,1,1,3,1,3,3,7,1,3,3,7,3,7,7,15,1,3,3,7,…仔細觀察上面兩個序列，可以發(fā)現(xiàn)：對于序列{A}或序列{B}，其奇數(shù)項構成的新序列與原序列完全相同。

34、解開子鎖一后，子鎖二浮現(xiàn)在NPY眼前。

35、子鎖二很特別，它是一個邊長為P的正立的網格正三角形（下圖是P=2的情況），這把子鎖的密碼，就是該三角形中，正立的子三角形的個數(shù)Q（包括邊長為P的，不包括邊長為0的）。

36、下圖中有5個邊長為2的正立的網格正三角形。

37、用紅線標出的，是它的4個正立子三角形。

38、（用紫線標出的，是倒立子三角形，這里只求正立的，不管倒立的）其中，邊長為2的正立子三角形有1個，邊長為1的正立子三角形有3個，共4個。

39、現(xiàn)在，NPY已經知道子鎖一的兩個提示信息，他希望得到兩把子鎖的密碼，從而解開密碼雙鎖，與GF逃離魔窟。

40、你不會不幫他吧。

41、輸入格式 Input Format 第一行：字母A或B，表示子鎖一的類型；第二行：正整數(shù)N。

42、輸出格式 Output Format 第一行：一個整數(shù) P第二行：一個整數(shù) Q具體含義見題目描述樣例輸入 Sample Input [復制數(shù)據(jù)] A4樣例輸出 Sample Output [復制數(shù)據(jù)] 24注釋 Hint 樣例解釋：子鎖一類型為A，提示信息N=4，故P=序列{A}的第4項：2子鎖二的邊長為P=2，其正立子三角形有4個，故Q=4.（見上圖）數(shù)據(jù)范圍：對于40%的數(shù)據(jù)，子鎖一為A型；其余為B型。

43、對于30%的數(shù)據(jù)，0

本文到此分享完畢，希望對大家有所幫助。