Tyvj题库_tyvj

1、背景 Background TYVJ八月月赛提高组第1题测试点数目：5测试点分值：20--内存限制：128M--时间限制：1s描述 Description 　　定义如下括号匹配序列：　　　　1．空序列是匹配序列；　　　　2．如果S是匹配序列，那么(S),[S],{S}和也是匹配序列；　　　　3．如果A和B都是匹配序列，那么AB也是匹配序列。

(相关资料图)

2、　　例如，下面的字符串都是匹配序列：　　　　()，[]，(())，([])，()[]，()[()]，{{}}，([]{{}})，　　而以下几个则不是：　　　　(，[，]，)(，())，([()，<<，{(})，)　　序列中可能包含通配符，含义如下：　　　　/匹配任意1个左括号　　　　#匹配任意2个左括号　　　　@匹配任意4个左括号　　　　?匹配任意8个左括号　　　　匹配任意1个右括号　　　　*匹配任意2个右括号　　　　&匹配任意4个右括号　　　　!匹配任意8个右括号　　现在，给你一些由"("、")"、"["、"]"、"{"、"}"、""和通配符构成的序列，你要做的，是判断该序列是否为匹配序列。

3、输入格式 Input Format 第一行：一个正整数N，表示测试数据组数； 接下来N行：每行一个括号序列(长度不超过L)。

4、输出格式 Output Format 共N行：对于每一个括号序列，判断其是否匹配。

5、对于不匹配的序列，直接输出FALSE。

6、对于匹配的序列，输出用单一空格隔开的3个信息：　　第一个信息为TRUE　　第二个信息为括号的最大深度(层数)　　第三个信息为达到最大深度的次数详见样例样例输入 Sample Input [复制数据] 2{()}@{})))>([})样例输出 Sample Output [复制数据] TRUE 5 2FALSE注释 Hint 样例解释：对于第一组数据，@相当于<(((，是匹配的，括号的最大深度为5，该深度出现了2次。

7、对于第二组数据，[和}不匹配。

8、数据规模：对于20%的数据，有N=1，0

9、近日，令岛民们振奋的消息传来：S国的专家要为他们修建电网！！！孤岛上共有N个村庄，发电站要建在第K个村庄中。

10、S国的专家要在N个村庄间修建M条输电线路，但由于地理原因，M条线路无法保证每个村庄都与第K个村庄(建有发电站)直接相连，同样，也不一定能保证每个村庄都与第K个村庄间接相连(假设A与B直接相连，B与C直接相连，那么A与C间接相连)。

11、然而，由于S国的专家智商实在太“高”了，以至于设计出了许多冗余线路。

12、现给出第i条线路两个端点Ui,Vi(分别表示线路连接的两个村庄,Ui!=Vi)和长度Li，请你帮岛民算一下：如果电网可以覆盖全岛，最少需要多长的电线；若不能，有多少个村庄无电可用。

13、注意：0<=冗余线路数目

14、输入格式 Input Format 第一行：N M K接下来M行：Ui Vi Li具体含义见题目描述输出格式 Output Format 如果电网可以覆盖全岛，输出最少需要的电线长度；若不能，输出无电可用的村庄的个数。

15、 样例输入 Sample Input [复制数据] 【样例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 [复制数据] 【样例1】4【样例2】3注释 Hint 样例解释：对于样例一，电网可以覆盖全岛，最短长度为4；对于样例二，电网无法覆盖3,4,5这3个村庄。

16、数据范围：对于20%的数据，有117、 背景 Background TYVJ八月月赛提高组第3题测试点数目：10测试点分值：10--内存限制：128M--时间限制：1s描述 Description 黄金矿工是一个经典的小游戏，它可以锻炼人的反应能力。18、该游戏中，可以通过“挖矿”获得积分并不断升级。

19、玩家可以在线玩flash版黄金矿工，也可以下载后玩单机版黄金矿工。

20、目前，黄金矿工小游戏有多个版本，例如黄金矿工双人版，黄金矿工单人版等。

21、Jimmy是一位黄金矿工，他所在的金矿是一个n*n的矩形区域（俯视），区域内有黄金、石头和TNT，由一个n*n的矩阵描述。

22、黄金的价值对应矩阵中的正值，石头的价值对应矩阵中的负值，TNT由0表示。

23、换句话说，挖到黄金赚钱，石头亏损，如果挖到TNT就挂了~_~Jimmy租到的挖矿工具很特别，它的形状是一个长宽任意（均为正整数）的矩形，可以取走被该工具覆盖的矩形区域内的所有物品，但如果该区域内有TNT，该工具将被炸毁，此时Jimmy将不得不赔偿矿主+∞元！！！需要注意的是，该工具只能在金矿范围内使用（即不得超出金矿边界），且租金为每次十元。

24、现在，Jimmy想知道，如果他至多只有一次租用该工具的机会，他能获得的最大收益是多少。

25、当然，如果Jimmy租用该工具无论如何都会亏损，他可以不租用，此时收益为0.输入格式 Input Format 第一行：一个整数n接下来n行，每行n个整数（绝对值<100），为题目中所描述的矩阵。

26、输出格式 Output Format 一个数，即Jimmy所能获得的最大收益。

27、 TYVJ八月月赛提高组第4题样例输入 Sample Input [复制数据] 30 -1 -10 -12 0-19 0 0样例输出 Sample Output [复制数据] 0注释 Hint 样例解释：无论Jimmy怎么挖矿，挖到的不是石头，就是TNT，总之无论如何都会亏损，所以选择不租用工具，收益为0数据范围：对于30%的数据：0

28、来到GF身边，他发现GF身上绑着一把连有炸弹的密码双锁。

29、密码双锁由两把子锁组成，每把子锁都有对应的密码。

30、只有连续正确输入两把子锁的密码，锁才能解开，否则连在锁上的炸弹就会爆炸，NPY和他的GF就升天了！（其实NPY是很想去西天和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,…仔细观察上面两个序列，可以发现：对于序列{A}或序列{B}，其奇数项构成的新序列与原序列完全相同。

34、解开子锁一后，子锁二浮现在NPY眼前。

35、子锁二很特别，它是一个边长为P的正立的网格正三角形（下图是P=2的情况），这把子锁的密码，就是该三角形中，正立的子三角形的个数Q（包括边长为P的，不包括边长为0的）。

36、下图中有5个边长为2的正立的网格正三角形。

37、用红线标出的，是它的4个正立子三角形。

38、（用紫线标出的，是倒立子三角形，这里只求正立的，不管倒立的）其中，边长为2的正立子三角形有1个，边长为1的正立子三角形有3个，共4个。

39、现在，NPY已经知道子锁一的两个提示信息，他希望得到两把子锁的密码，从而解开密码双锁，与GF逃离魔窟。

40、你不会不帮他吧。

41、输入格式 Input Format 第一行：字母A或B，表示子锁一的类型；第二行：正整数N。

42、输出格式 Output Format 第一行：一个整数 P第二行：一个整数 Q具体含义见题目描述样例输入 Sample Input [复制数据] A4样例输出 Sample Output [复制数据] 24注释 Hint 样例解释：子锁一类型为A，提示信息N=4，故P=序列{A}的第4项：2子锁二的边长为P=2，其正立子三角形有4个，故Q=4.（见上图）数据范围：对于40%的数据，子锁一为A型；其余为B型。

43、对于30%的数据，0

本文到此分享完毕，希望对大家有所帮助。