2019年安徽省程序设计大赛题目

本文主要是介绍2019年安徽省程序设计大赛题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.机器人足球

时间限制：2s
描述：
足球场地长为100，宽为20，对方球门的坐标为（100，10），你要控制一个机器人踢球，初始位置为（x,y）,机器人可以朝任何方向移动，但不能超出场地边界。当机器人与球门距离不超过10时，可以射门。问机器人从初始位置出发到射门，最少要移动多少距离？（四舍五入到小数点后3位）

输入
每组输入为2个整数，分别为x,y
0<=x<=100
0<=y<=20

输出
输入最小移动的距离

样例输入

10 10

样例输出

80.000

#include <bits/stdc++.h> 
using namespace std;
int main()
{int x,y;scanf("%d%d",&x, &y);double s;s=sqrt((x-100)*(x-100)+(y-10)*(y-10));if(s<0.000001){printf("0.000\n");}else{printf("%.3f",s-10);}return 0;	
}

B.纸牌识别

时间限制：2s
描述：
Alice沉迷于机器人研究，他打算做一个机器人来检查一副扑克是否完成，现在，他想请你帮他写一个程序，来识别纸牌。每张纸牌都有一个花色（四种花色，分别用大写字母P，K,H,T表示）和一个数字点数（1-13）.纸牌可以用ABC的形式来表示，A代表花色，BC代表数字，如果数字小于10，会有一位补0.比如花色是P，数字是9的纸牌会表示成P09.一副完整的纸牌有52张牌，四种不同的花色各有1张数字1-13的牌。
你的程序要读入一个字符串，表示缺少的纸牌有哪些，如果包含相同的纸牌（花色数字都相同）输出GRESKA，否则输入每种花色剩余的纸牌数量。

输入
输入只有一行，一个字符串s，s的长度小于等于1000.

输出
如果输入中包含相同的纸牌，输出GRESKA，否则分别输入四个整数，代表P,K,H,T四种花色纸牌的剩余数量。

样例输入1

P01K02H03H04

样例输出1

12 12 11 13

样例输入2

H02H10P11H02

样例输出2

GRESKA

提示
样例1中P花色缺少P01，所以只有12张，K花色缺少K02，所以也只有12张，H花色缺少两张；T花色不缺牌。

C.卡牌对决

时间限制：3s
描述：
有2N张牌，它们的点数分别为1到2N，Alice拿到了其中的N张，Bob拿了剩下的N张，Alice和Bob会进行N轮游戏，在每轮游戏中，Alice和Bob各出了一张牌，出了的牌不能收回，在前N/2轮中，每轮谁的牌点数大谁就赢；在后N/2轮中，每轮谁的牌点数小谁就赢。一直Bob每一轮会出什么牌，试求Alice最多能赢多少轮。

输入
第一行是一个整数N
接下来N行，每行一个整数，表示Bob这轮会出什么
2<=N<=50000,保证N是偶数
输出
输出Alice最多能赢几轮

样例输入

样例输出

D.自驾游

时间限制：2s
描述：
P省有N个城市，编号分别为1 . . . N，烦烦家住1号城市，N 号城市是省会。P省的交通非常发达，有 M 条有向的高速公路连接这 N 个城市，第 i 条高速公路（1 <= i <= M）从城市 ui 连向城市 vi.
这天，烦烦想自己开车从家前往省会城市游玩。烦烦是个做事很细致的人，为了有备无患，她决定同时开着 heromap 和 amap 这两个不同的导航软件来帮助自己完成这次旅程。这两个导航软件内部采用了不同的算法，对于第 i 条高速公路（1 <= i <= M）, heromap认为通过时间为 Pi 分钟，amap 则认为通过时间为 Qi 分钟，这两个导航软件会根据自己的数据来计算从当前位置到目标位置所需的最短时间是多少，对于第 i 个城市（1 <= i <=N ），记 heromap 认为从 i 到 N 的最短时间为 hero（i）, 记 amap 认为从 i 到 N 的最短时间为a（i）。烦烦开车途经某条高速公路（1 <= i <= M）时，如果 heromap 认为从 ui 到 N 不应该走这条路，即 hero(vi) + Pi > hero(ui)，则发出一次警告，同样的，如果 amap 认为从 ui 到 N 不应该走这条路，即 a(i) + Qi > a(ui)，也会发出一个警告。现在烦烦希望自己选择一条路径，使得受到的警告总数最少，请你编程解决这一问题。

输入
第一行是一个整数N和M
接下来M行，第 i 行有四个整数 ui, vi, Pi, Qi 分别表示第 i 条边发出的出发点和到达点编号，两个导航软件认为走过这条边所用的时间。
2 <= N <= 10000
1 <= M <= 50000
1 <= ui, vi <= N
输出
输出从 1 走到 N 最少受到多少次警告

样例输入

样例输出

E.现代艺术

时间限制：2s
描述：
给出平面上 N 个点的坐标点集，求这 N 个点有多少条整体对称轴。整体对称是指一条直线，对于每个点，都能找到点集的一个点与他关于这条直线对称。

输入
第一行是一个整数N，表示点的个数
接下来 N 行，每行两个整数 X, Y，表示点的坐标
2 <= N <= 1000
-10000 <= X, Y <= 10000
输出
输出点集的整体对称轴有多少条
样例输入

样例输出

F.邻家割草

时间限制：3s
描述：
邻居 Alice 家有一块大草坪，每个一段时间他都要用割草机修剪草坪；可以把草坪看成是一个 N * M 的矩阵，割草时需要 N 台割草机水平方向穿过草地， M 台割草机垂直方向穿过草地。草地并不是完全平整的，有高有低；如图所示，高的地方用深色表示，矮的地方用浅色表示。
在这里插入图片描述
割草机工作时需要消耗燃油，在走过不同的高度的草地时，会消耗 A 元燃油费；（比如从低的地方走到高的地方，从高的地方走到低的地方，在相同高度的地块上运行割草机的燃油消耗可以忽略）。Alice 为了节省燃油费，准备改造一些地形；可以给一些地块加入来升高地形，或者把高的地方铲平来降低地形高度，对一个地块进行改造需要花费 B 元。你能帮邻居 Alice 设计一个方案。让他花费最小吗？

输入
输人的第一行是四个整数 N M A B,分别表示矩阵有 N 行，M 列; 走过不同高度的地块需要多花费 A 元; 调整地块高度需要花费 B 元，
接下来 N 行，每行 M 个字符，‘#’ 代表高的地块，字符 ‘.’ 代表低的地块
1 <= N, M <= 50
1 <= A, B <= 10^6
输出
输出 Alice 改造地块 + 割草的最小花费
样例输入

54 1000 2000
. . . #
# . . #
. . . #
# # . .
# # # .

样例输出

提示
Alice 的草地大小是 5 x 4 .在不同高度的地块上行走每个割草机要多花费1000
元，调整一个地块的地形需要花费2000元;
Alice 最少需要 11000 元。2000 元用于修改第行第一个地块，把这个地块的
高度降低。9000元用于割草，水平方向运行的5台割草机花费5000元，垂直
方向运行的4台割草机花费4000元，

G.括号序列

时间限制：2s
描述：
括号序列是指由 ‘(’ 和 ‘)’ 组成的序列，假如一个括号序列中，包含相同数量的左括号和右括号，并且对于每一个右括号，在他的左侧都有左括号和他匹配，则这个括号序列就是一个合法括号序列，如（（））（）就是一个合法括号序列，但（（））（（）不是合法括号序列.
给出两个长度相同的合法括号序列 A 和 B , 那么 A < B 当且仅当:
● A 和 B 至少有一位不相同。
● 在 A 和 B 从左往右数第一个不相同的位置 i ， A[ i ] = ( , B[ i ] = )
比如A = （（））（）, B = （）（）（），则 A < B 。因为从左边数第一个不相同的是第二个字符，A[2] = ( , B[2] = )。对于长度 N，由于定义了小于关系，则可以通过这个关系推出所有长度为N的合法括号序列的大小关系，对于长度为6的合法括号序列，从小到大排列顺序如下:
1.（（（）））
2.（（）（））
3. （（））（）
4. （）（（））
5. （）（）（）
给出 N 和 M，求长度为 N 的合法括号序列中，第 M 小的合法括号序列是？

输入
输入的第一行是 N 和 M
2 <= N <= 2000
1 <= M <= 10^18
输出
输出一个字符串，表示长度为 N 的平衡括号序列从小到大排列，序号为 M 的字符串
样例输入

6 2

样例输出

（（）（））

H.不要回文

时间限制：2s
描述：
给出一个字符串 S，你需要尽可能少的修改 S 中的字符，使得 S 不包含长度大于等于 2 的回文子串。

输入
输入的第一行是一个字符串 S， S只包含小写字母
S 的长度大于 5 小于 300
输出
输出使得 S 中不包含长度大于等于 2 的回文，最少需要修改几个字符（可以修改成任意字符）
样例输入

abbaa

样例输出

I.你的名字

时间限制：2s
描述：
Alice 想要计算他那 N 只猫的名字的价值每只猫的名字由不超过 1000 个大小写字母构成，没有一个名字是空字体串。 Alice有一张*价值字符串表”，上面有 M个代表价值的字符串。每个字符串由不超过30个大小写字母构成，同样不存在空字符串。一个猫的名字蕴含多少个价值字符串，这个名字就有多少价值，所谓 “蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现 (不一定一个紧接着一个) .
所有的大写字母和小写字母都是等价的。比如，在贝黄的名字"Bessie"里，蕴含有 “Be” “si” “EE” 以及 “Es” 等等字符串，但不蕴含"Ls°或"eB"请帮Alice计算他的猫的名字的价值.
输入
输人的第-行是两个整数 N M
接下来N行，每行一个字符串表示猫的名字。
接下来M行，每行一个价值字符串
1 <=N<= 1000
1 <= M<=100
输出
输出每只猫名字蕴含多少个价值字符串，
样例输入

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
Se  
nGo  
oNt

样例输出

J.密信

时间限制：3s
描述：
Alice 想给 Bob 发短信，短信的内容可以看成是一个只有小写字母的字符串 p;为了加密短信，Alice 需要只有小写字母长度为 n 的字符串 h ,并且 p 是 h 的子串: Alice 想知道，这样的字符串有多少种。
给出 n 和 M 还有字符串 p ,假设一共有 K 种不同的 h ,输出K mod M

输入
输人包含多组数据，第一行是组数 T , T ≤= 50
对于每组测试数据，第一行是 n M
接下来一行是字符串 p
n,M <= 10 ^ 12
P 是一个长度不大于 50 且只有小写字母的字符串
输出
输出 K mod M
样例输入

2
2 100
ab
3 100
ab

样例输出

1
52

K.福报

时间限制：2s
描述：
员工绩效评估对于任何公司都是很重要的，在绩效考核中，员工会就最近完成的工作编写工作反馈。反馈会被递给他们的上级，然后上级根据收到的反馈来决定绩效.
Alice 负责-家知名公司工程部广]的绩效考核系统。该部门遵循树形结构。每位员工都有一个直接上级，最上级是部门总监.
让上级评估其直接下属的表现并不是很有效.经过深人研究，Alice 想出了一个新的绩效考核系统，主要思路是在现有的公司结构中补充每个员工的技术等级，新的绩效评估流程如下，员工要准备他们的工作反馈，然后向所有比他技术等级高的上级(直接上级和间接上级)递交工作反馈;上级需要花时间审核所有递交给他的工作反馈。
Alice 对这个新系统感到非常满意，但她不确定这在实践中是否可行，她想知道每个员工审核下属工作反馈所需的时间，你能帮她吗?

输入
输人的第一行是整数 E , 员工的总数。接下来有 E 行，第 i 行有三个整数mi,n,t表示第 i 号员工对应的上级编号，他的技术等级，审核他的工作反馈所需要的时间，部门总监没有上级，所以他的上级编号是 -1
1 < E, mi, ri,ti < 10^6
输出
按编号顺序输出每位员工审核下属工作反馈所需时间
样例输入

样例输出

提示
1号审核2号，花费时间40
2号是叶子节点，没有下属
3号审核4号，1号，5号，2号，花费时间80+40+50+70=240
4号审核1号，2号，花费时间80+40=120
5号没有下属

L.曲奇工厂

时间限制：2s
描述：
曲奇工厂是一个经典好玩的益智游戏，游戏中你的目标是生产至少 C 块曲奇:游戏的规则十分简单; 游戏开始时你有 0 块曲着，每分钟可以手工作出 S 块曲奇。你也可以从 N 个工厂中选择些买下来; 工厂依次编号为 1-N ,买下第 i 个工厂需要花费 Ai 个曲奇饼。但是工厂会为你带来更多收益，买下第 i 个工厂后，每分钟曲奇产出会增加 Bi 块。
对于每个工厂，你只能买一次: 你只能在整数分钟时购买工厂，并且可以一次买多个工厂, 请问达成日标所用最短时间是多少?

输入
输人的第一行是三个整数 N, C 和 S
接下来 N 行，每行两个整数 Ai 和 Bi
1 <=N<= 5
1<= C, S, Ai, Bi <=.10^5
输出
输出得到至少 C 块曲奇，最少要多长时间，
样例输入