蓝桥杯2019校赛题目+答案

蓝桥杯2019校赛题目+答案

题目 1

问题描述

某涉密单位下发了某种票据,并要在年终全部收回。每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。你的任务是通过编程,找出断号的ID和重号的ID。假设断号不可能发生在最大和最小号。

要求程序首先输入一个整数N(N<100)表示后面数据行数。

接着读入N行数据。

每行数据长度不等,是用空格分开的若干个(不大于100个)正整数(不大于100000)

每个整数代表一个ID号。

要求程序输出1行,含两个整数m n,用空格分隔。

其中,m表示断号ID,n表示重号ID

样例输入

2

5 6 8 11 9

10 12 9

样例输出:

7 9

样例输入:

6

164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196

172 189 127 107 112 192 103 131 133 169 158

128 102 110 148 139 157 140 195 197

185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190

149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188

113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119

样例输出:

105 120

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
int a[100001] = { 0 };
int t, row, ans, min = 100000, max = 0;
cin >> row;
while(row--)
while (1) { // 数据记录最大最小值此为范围
cin >> t;
if (t > max)
max = t;
if (t < min)
min = t;
++a[t]; // 出现几次,a[i] 为几
if (a[t] == 2)
ans = t;
if (getchar() == '\n')
break;
}

for(int i = min; i <= max; i++) {
if (a[i] == 0) {
cout << i << " ";
break;
}
}

cout << ans;
return 0;
}

题目 2

问题描述:

四平方和

四平方和定理,又称为拉格朗日定理: 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去,就正好可以表示为4个数的平方和。

比如: 5 = 0^2 + 0^2 + 1^2 + 2^2 7 = 1^2 + 1^2 + 1^2 + 22 (符号表示乘方的意思)

对于一个给定的正整数,可能存在多种平方和的表示法。 要求你对4个数排序: 0 <= a <= b <= c <= d 并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法

程序输入为一个正整数N (N<5000000) 要求输出4个非负整数,按从小到大排序,中间用空格分开

样例输入

5

样例输出

0 0 1 2

样例输入

12

样例输入

0 2 2 2

样例输入

773535

样例输出

1 1 267 838

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;

void f(int n) {
for (int i = 0; i < sqrt(n); ++i) {
int t1 = n - i * i;
for (int j = 0; j < sqrt(t1); ++j) {
int t2 = t1 - j * j;
for (int k = 0; k < sqrt(t2); ++k) {
int t3 = t2 - k * k;
int l = sqrt(t3);
if (l * l == t3) {
printf("%d %d %d %d\n", i ,j ,k ,l);
return;
}
}
}
}
}

int main() {
int n;
cin >> n;
f(n);
return 0;
}

题目 3

题目描述:

饮料换购

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊C型饮料,凭3个瓶盖可以再换一瓶C型饮料,并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下,如果小明不浪费瓶盖,尽量地参加活动,那么,对于他初始买入的n瓶饮料,最后他一共能喝到多少瓶饮料。

输入:一个整数n,表示开始购买的饮料数量(0<n<10000) 输出:一个整数,表示实际得到的饮料数

样例输入

100

样例输出

149

样例输入

101

样例输出

151

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

using namespace std;

int main() {
int n, cnt;
cin >> n;
cnt = n;
while (n / 3) {
cnt += n / 3;
n = n / 3 + n % 3;
}
cout << cnt;
return 0;
}

题目 4

题目描述

给定一个合法的括号序列,请你找出每一对匹配左右括号的位置。

输入:一个只包含左右小括号的序列,长度不超过100000。保证括号序列是合法的。

输出:对于序列中每一个左括号,输出它和与它匹配的右括号的位置。

样例输入

1
(())()()

样例输出

1
2
3
4
1 4
2 3
5 6
7 8

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stack>
#include <string>
#include <iostream>

using namespace std;

int main()
{
stack<int> kuohao;
string str;
cin >> str;
int arr[100000]{ 0 }, t = 0;
for (int i = 0; i < str.length(); i++)
if (str[i] == '(')
kuohao.push(i);
else {
if (!kuohao.empty()) {
arr[kuohao.top()] = i;
kuohao.pop();
}
}
for (int i = 0; i < 100000; i++)
if (arr[i] != 0)
cout << i + 1 << " " << arr[i] + 1 << endl;
return 0;
}

/*------------------------------------------------------------------------------------*/
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
}

int main() {
vector<pair<int, int>> ans;
stack<int> brackets;

string s;
cin >> s;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
brackets.push(i+1);
} else {
ans.push_back(make_pair(brackets.top(), i+1));
brackets.pop();
}
}

sort(ans.begin(), ans.begin()+ans.size(), cmp);
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i].first << " " << ans[i].second << endl;
}

return 0;
}

题目 5

题目描述

给定一个N x M的矩阵,请你数一数其中有多少个3 x 3的子矩阵可以构成三阶幻方?

如果3 x 3的矩阵中每一行、每一列和两条对角线上的3个数之和都相等,我们就认为其构成一个三阶幻方。

输入:第一行包含两个整数N和M。(1 ≤ N, M ≤ 100),以下N行M列包含一个N x M的矩阵A。(1 ≤ Aij ≤ 100)

输出矩阵中包含多少个三阶幻方。

样例输入

1
2
3
4
5
6
5 5
4 9 2 1 8
3 5 7 6 2
8 1 6 9 3
2 3 3 6 9
5 6 9 3 6

样例输出

1
2

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>

using namespace std;

int maze[101][101];

bool check(int i, int j) {
int sum = maze[i][j] + maze[i+1][j] + maze[i+2][j];
if (maze[i][j+1] + maze[i+1][j+1] + maze[i+2][j+1] != sum)
return false;
if (maze[i][j+2] + maze[i+1][j+2] + maze[i+2][j+2] != sum)
return false;
if (maze[i+1][j] + maze[i+1][j+1] + maze[i+1][j+2] != sum)
return false;
if (maze[i][j] + maze[i][j+1] + maze[i][j+2] != sum)
return false;
if (maze[i+2][j] + maze[i+2][j+1] + maze[i+2][j+2] != sum)
return false;
if (maze[i][j] + maze[i+1][j+1] + maze[i+2][j+2] != sum)
return false;
if (maze[i][j+2] + maze[i+1][j+1] + maze[i+2][j] != sum)
return false;
return true;
}

int main() {
int n, m, cnt = 0;
cin >> n >> m;

for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> maze[i][j];

for (int i = 0; i < n - 2; ++i)
for (int j = 0; j < m - 2; ++j)
if (check(i, j))
++cnt;
cout << cnt << endl;
return 0;
}

题目 6

描述

给定一个数组A1, A2, ... AN,每次操作可以从中选定一个元素Ai,把除了Ai之外的所有元素都加1。

问最少几次操作可以实现“共同富裕”,即数组中所有元素都相等。

例如对于[1, 1, 1, 2, 3]经过3步:[1, 1, 1, 2, 3] -> [2, 2, 2, 3, 3] -> [3, 3, 3, 3, 4] -> [4, 4, 4, 4, 4]。

输入:第一行包含一个整数N。(1 ≤ N ≤ 100000),以下N行包含N个整数A1, A2, ... AN。 (1 ≤ Ai ≤ 100000)

输出:最小的操作数

样例输入

1
2
3
4
5
6
5
1
1
1
2
3

样例输出

1
3

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 101000;
int rec[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> rec[i];
sort(rec, rec + n);
long long ans = 0;
int a = rec[0];
for (int i = 0; i < n; i++)
ans += rec[i] - a;
cout << ans << endl;

return 0;
}

题目 7

描述

给定:

1)N个正整数A1, A2, ... AN;

2)P个加号+和Q个减号-; (P+Q=N-1)

3)K对括号()

请你使用全部整数、加减号和括号,组成一个合法的算式(A1~AN在算式中的顺序随意),使得算式的结果最大。

注意加减号只能作为二元运算符出现在算式中,不能作为正负号。

括号可以出现在算式最左和最右,例如(((1+2)))是合法的。

例如对于样例数据,(2-1)+3或3+(2-1)等都是结果最大的算式。

输入格式

第一行包含4个整数,N,P, Q和K。

第二行包含N个整数A1, A2, ... AN。

2 ≤ N ≤ 100 P+Q+1=N 0 ≤ K ≤ 10

1 ≤ Ai ≤ 1000

输出格式

最大算式结果

样例输入

1
2
3 1 1 1
1 2 3

样例输出

1
4

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>

using namespace std;

bool cmp(int x, int y) {
return x > y;
}

int main() {
int n, p, q, k;
int a[110];
cin >> n >> p >> q >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n, cmp);
int ans = 0;

if (k == 0) {
for (int i = 0; i < n; i++)
if (i <= p)
ans += a[i];
else
ans -= a[i];
} else {
for (int i = 0; i < n - 1; i++)
ans += a[i];
ans -= a[n-1];
}
cout << ans << endl;
return 0;
}

题目 8

描述

小Ho的虚拟城市正在遭受小Hi的攻击,小Hi用来攻击小Ho城市的武器是一艘歼星舰,这艘歼星舰会以T(T为大于0的整数)个单位时间的间隔向小Ho的城市轰击。歼星舰总共有N枚炮弹,其中第i枚会造成Ai点伤害值。

幸好小Ho的城市有K层护盾,每层护盾可以抵挡M点伤害。当某次轰击使得伤害值达或超过M时,该层护盾就会被击碎;该次轰击溢出的伤害不会作用于下一层护盾;下一次轰击将由下一层护盾承受。

同时,受损但尚未被击碎护盾会以每单位时间减少1点伤害值的速度修复自己,直到伤害值降为0。这就意味着小Hi的攻击间隔T越大,小Ho撑过这N枚炮弹的可能性就越大。

那么问题来了,小Hi的攻击间隔T至少需要是多少,小Ho城市的防护护盾才能不被全部击破?

为了使题目不存在歧义,规定:

小Hi的第i次攻击发生在时刻(i-1)*T

小Ho的第i次修复发生在时刻i-0.5

输入

第一行包含3个整数N、M和K,意义如前文所述。

第二行包含N个整数A1 - AN,表示小Hi第i枚炮弹的伤害值。

对于30%的数据,满足N<=100

对于100%的数据,满足1<=N<=100000

对于100%的数据,满足1<=K<=10, 1<=Ai, M<=100000

输出

输出使得小Ho城市的防护护盾不被全部击破的小Hi攻击间隔的最小值。如果不存在这样的T,则输出-1。

样例输入

1
2
3 5 1
3 3 3

样例输出

1
3

参考解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>

using namespace std;

int n, m, k;
int a[101];

bool check(int T);

int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; ++i)
cin >> a[i];

int mid, left = 0, right = 0xffffff;

while (true) {
mid = (left + right) / 2;
if (mid == left && mid == right) {
mid = -1;
break;
}
bool flag = check(mid);
if (flag && !check(mid-1)) {
break;
} else if (!flag) {
left = mid;
} else {
right = mid;
}
}
cout << mid << endl;
return 0;
}

bool check(int T) {
int tmpM = m;
for (int i = 0; i < n; ++i) {
if (tmpM > a[i]) {
tmpM -= a[i];
tmpM += T;
tmpM = tmpM > m ? m : tmpM;
}
else {
tmpM = m;
if (--k == 0) return false;
}
}
return true;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×