2016年安徽省大学生程序设计大赛

B. 阵前第一功

C. 箭无虚发

D. 梯田AGAIN

2016年“京胜杯”安徽省大学生程序设计大赛

比

赛

题

目

全国大学生信息安全竞赛安徽省赛区组委会

安徽省大学生程序设计大赛技术委员会

2016年5月24日 合肥

目 录

E. 转啊转

F. 吃在工大

G. 木条染色

H. 单身晚会

I. 恶魔A+B

J. YZK的大别墅

K. 纸上谈兵

A. 砝码称重

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

小明非常喜爱物理，有一天，他对物理实验室中常用的弹簧拉力计产生了兴趣。实验室中有两种质量不同的砝码，小明分别用a个第一种砝码放在弹簧拉力计上和b个第二种砝码放在弹簧拉力计上，假设每增加单位重量的砝码，弹簧拉力计的长度增加1，那么两次称量弹簧拉力计的长度差是多少呢？（假设拉力计不发生非弹性形变）

输入格式：

第一行一个整数T，表示有T组数据。

之后T行，每行数据包含四个正整数，分别表示第一种砝码重量a，第一种砝码数量b，第二种砝码重量c，第二种砝码数量d。

T<25

0输出格式：

对于每组数据，输出一个正整数，表示弹簧拉力计的长度差值。

输入样例：

3

1 2 3 4

1 4 2 2

1 3 2 1

输出样例：

10

0

1

B. 阵前第一功

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

A国每个国民都有一定战斗力，每年国家都要对人民的战斗力进行一次排序统计，他们的排序规矩是相同战斗力的排名一样，而且只占一个排序名额。比如，有5个人：100,100,90,90,70. 两个100的并列第一，称为第一战斗力，两个90的并列第二，称为第二战斗力，依次类推……现在你想查询第K战斗力是多少

输入描述：

先输入一个整数T，表示T（T<50）组数据。

每组第一行一个正整数N（1000>N>0），表示表示有N个人。接下里一行N个正整数ai(2^30>=ai>=0)，表示每个人的战斗力。

接下输入一个正整数K（N>=K>0）。（保证输入都合法）

输出描述：

输出第K战斗力,输出占一行

输入样例：

2

5

100 90 90 100 70

2

10

1 2 3 3 3 400 3 4 3 1

4

输出样例：

90

2

C. 箭无虚发

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

JH苦练10年，终于成为了一个神箭手，在下山之前，大师兄YZ不放心，想考验他，只给他一定时间t，同时给他n支箭，最终根据他的表现，考虑他是否能下山。

对于每发一次箭，YZ给他4种成绩（优、良、中、差），JH有三种拉弓以及瞄准时间a ,b，c（a>=b>=c）分别能拿优，良，中等级，如果不拉弓不瞄（直接射），只能拿差（不能中靶）了。

现在JH想知道，在保证自己弹无虚发（不获得差）的情况下，最多能拿多少个优。

如果JH不能做到弹无虚发，输出Oh，my god!

输入描述：

输入数据包含T组:

对于每组数据，第一行为一个整数n，表示总共有n支箭。

0之后n行，每行包含三个数字a，b，c，分别表示拿对应等级所需要花的时间。

(0之后一个数字t，表示JH有考核总时间为t

(0<=t<=1000000)

输出描述：

对于每组输入，如果JH能箭无虚发，则输出一个数字x，表示最多能拿到的优的数量。如果不能，则输出Oh，my god!

输入样例：

3

1

3 2 1

1

2

3 2 1

3 2 1

4

2

3 2 1

3 2 1

1

输出样例：

0

1

Oh,my god!

D. 梯田AGAIN

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

大家还记得去年的梯田吗？土豪YZK在一块小岛上有着一大片n*m的梯田，每块1*1的田地都有它的高度。奴隶们不甘被YZK剥削，他们联合起来决定发动一场海啸淹掉YZK的部分梯田。

奴隶们去年尝试了一下，结果发现，由于土质太过松软，水能够透过土地渗入到相邻的梯田，即对于海啸高度h，梯田中所有小于等于h的土地都会由于土质松软而被被淹没。

现在给你一个n*m的矩阵，代表梯田中每块田地的高度。然后给定q个询问，每个询问给定一个海啸高度h，问在此高度下，不被淹没的梯田数量是多少。

输入格式：

第一行一个整数T，表示测试数据组数。

对于每组测试数据：

第一行三个数字n，m，q，表示梯田的行数，列数和询问数。

之后n行，每行m个数字，表示每块田地的高度，梯田高度不大于1000000。

之后q行，每行给出一个海啸高度h，问大于这个高度的梯田有多少块。

0输出格式：

对于每个询问，给出一个整数，表示大于这个海啸高度的梯田数量。

输入样例：

2

2 2 2

1 2

3 4

2

3

2 3 3

1 2 3

3 4 5

0

4

5

输出样例：

2

1

6

1

0

E. 转啊转

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

在二维平面上，有一个固定的圆和一个固定的点（保证该点不在圆上），还有一个动点在圆上以角速度w绕圆心一直转。在t时刻，连接该动点与定点成一条直线k，求直线k被圆所截线段的长度（即直线k在圆内部分长度）。

动点初始时刻在圆的三点钟方向（即与x轴正方向平行），并以逆时针方向绕圆转。

输入描述：

先输入一个整数T，表示T（T<50）组数据。

每组数据一行七个实数a,b,r(r>0),x,y,w(w>=0),t(t>=0) 分别表示圆的圆心坐标（a,b），半径r,固定点坐标(x,y)，角速度w,要查询的时刻t。

上述所有数据的绝对值小于10000。

输出描述：

输出答案占一行，保留2位小数。

输入样例：

1

1 1 1 3 1 3 0

输出样例：

2.00

角速度定义：

一个以弧度为单位的圆（一个圆周为2π,即：360度=2π),在单位时间内所走的弧度即为角速度。

F. 吃在工大

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

JH和他的好朋友YZ两名程序员回访母校合工大，准备在这住一段日子，都说“玩在安大，吃在工大”，JH又是一名典型吃货，于是决定在工大食堂好好吃一段日子，但是，面对美食诱惑：黄焖鸡、风暴干锅、麻辣香锅、奥尔良烤翅…由于时间有限，JH不知道哪顿饭吃哪个菜好。

于是YZ为了帮助他解决这个问题，也顺便考考他，给他出了一个问题：“黄焖鸡必须在干锅花菜前面吃，干锅牛肉必须在干锅鱿鱼前面吃….你按这个要求下，就知道吃的顺序啦”。JH抓抓头，分分钟写了个程序搞定，现在，让你来写写看？输出一组JH符合条件下吃的食物的序列。

假设JH每顿只吃一种食物，且每顿吃的都不同，食物编号1到N。

输入描述：

先输入一个整数T，表示T（T<20）组数据。

每组数据第一行输出一个整数，N,M,分别表示有N(N<=1000)种食物，总共有M(M<5000)个约束条件，接下来M行每行输入两个正整数a,b(n>=a>0,n>=b>0)，表示食物a必须在食物b之前吃。

输出描述：

各组数据输出答案占一行，输出一组符合条件的序列（要求输出字典序最大的那一组），如果答案不存在，输出“-1”。

输入样例：

1

4 3

1 2

2 3

4 3

输出样例：

4 1 2 3

G. 木条染色

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

小明是一个非常浪漫的画家，他喜欢画各种奇奇怪怪的画，虽然没人理解他画的究竟是什么东西。

有一天，他突发奇想，对于一根木条，他每次从木条中选取一个区间[l,r]进行染色，多次染色之后，他想知道在[a,b]区间中有几个未被染色的子区间？

可惜小明虽然画画非常厉害，但是并不擅长解决这类问题，于是，他拿着这根木条来找你，希望你能够给他帮助。

假设木条无限长，所有查询都在木条长度范围内，未被染色的子区间是指，木条上染过色的区间的间断部分。

输入格式：

第一行一个整数T，代表数据组数。

对于每组数据，第一行给出两个整数n，q，分别代表染色的区间个数，以及查询个数。

之后n行，每行两个整数l，r，表示将l到r的区间进行染色，包含l，r两个节点。

之后q行，每行两个整数a，b，表示询问a到b总共有多少未被染色的子区间。

两组数据之间用一个空行隔开。

T<20

n<10000

q<100000

0<=l0<=a<=b<1000000

输出格式：

对于每次询问，输出一个整数，表示查询结果。

每组数据之后，请输出一个空行。

输入样例：

2

2 3

1 2

3 4

1 3

3 4

5 5

3 3

1 5

2 8

5 6

0 5

0 9

9 9

输出样例：

1

0

1

1

2

1

样例解释：

对于第一组数据，[0,1)，(2,3)，(4,+)是未染色的子区间，因此查询[1,3]可以找到(2,3)这个子区间，而对于[3,4]不能找到，对于[5,5]可以找到[5,5]。

对于第二组数据，[0,1)和(8,+)是未染色的子区间，因此对于[0,5]只有子区间[0,1)，对于查询[0,9]，有子区间[0,1)和（8,9]，对于查询[9,9]，有[9,9]这个子区间。

H. 单身晚会

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

ZJ和ZCX在一起很久了，两个人都互生爱意，最终决定喜结良缘，从此踏入浪漫的婚姻殿堂。

但是，ZJ的好基友们想到以后ZJ就不能经常跟他们一起愉快的玩耍了，都觉得非常伤心难过，于是他们决定在最后一晚为ZJ开一场单身晚会，玩整晚紧张刺激的飞行棋。

ZJ的好基友居住在城市的各个地方（每个地方不一定只有一个基友），他们需要从各个地方赶到其中一个朋友的家里来参加这最后的单身PARTY，ZJ被基友们的热情深深感动了，决定对基友们来时的路费进行报销。报销规则按照距离来计算。基友们为了帮ZJ省钱，决定在所有人走最短路径的情况下，总距离最小的人的家里开PARTY。

ZJ想知道基友们走过的总距离是多少，然后他把总共需要报销的钱拿出来，就可以让基友们自己来分配了。但是他算了半天也没算出来总距离是多少，单身PARTY马上就开始了，你能帮帮他吗？

输入格式：

第一行一个整数T，表示有T（T<15）组数据

每组数据的第一行基友数（包括ZJ）N（N<100），路口P（2<=P<=100）,路口之间道路数C(1<=C<=1450)，（基友的编号为1…N，路口的编号为1…P）

第二行到第N+1行：编号为1到N的基友们家所在的路口号。

第N+2行到N+C+1行：每行有三个数：相连的路口A,B，路口间间距D（1<=D<=255），当然，连接是双向的。

输出格式：

每组数据输出占一行，输出大家必须要走的最小距离和

样例输入：

1

3 4 5

2

3

4

1 2 1

1 3 5

2 3 7

2 4 3

3 4 5

样例输出：

8

I. 恶魔A+B

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

相信大家都做过A+B问题，这个问题简直太简单了，以至于所有的程序员都会做这个题目。

有一天，萌萌哒YZK学姐写了很久很久的代码，以至于在半睡半醒状态看到了恶魔。

恶魔说：愚蠢的程序员啊，不要再做无谓的挣扎了，你再怎么写代码，也改变不了这个世界终将被我统治的结局。

YZK学姐顿时觉得自己被侵犯了，为了程序员的尊严，她要求与恶魔进行决斗，决斗的形式就是写代码。

恶魔给出了一个非常复杂的A+B问题，对于两个长度小于1000的26进制数，它们

相加的结果是什么呢？

两人谁先解决这个问题谁就获胜，你能帮助YZK学姐战胜恶魔吗？

输入格式：

第一行一个整数T，代表测试数据组数，0之后T行，每行两个长度不大于1000的字符串，仅包含a~z和小数点，a~z分别代表数字0~25。

输出格式：

输出占一行，输出相加的结果，不能包含前导零和后导零（即a）。

输入样例：

3

b b

bb ac

a.b a.b

输出样例

c

bd

a.c

J. YZK的大别墅

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

土豪YZK最近得到了面积为n*m的一大块土地（高兴ING^_^），他想在这块土地上建造一所别墅，但是这个别墅必须是方形的。

可是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。但是却可以挖成人工观赏湖，或者挖成游泳池。

YZK希望找到一块最大的矩形土地来盖别墅，YZK计划在里面盖一些房子并且挖一些人工湖，但是YZK最多只愿意造k个人工湖(一个人工湖的占地面积为1，即使是相连的两块地方都是人工湖，也要算作两块人工湖)，现在请你来帮助YZK找到面积最大的满足条件的土地。

给定一个01矩阵，0表示土地可用，1表示土地不可用，输出符合YZK要求的最大土地的面积。

输入格式：

第一行一个整数T，表示有T组测试数据。

对于每组测试数据，第一行包含三个整数n，m，k，表示矩阵的行数和列数，以及最多的人工湖数量。

之后n行，每行m个整数，表示矩阵。

T<25

0输出格式：

对于每组数据输出一行占一行，包含一个整数，表示最大面积。

输入样例：

2

2 2 0

1 0

0 1

3 3 1

1 0 0

0 0 1

0 0 1

输出样例：

1

6

K. 纸上谈兵

Time Limit: 1000 MS Memory Limit: 65536 KB

题目描述：

战国时期，孙膑与庞涓都拜在鬼谷子门下学习。有一日鬼谷子想考察他们兵法，对着墙上挂着的一幅当时城池地图（假设城池编号从1到N，相邻城池之间有边相连），让他们自己相互考察：

庞涓出题：“如果我给出一组城池间相互约束的关系，你能否给我一个攻城方案，…….”

孙膑出题：“如果从1号城池出发，到达N号城池，请问最多有几条最近的路？我对不同的最近的路有两种定义，第一种：‘如果两条路径有一条边不相同，就认为这两条路径不同’，第二种‘如果两条路径有一条边相同，就认为相同’，请告诉我在这两种不同定义下，各自答案是多少”

由于地图很大，图上大大小小的城池很多，两人对着图一时有点迷糊，这就很尴尬了！

据说当时缓解这尴尬局面的一位来自未来的神奇少年，背地里相互告诉他们各自的答案，这人莫非就是你？

输入描述：

先输入一个整数T，表示T（T<20）组数据。

每组第一行三个正整数N，M，K（500>N>0，10000>M>0，50000>K>0），表示表示有N个城池，M条边,K组约束关系。

接下里M行，每行3个正整数a，b，w(N>=a,b>=1,1000000>w>0)，表示a,b之间有条边，长度为w。

接下来K行，每行有下面几种形式：

1 a b ：表示如果攻打城池a，则必须攻打城池b。

2 a b ：表示城池a,b至少攻打一个。

3 a b ：表示如果城池a攻打了，则城池b不能攻打。

4 a b ：表示如果城池a没有攻打，则城池b必须攻打。

5 a b ：表示城池a与城池b只能都攻打或者都不攻打。

(N>=a,b>=1)

输出描述：

每组数据输出占三行：

第一行输出孙膑给的方案，N个数，如果城池i攻打，输出1，反之输出0，这N个数构成的01序列代表一个方案。如果不存在方案，输出“impossible.”

第二行输出庞涓的第一个解，输出按第一种定义下的最短路；第三行输出庞涓的第二个解，输出按第二种定义下的最短路。如果不存在最短路，输出“-1”

输入样例：

2

5 6 5

1 2 3

2 4 4

4 5 1

1 3 5

3 4 2

3 5 3

1 1 2

1 2 1

2 1 2

3 1 4

4 3 5

3 3 5

1 2 10

2 3 10

1 3 20

1 1 2

1 2 1

2 1 2

3 1 3

1 2 3

输出样例：

1 1 0 0 1

3

2

impossible.

2

2

提示：

第一组样例中：孙膑的答案表示 攻打1 2 5，不攻打3 4。庞涓的第一个解：1->2->4->5, 1->3->4->5, 1->3->5。第二个解：1->2->4->5, 1->3->5