第七届蓝桥杯大赛个人赛省赛C++ A组 题解+原题 (填空题)

时间:2021-09-02 06:27:50

1.网友年龄

某君新认识一网友。

当问及年龄时,他的网友说:

“我的年龄是个2位数,我比儿子大27岁,

如果把我的年龄的两位数字交换位置,刚好就是我儿子的年龄”

请你计算:网友的年龄一共有多少种可能情况?

提示:30岁就是其中一种可能哦.

请填写表示可能情况的种数。

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

i*10+j-j*10-i =27
9*i-9*j = 27
i-j = 3


答案:7    (30 41 52 63 74 85 96)

2.生日蜡烛

某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来,他一共吹熄了236根蜡烛。

请问,他从多少岁开始过生日party的?

请填写他开始过生日party的年龄数。

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

解题思路:直接逐一枚举就可以求出来

答案:26

代码如下:
#include <stdio.h>
#include <math.h>
int main()
{
int a[101];
a[0]=0;
for(int i=1;i<=100;i++)
a[i]=a[i-1]+i;
for (int i = 1; i < 100; ++i)
for (int j = 2; j <= 100; ++j)
if(a[j]-a[i] == 236) {printf("%d %d\n",j,i);}
return 0;
}

3. 方格填数

第七届蓝桥杯大赛个人赛省赛C++ A组 题解+原题 (填空题)
如下的10个格子
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+


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


填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)


一共有多少种可能的填数方案?


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

解题思路:如果说不怎么会搜索,那么就只能用死办法,暴力枚举出来了,如果会搜索的,那么就直接dfs就出来了。。。

答案:1580



代码一:暴力暴力(代码看起来有点吓人)-----for
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
int s[15]={0},ans=0;
for (int a = 1; a < 11; ++a)
{
if(s[a]) continue;
s[a]=1;
for (int b = 1; b < 11; ++b)
{
if(s[b] || abs(b-a)==1) continue;
s[b]=1;
for (int c = 1; c < 11; ++c)
{
if(s[c] || abs(c-b)==1) continue;
s[c]=1;
for (int d = 1; d < 11; ++d)
{
if(s[d] || abs(d-a)==1) continue;
s[d]=1;
for (int e = 1; e < 11; ++e)
{
if(s[e] || abs(e-a)==1 || abs(e-d)==1 || abs(e-b)==1) continue;
s[e]=1;
for (int f = 1; f < 11; ++f)
{
if(s[f] || abs(f-a)==1 || abs(f-b)==1 || abs(f-c)==1 || abs(f-e)==1) continue;
s[f]=1;
for (int g = 1; g < 11; ++g)
{
if(s[g] || abs(g-b)==1 || abs(g-c)==1 || abs(g-f)==1) continue;
s[g]=1;
for (int h = 1; h < 11; ++h)
{
if(s[h] || abs(h-d)==1 || abs(h-e)==1) continue;
s[h]=1;
for (int i = 1; i < 11; ++i)
{
if(s[i] || abs(i-d)==1 || abs(i-e)==1 || abs(i-h)==1 || abs(i-f)==1) continue;
s[i]=1;
for(int j=1;j<11;j++)
{
if(s[j] || abs(j-e)==1 || abs(j-f)==1 || abs(j-i)==1 || abs(j-g)==1) continue;
ans++;
}
s[i]=0;
}
s[h]=0;
}
s[g]=0;
}
s[f]=0;
}
s[e]=0;
}
s[d]=0;
}
s[c]=0;
}
s[b]=0;
}
s[a]=0;
}
printf("%d\n",ans);
return 0;
}

代码二:搜索-----dfs
#include <stdio.h>
#define LL long long
#define INF 0x3f3f3f3f
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[4][5],vis[11],ans=0;
int f[4][2]={-1,-1, 0,-1, -1,1, -1,0};
int fun(int s,int x,int y)
{
for (int i = 0; i < 4; ++i)
{
int fx = x+f[i][0];
int fy = y+f[i][1];
if(fx<1 || fx>3 || fy<1 || fy>4) continue;
if(abs(s-a[fx][fy])==1) return 0;
}
return 1;
}
void dfs(int x,int y)
{
if(x==3 && y==4)
{ans++; return;}
for(int i=0;i<10;i++)
{
if(vis[i] || !fun(i,x,y)) continue;
vis[i]=1;
a[x][y]=i;
if(y==4) dfs(x+1,1);
else dfs(x,y+1);
vis[i]=0;
a[x][y]=-INF;
}
}
int main()
{
for(int i=1;i<4;i++)
for(int j=1;j<5;j++)
a[i][j]=-INF;
dfs(1,2);
printf("%d\n",ans);
return 0;
}

4. 快速排序

排序在各种场合经常被用到。

快速排序是十分常用的高效率的算法。

其思想是:先选一个“标尺”,

用它把整个队列过一遍筛子,

以保证:其左边的元素都不大于它,其右边的元素都不小于它。

这样,排序问题就被分割为两个子区间。

再分别对子区间排序就可以了。

下面的代码是一种实现,请分析并填写划线部分缺少的代码。
#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,i,j);

5. 消除尾一

下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0

如果最后一位是0,则原数字保持不变。

如果采用代码中的测试数据,应该输出:

00000000000000000000000001100111   00000000000000000000000001100000

00000000000000000000000000001100   00000000000000000000000000001100

请仔细阅读程序,填写划线部分缺少的代码。

#include <stdio.h>

void f(int x)
{
int i;
for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
printf(" ");

x = _______________________;

for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1);
printf("\n");
}

int main()
{
f(103);
f(12);
return 0;
}

注意:只填写缺少的内容,不要书写任何题面已有代码或说明性文字。

答案:x&(x+1)

6. 寒假作业

现在小学的数学题目也不是那么好玩的。

看看这个寒假作业:

 

   □+ □ = □

   □- □ = □

   □× □ = □

   □÷ □ = □

  

   (如果显示不出来,可以参见【图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

 

就算两种解法。(加法,乘法交换律后算不同的方案)

你一共找到了多少种方案?

 

请填写表示方案数目的整数。

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


答案:64


解题思路:这题和第三题一样的,可以暴力也可以dfs,只要控制好判断条件就可以了。。。

代码一:暴力暴力----for
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
int s[15]={0},ans=0;
for (int a = 1; a < 14; ++a)
{
if(s[a]) continue;
s[a]=1;
for (int b = 1; b < 14; ++b)
{
if(s[b]) continue;
s[b]=1;
for (int c = 1; c < 14; ++c)
{
if(s[c] || a+b!=c) continue;
s[c]=1;
for (int d = 1; d < 14; ++d)
{
if(s[d]) continue;
s[d]=1;
for (int e = 1; e < 14; ++e)
{
if(s[e]) continue;
s[e]=1;
for (int f = 1; f < 14; ++f)
{
if(s[f] || d-e!=f) continue;
s[f]=1;
for (int g = 1; g < 14; ++g)
{
if(s[g]) continue;
s[g]=1;
for (int h = 1; h < 14; ++h)
{
if(s[h]) continue;
s[h]=1;
for (int i = 1; i < 14; ++i)
{
if(s[i] || g*h!=i) continue;
s[i]=1;
for (int j = 1; j < 14; ++j)
{
if(s[j]) continue;
s[j]=1;
for (int k = 1; k < 14; ++k)
{
if(s[k]) continue;
s[k]=1;
for (int l = 1; l < 14; ++l)
{
if(s[l]) continue;
if(k*l == j) {
printf("%d %d %d %d %d %d %d %d %d %d %d %d ",a,b,c,d,e,f,g,h,i,j,k,l); ans++;
}
}
s[k]=0;
}
s[j]=0;
}
s[i]=0;
}
s[h]=0;
}
s[g]=0;
}
s[f]=0;
}
s[e]=0;
}
s[d]=0;
}
s[c]=0;
}
s[b]=0;
}
s[a]=0;
}
printf("%d\n",ans);
return 0;
}

代码二:搜索----dfs
#include <stdio.h>
#define LL long long
#define INF 0x3f3f3f3f
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
int ans=0;
int vis[14],a[13];
void dfs(int x)
{
if( (x==4&& a[1]+a[2]!=a[3]) || (x==7&& a[4]-a[5]!=a[6]) || (x==10&& a[7]*a[8]!=a[9]) || (x==13&& a[11]*a[12]!=a[10])) return;
if(x ==13) {ans++; return;}
for(int i=1;i<=13;i++)
{
if(vis[i]) continue;
vis[i]=1;
a[x]=i;
dfs(x+1);
a[x]=-1;
vis[i]=0;
}
}
int main()
{
dfs(1);
printf("%d\n",ans);
return 0;
}
所有的符合条件:
1 8 9 13 6 7 2 5 10 12 3 4     1 8 9 13 6 7 2 5 10 12 4 3     1 8 9 13 6 7 3 4 12 10 2 5
1 8 9 13 6 7 3 4 12 10 5 2 1 8 9 13 6 7 4 3 12 10 2 5 1 8 9 13 6 7 4 3 12 10 5 2
1 8 9 13 6 7 5 2 10 12 3 4 1 8 9 13 6 7 5 2 10 12 4 3 1 8 9 13 7 6 2 5 10 12 3 4
1 8 9 13 7 6 2 5 10 12 4 3 1 8 9 13 7 6 3 4 12 10 2 5 1 8 9 13 7 6 3 4 12 10 5 2
1 8 9 13 7 6 4 3 12 10 2 5 1 8 9 13 7 6 4 3 12 10 5 2 1 8 9 13 7 6 5 2 10 12 3 4
1 8 9 13 7 6 5 2 10 12 4 3 6 7 13 9 1 8 2 5 10 12 3 4 6 7 13 9 1 8 2 5 10 12 4 3
6 7 13 9 1 8 3 4 12 10 2 5 6 7 13 9 1 8 3 4 12 10 5 2 6 7 13 9 1 8 4 3 12 10 2 5
6 7 13 9 1 8 4 3 12 10 5 2 6 7 13 9 1 8 5 2 10 12 3 4 6 7 13 9 1 8 5 2 10 12 4 3
6 7 13 9 8 1 2 5 10 12 3 4 6 7 13 9 8 1 2 5 10 12 4 3 6 7 13 9 8 1 3 4 12 10 2 5
6 7 13 9 8 1 3 4 12 10 5 2 6 7 13 9 8 1 4 3 12 10 2 5 6 7 13 9 8 1 4 3 12 10 5 2
6 7 13 9 8 1 5 2 10 12 3 4 6 7 13 9 8 1 5 2 10 12 4 3 7 6 13 9 1 8 2 5 10 12 3 4
7 6 13 9 1 8 2 5 10 12 4 3 7 6 13 9 1 8 3 4 12 10 2 5 7 6 13 9 1 8 3 4 12 10 5 2
7 6 13 9 1 8 4 3 12 10 2 5 7 6 13 9 1 8 4 3 12 10 5 2 7 6 13 9 1 8 5 2 10 12 3 4
7 6 13 9 1 8 5 2 10 12 4 3 7 6 13 9 8 1 2 5 10 12 3 4 7 6 13 9 8 1 2 5 10 12 4 3
7 6 13 9 8 1 3 4 12 10 2 5 7 6 13 9 8 1 3 4 12 10 5 2 7 6 13 9 8 1 4 3 12 10 2 5
7 6 13 9 8 1 4 3 12 10 5 2 7 6 13 9 8 1 5 2 10 12 3 4 7 6 13 9 8 1 5 2 10 12 4 3
8 1 9 13 6 7 2 5 10 12 3 4 8 1 9 13 6 7 2 5 10 12 4 3 8 1 9 13 6 7 3 4 12 10 2 5
8 1 9 13 6 7 3 4 12 10 5 2 8 1 9 13 6 7 4 3 12 10 2 5 8 1 9 13 6 7 4 3 12 10 5 2
8 1 9 13 6 7 5 2 10 12 3 4 8 1 9 13 6 7 5 2 10 12 4 3 8 1 9 13 7 6 2 5 10 12 3 4
8 1 9 13 7 6 2 5 10 12 4 3 8 1 9 13 7 6 3 4 12 10 2 5 8 1 9 13 7 6 3 4 12 10 5 2
8 1 9 13 7 6 4 3 12 10 2 5 8 1 9 13 7 6 4 3 12 10 5 2 8 1 9 13 7 6 5 2 10 12 3 4
8 1 9 13 7 6 5 2 10 12 4 3

7. 剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来,要求必须是连着的。

(仅仅连接一个角不算相连)

比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合格的剪取。

 

请你计算,一共有多少种不同的剪取方法。

 

请填写表示方案数目的整数。

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

第七届蓝桥杯大赛个人赛省赛C++ A组 题解+原题 (填空题)第七届蓝桥杯大赛个人赛省赛C++ A组 题解+原题 (填空题)第七届蓝桥杯大赛个人赛省赛C++ A组 题解+原题 (填空题)

答案:116