第十届“蓝桥杯”大赛软件类校选

第一题

问题描述

给你一个排好序的数组,请基于当前数组去除所有重复的元素。

输入

输入包含多组数据。对于每组数据: 第一行是n,表示数组有n个元素,当n=-1,表示输入结束;第二行是n个排序好的整数

输出

针对每组输入,输出去重后的数组

样例输入

5
1 2 2 3 3
-1

样例输出

1 2 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
#include<iostream>
using namespace std;
const int maxn = 1000000;
int ans[maxn];
int main()
{
int n;
int tmp;
cin >> n;
while(n!=-1){
cin >> ans[0];
int k = 1; //数组ans的index
for(int i = 1;i < n;i++){
cin >> tmp;
if(tmp>ans[k-1]){
ans[k++] = tmp;
}
}
for(int j = 0; j < k;j++)
{
cout<<ans[j]<< " ";
}
cout << endl;
cin >> n;
}
return 0;
}

第二题

问题描述

四平方和定理,又称为拉格朗日定理: 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去,就正好可以表示为4个数的平方和。 比如:
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符号表示乘方的意思) 对于一个给定的正整数,可能存在多种平方和的表示法。 要求你对4个数排序:0 <= a <= b <= c <= d,并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法
程序输入为一个正整数N (N<5000000) 要求输出4个非负整数,按从小到大排序,中间用空格分开

样例输入1

5

样例输出1

0 0 1 2

样例输入2

12

样例输出2

0 2 2 2

样例输入3

773535

样例输出3

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
#include<iostream> //存在超时问题
#include<cmath>
using namespace std;
int main()
{
int N;
cin >> N;
int a, b, c, d;
int n = (int)sqrt(N); //在这里的类型转换中,对sqrt()要实行的是向下取整,所以下面的a<=n不能写成a<n
for(a = 0;a<=n;a++){
for(b = 0;b<=n;b++){
for(c = 0;c<=n;c++){
for(d = 0;d<=n;d++){
// cout << "cur " << a << " " << b << " " << c << " " << d << endl;
if(a*a+b*b+c*c+d*d == N){
cout << a << " " << b << " " << c << " " << d << endl;
return 0;
}
}
}
}
}
return 0;
}

第三题

问题描述

任意给定一个正整数N,如果是偶数,执行: N / 2 如果是奇数,执行: N * 3 + 1
生成的新的数字再执行同样的动作,循环往复。
通过观察发现,这个数字会一会儿上升到很高, 一会儿又降落下来。就这样起起落落的,但最终必会落到“1” 这有点像小冰雹粒子在冰雹云中翻滚增长的样子。
比如N=9 9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1 可以看到,N=9的时候,这个“小冰雹”最高冲到了52这个高度。

输入格式

一个正整数N(N<1000000)

输出格式

一个正整数,表示不大于N的数字,经过冰雹数变换过程中,最高冲到了多少。

样例输入1

10

样例输出1

52

样例输入2

100

样例输出2

9232

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main(){
long long n, max, N;
cin >> N;
max = N;
while(N>=1){
n = N;
N--;
while(n!=1){
if(n%2==0)
{
n/=2; //n变小
}
else
{
n=n*3+1;
if(max < n) max = n;
}
}
}
cout << max << endl;
return 0;
}

注意看题目:一个正整数,表示不大于N的数字,经过冰雹数变换过程中,最高冲到了多少。

也就是说仅仅对N求峰值是不够的,对[1, N]都要求峰值,最终输出的max是峰值中的峰值。

第四题

问题描述

给定一个NxN的整数矩阵,小Hi每次操作可以选择两列,将这两列中的所有数变成它的相反数。
小Hi可以进行任意次操作,他的目标是使矩阵中所有数的和尽量大。你能求出最大可能的和吗?

输入格式

第一行一个整数N。
以下N行,每行N个整数Aij。
对于30%的数据,2 ≤ N ≤ 10
对于100%的数据,2 ≤ N ≤ 200, -1000 ≤ Aij ≤ 1000

输出格式

最大可能的和

样例输入

4
-1 1 1 2
-2 -3 1 2
-3 -2 1 2
-4 -1 1 2

样例输出

27

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
#include <algorithm>
#include <iostream>
#include <cstring> //用到了memset()
using namespace std;
const int MAX_N = 200;
int main()
{
int matrix[MAX_N];
memset(matrix, 0, sizeof(matrix));
int N;
cin >> N;
int tmp;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> tmp;
matrix[j] += tmp;
}
}
sort(matrix, matrix + N);
for (int i = 0;matrix[i] + matrix[i + 1]< 0; i += 2)
{
matrix[i] *= -1;
matrix[i + 1] *= -1;
}
int sum = 0;
for (int i = 0; i < N; i++)
{
sum += matrix[i];
}
cout << sum << endl;
return 0;
}

题目的意思是只能变换偶数次,所以第二个for循环中,步长设置为2。

matrix[i] + matrix[i + 1]< 0这个判断条件比较关键,想不到的话不太容易做出来。matrix[i] + matrix[i + 1]如果为负数,则变换后为正,这样sum就能变大了。可以说倒数第二个循环的作用是找到负数项并进行相反数变换,以增大sum。

第五题

问题描述

小Hi写程序时习惯用蛇形命名法(snake case)为变量起名字,即用下划线将单词连接起来,例如:file_name 、 line_number 。小Ho写程序时习惯用驼峰命名法(camel case)为变量起名字,即第一个单词首字母小写,后面单词首字
母大写,例如: fileName 、 lineNumber 。
为了风格统一,他们决定邀请公正的第三方来编写一个转换程序,可以把一种命名法的变量名转换为另一种命名法的变量名。你能帮助他们解决这一难题吗?

输入格式

第一行包含一个整数N,表示测试数据的组数。(1 <= N <= 10)
以下N行每行包含一个以某种命名法命名的变量名,长度不超过100。
输入保证组成变量名的单词只包含小写字母。

输出格式

对于每组数据,输出使用另一种命名法时对应的变量名。

样例输入

2
file_name
lineNumber

样例输出

fileName
line_number

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
#include<iostream>
#include<string> //别忘了加上这个头文件
using namespace std;
int main()
{
int N, end;
cin >> N;
string s;
while(N){
cin >> s;
for(int i = 0;i < s.length();i ++){
if(s[i]=='_'){ //遇到"_",删掉"_",并将随后的"小写字母"变为"大写字母"
s.erase(i,1);
s[i]-=32;
break;
}else if(s[i] < 'a'){ //遇到大写字母,将"大写字母"变为"_小写字母"
s[i] += 32; //变大写字母为小写字母
s.insert(i,1,'_');
break;
}
}
cout << s << endl;
N--;
}
return 0;
}

主要用来考察字符串操作函数的使用吧。只要能对erase(),length(),insert()这些函数熟练使用就ok了。

第六题

问题描述

给定N个整数二元组(X1, Y1), (X2, Y2), … (XN, YN)。
请你计算其中有多少对二元组(Xi, Yi)和(Xj, Yj)满足Xi + Xj = Yi + Yj且i < j。

输入格式

第一行包含一个整数N。
以下N行每行两个整数Xi和Yi。
对于70%的数据,1 ≤ N ≤ 1000
对于100%的数据,1 ≤ N ≤ 100000,-1000000 ≤ Xi, Yi ≤ 1000000

输出格式

一个整数表示答案。

样例输入

5
9 10
1 3
5 5
5 4
8 6

样例输出

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
const int MAX_N = 100000;
int main()
{
int N;
int matrix[MAX_N][2];
cin >> N;
for(int i = 0;i < N;i++){
cin >> matrix[i][0] >> matrix[i][1];
}
int cnt = 0;
for(int i = 0;i < N;i++){
for(int j = i+1;j < N;j++){
if(matrix[i][0]+matrix[j][0]==matrix[i][1]+matrix[j][1]){
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}

第七题

问题描述

H国的国王有很多王子,这些王子各自也都有很多王孙,王孙又各自有很多后代…… 总之,H国王族的族谱形成了一棵以国王为根的树形结构。根据H国的法律,王族的继承顺位这样规定的:
假设A和B是两位王族

  1. 如果其中一位是另一位的直系父亲、祖先,则辈份高的王族继承顺位更高
  2. 否则,假设C是A和B的最近公共祖先。显然A和B一定是C的两位不同子嗣的后代。其中C较年长的子嗣的后代的继承顺位更高

按时间顺序给出所有国王后代的出生和死亡记录,请你计算所有还活着的后代的继承顺位。

输入格式

第一行包含一个整数N和一个只包含大写字母和数字的字符串,分别代表记录的条数和国王的名字。
以下N行每行包含一条记录:
birth name1 name2 代表name1的儿子name2出生
death name 代表name死亡
1 <= N <= 10000
名字长度不超过20,并且没有重名的王族。

输出格式

按继承顺位从高到低输出每位王族的名字。(不包括国王)
每个名字一行。

样例输入

4 KING
birth KING ALI
birth KING BOB
birth ALI CARRO
death ALI

样例输出

CARRO
BOB

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
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <list>
#include <map>
#include <string>

using namespace std;
struct node
{
string name;
bool alive;
list<node *> sons; //由于node结点可能有不止一个子节点,所以用链表容器(list)存放指向其子节点的指针
node(const string &n, bool a = true) : name(n), alive(a), sons() {}
};

map<string, node *> Node; //用来存储结点名字和指向该结点的指针的映射关系。
// 由于结点的名字不会重复,所以结点的名字可以作为主键,但结点的名字无法定位结点的位置,也无法表明结点之间的关系,所以需要用到指针(node *)

void birth(const string &parent, const string &son)
{
node *king = new node(son); //king是指向新生成的结点的指针
Node[son] = king;
(Node[parent]->sons).push_back(king); //Node[king]是指向名字为parent的结点的指针
}

void death(const string &a)
{
Node[a]->alive = false; //Node[a]是指向名字为a的结点的指针
}

void dfs(node *k)
{
if(k->alive)
{
cout << k->name << endl;
}
list<node *>::iterator i;
for (i = k->sons.begin(); i != k->sons.end(); ++i)
{
dfs(*i);
}
}

int main()
{
int N; //N是记录的条数
string root; //国王的名字
string command, a, b;
cin >> N >> root;
Node[root] = new node(root, false);
for (int i = 0; i < N; i++)
{
cin >> command;
if(command == "birth")
{
cin >> a >> b;
birth(a, b);
}
else if(command == "death")
{
cin >> a;
death(a);
}
}
dfs(Node[root]);
}

如果不是在蓝桥杯的OJ上答题,那么dfs()函数写成这样也是可以的,为什么不能在蓝桥杯OJ上用?因为这种写法用到了C++11标准的一个新特性,而蓝桥杯目前不支持C++11

1
2
3
4
5
6
7
8
9
10
11
void dfs(node *k)
{
if(k->alive)
{
cout << k->name << endl;
}
for (auto i = k->sons.begin(); i != k->sons.end(); ++i)
{
dfs(*i);
}
}

这个dfs()函数中使用了auto来定义循环变量i,这个小技巧是从一位学弟的代码中学来的(果真后浪推前浪哈哈哈)

当时没看明白啥意思,于是网上搜了下auto,发现在C++11标准中,auto关键字在原有基础上,被添加了一种类似其他高级语言的型别推导特性

可以使用auto关键字作为变量的类型声明变量,前提是该变量是被类型明确的初始化变量初始化的

比如int i = 0; auto a = i; //这样a也是int类型了

auto关键字这个新特性在使用模板类的场景下,有助于减少冗赘的代码
不过现在蓝桥杯下这个新特性用不起来,以后应该是会支持的

第八题

问题描述

小Hi的学校大礼堂的地毯是由很多块N × M大小的基本地毯拼接而成的。例如由2×3的基本地毯
ABC
ABD
拼接而成的大礼堂整片地毯如下:

1
2
3
4
5
6
7
8
9
       ...
ABCABCABCABCAB
ABDABDABDABDAB
. ABCABCABCABCAB .
. ABDABDABDABDAB .
. ABCABCABCABCAB .
ABDABDABDABDAB
ABCABCABCABCAB
...

由于大礼堂面积非常大,可以认为整片地毯是由基本地毯无限延伸拼接的。
现在给出K张地毯的照片,请你判断哪些照片可能是小Hi学校大礼堂地毯的一部分。不需要考虑旋转照片的方向。
例如
BCA
BDA
BCA
可能是上述地毯的一部分,但
BAC
BAD
不可能是上述地毯的一部分。

输入格式

第1行包含三个整数,N,M 和 K。
第2~N+1行包含一个N × M的矩阵,代表基本地毯的样式。其中每一个元素都是一个大写字母(A-Z)。
之后是 K 张照片的数据。
每张照片的第一行包含两个整数,H 和 W,代表照片的大小。
以下 H 行包含一个 H × W的矩阵,代表照片中地毯的样式。其中每一个元素都是一个大写字母(A-Z)。
对于80%的数据,1 ≤ N, M ≤ 10, 1 ≤ H, W ≤ 100
对于100%的数据, 1 ≤ N, M ≤ 50, 1 ≤ K ≤ 10, 1 ≤ H ≤ 100, 1 ≤ W ≤ 800。

输出格式

对于每张照片,输出YES或者NO代表它是否可能是大礼堂地毯的一部分。

样例输入

2 3 3
ABC
ABD
3 3
BCA
BDA
BCA
2 3
BAC
BAD
7 14
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB
ABDABDABDABDAB
ABCABCABCABCAB

样例输出

YES
NO
YES

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
#include<iostream>
using namespace std;
const int MAX_N = 50, MAX_M = 50, MAX_H = 100, MAX_W = 800;
bool isPart();
int N, M, K;
int H, W;
char meta[MAX_N][MAX_M]; //用来存储基本样式
char photo[MAX_H][MAX_W];
int main()
{

cin >> N >> M >> K;
for(int i = 0;i < N;i++){ //输入基本样式
for(int j = 0;j < M;j++){
cin >> meta[i][j];
}
}
for(int i = 0;i < K;i++){ //输入照片数据
cin >> H >> W;
for(int m = 0;m < H;m++){
for(int n = 0;n < W;n++){
cin >> photo[m][n];
}
}
if(isPart()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
bool isPart(){
bool ans;
for(int m = 0;m < H-N;m++){
for(int n = 0;n<W-M;n++){
ans = true;
for(int i = 0;i < N ;i++){ //row
for(int j = 0;j < M;j++){ //column
if(photo[m+i][n+j] != meta[i][j]){
ans = false;
return true;
}
}
}
}
}
return false;
}