2017第八届蓝桥杯C/C++语言A组

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一：题目：

标题：迷宫

X星球的一处迷宫游乐场建在某个小山坡上。
它是由10x10相互连通的小房间组成的。

房间的地板上写着一个很大的字母。
我们假设玩家是面朝上坡的方向站立，则：
L表示走到左边的房间，
R表示走到右边的房间，
U表示走到上坡方向的房间，
D表示走到下坡方向的房间。

X星球的居民有点懒，不愿意费力思考。
他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把100名玩家放入一个个小房间内。
玩家一定要按照地上的字母移动。

迷宫地图如下：
------------
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
------------

请你计算一下，最后，有多少玩家会走出迷宫?
而不是在里边兜圈子。

请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。

参考：

蓝桥杯果然越来越不水了（本人菜鸟。。。。。）这是递归写的，low，坐等bigold。

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack> using namespace std;int canornot[][];
char map[][];
int flag = ;int canout(int x, int y)
{
int prex = x, prey = y;
flag++;
if (x < || x> || y < || y>||canornot[y][x]==)
{
flag--;
return ;
}
switch (map[y][x])
{
case 'U':
y ++;
break;
case'D':
y --;
break;
case'R':
x ++;
break;
case'L':
x --;
break;
}
if (flag > )
{
canornot[y][x] = ;
flag--;
return ;
}
if (canout(x, y))
{
canornot[prey][prex] = ;
flag--;
return ;
}
else
{
canornot[prey][prex] = ;
flag--;
return ;
}
}int main()
{
int x, y;
int sum=;
char useless;
for (y = ; y >= ; y--)
{
for (x = ; x < ; x++)
{
scanf("%c", &map[y][x]);
canornot[y][x] = -;
}
scanf("%c",&useless);
} for (y = ; y >= ; y--)
{
for (x = ; x < ; x++)
{
canout(x, y);
if (canornot[y][x])
sum++;
}
}
printf("\n%d\n", sum);
return ;
}

二：题目：

标题：跳蚱蜢

如图 p1.png 所示：
有9只盘子，排成1个圆圈。
其中8只盘子内装着8只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8

每只蚱蜢都可以跳到相邻的空盘中，
也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，
并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？

注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

参考：

三：魔方模拟，，，，跳过（一般是看不懂的节奏）

四:题目：

标题：方格分割

6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。

如图：p1.png, p2.png, p3.png 就是可行的分割法。

试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。

参考：

结果因为旋转要除四；此解没有剪枝，

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <queue>using namespace std;int map[][];
int dire[][] = { -,,,,,-,, };//方向
const int N = ;
int ans;
void dfs(int x, int y)
{
if (x == || y == N || x == N || y == ) {
ans++; return;
}
for (int i = ; i<; i++)
{
int nx = x + dire[i][];
int ny = y + dire[i][];
if (nx< || nx>N || y< || ny>N)continue;
if (!map[nx][ny])
{
map[nx][ny] = ;
map[N - nx][N - ny] = ;
dfs(nx, ny); map[nx][ny] = ;
map[N - nx][N - ny] = ;
} }
}
int main()
{
map[N / ][N / ] = ;
dfs(N / , N / );
cout << ans / << endl;
return ;
}

五：题目

标题：字母组串由 A,B,C 这3个字母就可以组成许多串。
比如："A","AB","ABC","ABA","AACBB" ....现在，小明正在思考一个问题：
如果每个字母的个数有限定，能组成多少个已知长度的串呢？他请好朋友来帮忙，很快得到了代码，
解决方案超级简单，然而最重要的部分却语焉不详。请仔细分析源码，填写划线部分缺少的内容。#include <stdio.h>// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。
int f(int a, int b, int c, int n)
{
if(a< || b< || c<) return ;
if(n==) return ; return ______________________________________ ; // 填空
}int main()
{
printf("%d\n", f(,,,));
printf("%d\n", f(,,,));
return ;
}对于上面的测试数据，小明口算的结果应该是：19er注意：只填写划线部分缺少的代码，不要提交任何多余内容或说明性文字。

参考：刚开始想复杂了，结果，，，， f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

六：题目：

标题：最大公共子串

最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。

比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

#include <stdio.h>
#include <string.h>#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;memset(a,,sizeof(int)*N*N);
int max = ;
for(i=; i<=len1; i++){
for(j=; j<=len2; j++){
if(s1[i-]==s2[j-]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}return max;
}int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return ;
}

参考：emmmm，，，第一眼还以为kmp

a[i-1][j-1]+1

七：题目：

描述：正则问题

考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入
----
一个由x()|组成的正则表达式。输入长度不超过100，保证合法。

输出
----
这个正则表达式能接受的最长字符串的长度。

例如，
输入：
((xx|xxx)x|(x|xx))xx

程序应该输出：
6

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

参考：实话说，完全看不懂题目在说啥，后来发现原来这是最简单的题目。

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string>
#include <stack>
#include <queue>using namespace std;string str;
int pos, len;
int dfs()
{
int xnum = , res = ;
while (pos < len) {
if (str[pos] == '(') {
pos++;
xnum += dfs();
}
else if (str[pos] == ')') {
pos++;
break;
}
else if (str[pos] == '|') {
pos++;
res = max(xnum, res);
xnum = ;
}
else {
pos++;
xnum++;
}
}
res = max(xnum, res);
return res;
}
int main()
{
cin >> str;
int ans = ;
len = str.length(), pos = ;
ans = dfs();
cout << ans << endl;
return ;
}

八:题目：

标题：包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。

当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

例如，
输入：
2
4
5

程序应该输出：
6

再例如，
输入：
2
4
6

程序应该输出：
INF

样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

参考：

对于整系数方程 ax+by = c ，
如果 a、b 的最大公约数能整除 c ，那么它的整数解有无数多个，
如果 a、b 的最大公约数不能整除 c，那么它没有整数解。
如果a、b的最大公约数不为1，则不论x、y是啥，数不到的就会有无穷个；
为一的话，就是有限个。

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <queue>using namespace std;int gcd(int a, int b)
{
if (b == )
return a;
return gcd(b, a%b);
}int unit[], n;
const int N = ;
bool sign[N];int main()
{ scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &unit[i]);
int g = unit[];
for (int i = ; i < n; i++)
g = gcd(g, unit[i]);
if (g != )
{
printf("INF\n");
}
else
{
sign[] = true;
for (int i = ; i < n; i++)
{
for (int j = ; j + unit[i] < N; j++)
if (sign[j])
sign[j + unit[i]] = true;
}
int count = ;
for (int i = ; i < N - ; i++)
{
if (sign[i] == false)
count++;
}
printf("%d\n", count);
}
return ;}

九：题目：

标题：分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数
2. 大小相同

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出
输出切出的正方形巧克力最大可能的边长。

样例输入：
2 10
6 5
5 6

样例输出：
2

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

提交程序时，注意选择所期望的语言类型和编译器类型。

参考：呃呃呃，二分搜索找最大边长

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include<algorithm>
#include<time.h>
#include<math.h>
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <queue>using namespace std;int n, k, length[], wide[];bool chocolate(int n)
{
int num = , a, b, i;
for (i = ; i<n; i++)
{
a = length[i] / n;
b = wide[i] / n;
num += a*b;
}
if (num >= k)
return true;
return false;
}
int main()
{
int i, low, high;
while (scanf("%d%d", &n, &k) != EOF)
{
low = ;
high = ;
for (i = ; i<n; i++)
scanf("%d%d", &length[i], &wide[i]);
while (low<high - )
{
int mid = (low + high) / ;
if (!chocolate(mid))
high = mid;
else
low = mid;
}
printf("%d\n", low);
}
return ;
}