第七届蓝桥杯C语言C组-(自己懂的题目)

第七届蓝桥杯C语言C组-(自己懂的题目)


表示刚刚查了成绩,省赛一等奖,有资格去北京了,然后写一下总结,
先来写一下我懂的题目,毕竟我也是菜鸟,听说国赛比预赛难几个等级。。。


第一题
报纸页数

X星球日报和我们地球的城市早报是一样的,
都是一些单独的纸张叠在一起而已。每张纸印有4版。

比如,某张报纸包含的4页是:5,6,11,12,
可以确定它应该是最上边的第2张报纸。

我们在太空中捡到了一张X星球的报纸,4个页码分别是:
1125,1126,1727,1728

请你计算这份报纸一共多少页(也就是最大页码,并不是用了几张纸哦)?
请填写表示总页数的数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。
这道题我没填,说实话,没看懂,没看过报纸的孩纸
不会。。
贴吧说的。。。

1
1125+1126+1727+1728=1+2+X,X等于5703,5703等于2851+2852


第二题
煤球数目

有一堆煤球,堆成三角棱锥形。具体:
第一层放1个,
第二层3个(排列成三角形),
第三层6个(排列成三角形),
第四层10个(排列成三角形),
….
如果一共有100层,共有多少个煤球?

请填表示煤球总数目的数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<iostream>
using namespace std;
int getInt(int n) {
int n1 = 1;
int sum = n1;
for (int i = 2; i <= n; i++) {
sum = i + n1;
n1 = sum;
}
return sum;
}
int main() {
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += getInt(i);
}
cout << sum << endl;
return 0;
}

我当时填的5050,计算的是第100层。。 题目要求的是100层总共多少。
答案171700


第三题
平方怪圈

如果把一个正整数的每一位都平方后再求和,得到一个新的正整数。
对新产生的正整数再做同样的处理。

如此一来,你会发现,不管开始取的是什么数字,
最终如果不是落入1,就是落入同一个循环圈。

请写出这个循环圈中最大的那个数字。
请填写该最大数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

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<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char s[100];
int getInt(char *s) {
int sum = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
sum += (s[i]-'0')*(s[i]-'0');
}
return sum;
}
int main() {
int num = 3;
int MAX = 0;
for (int i = 0; i < 100; i++) {
sprintf(s, "%d", num);
num = getInt(s);
MAX = max(MAX, num);
}
cout << MAX << endl;
return 0;
}

答案145 有一些是1,可以打印出来


第四题
打印方格
11分
小明想在控制台上输出 m x n 个方格。
比如 10x4的,输出的样子是:
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+
| | | | | | | | | | |
+—+—+—+—+—+—+—+—+—+—+

(如果显示有问题,可以参见【图1.jpg】)

以下是小明写的程序,请你分析其流程,填写划线部分缺少的代码。

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
#include <stdio.h>
//打印m列,n行的方格
void f(int m, int n)
{
int row;
int col;

for(row=0; row<n; row++){
for(col=0; col<m; col++) printf("+---");
printf("+\n");
for(col=0; col<m; col++) printf("| ");
printf("|\n");
}

printf("+");
_____________________________; //填空
printf("\n");
}


int main()
{
f(10,4);
return 0;
}

注意:仅仅填写划线部分缺少的内容,不要添加任何已有内容或说明性文字。
for循环即可,反正我是这样写的

1
2
3
for(col=0; col<m; col++) printf("---+");
//或者
for(row=0; row<m; row++) printf("---+");

第五题
13分
快速排序

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。

其思想是:先选一个“标尺”,
用它把整个队列过一遍筛子,
以保证:其左边的元素都不大于它,其右边的元素都不小于它。

这样,排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

下面的代码是一种实现,请分析并填写划线部分缺少的代码。

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
#include <stdio.h>


void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}


int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
swap(a,i,j);
}
______________________;
return j;
}


void quicksort(int a[], int p, int r)
{
if(p<r){
int q = partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

int main()
{
int i;
int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};
int N = 12;

quicksort(a, 0, N-1);

for(i=0; i<N; i++) printf("%d ", a[i]);
printf("\n");

return 0;
}

答案是swap(a,p,j)


第六题
6.
15分
凑算式

B DEF
A + — + ——- = 10
C GHI

(如果显示有问题,可以参见【图1.jpg】)

这个算式中A~I代表1~9的数字,不同的字母代表不同的数字。

比如:
6+8/3+952/714 就是一种解法,
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法?

注意:你提交应该是个整数,不要填写任何多余的内容或说明性文字。

这里写图片描述
记住要通分,不要fabs(…) < 1E10 这样来进行约等于
dfs思路

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a1[9], book[9], COUNT = 0;
bool getSum(int *a) {
int A = a[0], B = a[1], C = a[2];
int DEF = a[3]*100+a[4]*10+a[5], GHI = a[6]*100+a[7]*10+a[8];
if ((B*GHI+DEF*C)%(C*GHI) != 0) return false;
if (A+(B*GHI+DEF*C)/(C*GHI) == 10) return true;
return false;
}
void dfs(int step) {
if (step == 9) {
if (getSum(a1)) COUNT++;
return;
}
for (int i = 0; i < 9; i++) {
if (book[i] == 0) {
book[i] = 1;
a1[step] = i+1;
dfs(step+1);
book[i] = 0;
}
}
}
int main() {
dfs(0);
cout << COUNT << endl;
return 0;
}

答案29


第七题
19分
寒假作业
现在小学的数学题目也不是那么好玩的。
看看这个寒假作业:
□ + □ = □
□ - □ = □
□ × □ = □
□ ÷ □ = □
(如果显示不出来,可以参见【图1.jpg】)
每个方块代表1~13中的某一个数字,但不能重复。
比如:
6 + 7 = 13
9 - 8 = 1
3 4 = 12
10 / 2 = 5
以及:
7 + 6 = 13
9 - 8 = 1
3
4 = 12
10 / 2 = 5
就算两种解法。(加法,乘法交换律后算不同的方案)

你一共找到了多少种方案?
还是dfs思路

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<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a1[13], book[13], COUNT = 0;
bool getSum(int *a) {
if (a[9]%a[10] != 0) return false;
return (
a[0]+a[1] == a[2] &&
a[3]-a[4] == a[5] &&
a[6]*a[7] == a[8] &&
a[9]/a[10] == a[11]
);
}
void dfs(int step) {
if (step == 13) {
if (getSum(a1)) COUNT++;
return;
}
for (int i = 0; i < 13; i++) {
if (book[i] == 0) {
book[i] = 1;
a1[step] = i+1;
dfs(step+1);
book[i] = 0;
}
}
}
int main() {
dfs(0);
cout << COUNT << endl;
return 0;
}

大概运行了5分钟。。
答案64
如果有好的解法,请告诉我,本人水平有限。嘿嘿


第八题
21分
冰雹数

任意给定一个正整数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的数字,经过冰雹数变换过程中,最高冲到了多少。

例如,输入:
10
程序应该输出:
52

再例如,输入:
100
程序应该输出:
9232

相信很多童鞋被这道题给坑了。。。 哈哈哈,请看清题意
一个正整数,表示不大于N的数字
好吧,是后面往前面推,在考场我不到五分钟写好代码。。。 然后跪了。。
错误代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<iostream>
using namespace std;
int getInt(int N) {
if (N%2 == 0) return N/2;
return N*3+1;
}
int main() {
int N;
scanf("%d", &N);
int MAX = N;
while(N != 1) {
N = getInt(N);
MAX = max(MAX, N);
}
cout << MAX << endl;
return 0;
}

写完之后,感觉么么哒。。。
然后一测数据,感觉不对劲,是不是题目测试数据给错了,到了快交卷,我还是以为是测试数据错了。。
其实是我理解题意错了。
正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<iostream>
using namespace std;
int getInt(int N) {
if (N%2 == 0) return N/2;
return N*3+1;
}
int main() {
int N, MAX, M;
scanf("%d", &N);
MAX = N;
for (int i = N; i >= 1; i--) {
M = i;
while(M != 1) {
M = getInt(M);
MAX = max(MAX, M);
}
}
cout << MAX << endl;
return 0;
}

如果输入的数大于122222就会超时。。
水一部分数据吧。


第九题
25

卡片换位

你玩过华容道的游戏吗?
这是个类似的,但更简单的游戏。
看下面 3 x 2 的格子

+—+—+—+
| A | | |
+—+—+—+
| B | | * |
+—+—+—+

在其中放5张牌,其中A代表关羽,B代表张飞,* 代表士兵。
还有一个格子是空着的。

你可以把一张牌移动到相邻的空格中去(对角不算相邻)。
游戏的目标是:关羽和张飞交换位置,其它的牌随便在哪里都可以。

输入格式:
输入两行6个字符表示当前的局面

输出格式:
一个整数,表示最少多少步,才能把AB换位(其它牌位置随意)

这里写图片描述

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms


记忆化搜索
不会。。


第十道
密码脱落

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。

例如,输入:
ABCBA
则程序应该输出:
0

再例如,输入:
ABECDCBABC
则程序应该输出:
3

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。
听大神说动态规划
不会。。。