【蓝桥杯】2016题解

2023-04-03 1059 words 5 minutes views

⏰总用时：146/240 🎯总分：66/150

题号	时间	结果	满分	难度	备注
1	3	✅	3	🌕
2	3	✅	5	🌕
3	40	❌	11	🌓	🔸 直接用 next_permutation(a,a+10) 来枚举所有可能
4	5	✅	9	🌕
5	10	✅	13	🌓	🔸 消除末尾连续的 1 ： `x&(x+1)`
6	35	✅	15	🌕	🔹 dfs
7	30	❌	19	🌓	🔸 先枚举，再用dfs判断连通性 🔸 压缩：用一维数组存储2×3矩阵
8	10	✅	21	🌕	🔹 暴力枚举
9	5	❌	25	🌓	🔸 问题转化为求【最长回文子序列】 🔸 动态规划、带备忘录
10	5	❌	29

1 【填空】网友年龄

题目

某君新认识一网友。当问及年龄时，他的网友说： “我的年龄是个 2 位数，我比儿子大 27 岁, 如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”

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

提示：30 岁就是其中一种可能哦。

解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <bits/stdc++.h>
using namespace std;

int main(){
	int cnt=0;
	for(int i=1;i<=9;i++){
		for(int j=0;j<=9;j++){
			if(i*10+j-j*10-i==27){
				cout<< i*10+j <<" ";
				cnt++;
			}
		}
	}
	
	cout<<endl<<cnt;
} 

2 【填空】生日蜡烛

题目

某君从某年开始每年都举办一次生日 party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了 236 根蜡烛。

请问，他从多少岁开始过生日 party 的？请输出他开始过生日 party 的年龄数。

请输出他开始过生日 party 的年龄数。

解析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <bits/stdc++.h>
using namespace std;

int main(){

	for(int i=1;i<=200;i++){
		for(int j=i;j<=200;j++){
			if((i+j)*(j-i+1)/2==236){
				cout<< i<<" "<<j;
				return 0;
			}
		}
	}
	
	return 0;
} 

3 【填空】方格填数

题目

如下的 10 个格子，填入 0 ~ 9 的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）

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

1
2
3
4
5
6
7


   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+

解析

🟠 直接用 next_permutation(a,a+10) 来枚举所有可能

🟡 check 的条件比较多，小心下标标错❗❗❗

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <bits/stdc++.h>
using namespace std;

int main(){
	int cnt=0;
	int a[10]={0,1,2,3,4,5,6,7,8,9};
	do{
		if(abs(a[0]-a[1])!=1 && abs(a[0]-a[3])!=1 && abs(a[0]-a[4])!=1 && abs(a[0]-a[5])!=1 &&
		abs(a[1]-a[2])!=1 && abs(a[1]-a[4])!=1 && abs(a[1]-a[5])!=1 && abs(a[1]-a[6])!=1 &&
		abs(a[2]-a[5])!=1 && abs(a[2]-a[6])!=1 && abs(a[3]-a[4])!=1 && abs(a[3]-a[7])!=1 &&
		abs(a[3]-a[8])!=1 && abs(a[4]-a[5])!=1 && abs(a[4]-a[7])!=1 && abs(a[4]-a[8])!=1 &&
		abs(a[4]-a[9])!=1 && abs(a[5]-a[6])!=1 && abs(a[5]-a[8])!=1 && abs(a[5]-a[9])!=1 &&
		abs(a[6]-a[9])!=1 && abs(a[7]-a[8])!=1 && abs(a[8]-a[9])!=1)	cnt++;
	}while(next_permutation(a,a+10));
	cout<<cnt;
	
	return 0;
}

4 【填空】快速排序

题目

以下代码可以从数组 a[ ] 中找出第 k 小的元素。

它使用了类似快速排序中的分治算法，期望时间复杂度是 O(N) 的。

请仔细阅读分析源码，填写划线部分缺失的内容。

解析

 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


#include <stdio.h>

int quick_select(int a[], int l, int r, int k) {
    int p = rand() % (r - l + 1) + l;
    int x = a[p];
    {int t = a[p]; a[p] = a[r]; a[r] = t;}
    int i = l, j = r;
    while(i < j) {
        while(i < j && a[i] < x) i++;
        if(i < j) {
            a[j] = a[i];
            j--;
        }
        while(i < j && a[j] > x) j--;
        if(i < j) {
            a[i] = a[j];
            i++;
        }
    }
    a[i] = x;
    p = i;
    if(i - l + 1 == k) return a[i];
    if(i - l + 1 < k) return quick_select(a,l+1,i,k); //填空
    else return quick_select(a, l, i - 1, k);
}
    
int main()
{
    int a[100];
    int n;
    scanf("%d %d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    printf("%d\n", quick_select(a, 0, n-1, 5));
    return 0;
}

5 【填空】消除尾一

题目

下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0 如果最后一位是0，则原数字保持不变。

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

解析

🟠 消除末尾连续的 1 ： x&(x+1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <stdio.h>

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

int main()
{
    f(128+64+2);
    f(128+64+15);
    f(128+64+1);
    
    return 0;
}

6 【填空】寒假作业

题目

现在小学的数学题目也不是那么好玩的。看看这个寒假作业：

1
2
3
4


   □ + □ = □
   □ - □ = □
   □ × □ = □
   □ ÷ □ = □

每个方块代表 1~13 中的某一个数字，但不能重复。（加法，乘法交换律后算不同的方案）

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

解析

🟠 【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


#include <bits/stdc++.h>
using namespace std;

int cnt=0;
bool v[14]={false};		// 表示这个位置有没有遍历过 
int a[15]={0};
void dfs(int x){		// 当前正决定位置 x 放哪个数 
	if(x==14){			// 遍历到底，此情况成立 
		cnt++;return;
	}
	
	if(x==4 && a[1]+a[2]!=a[3])	return;
	if(x==7 && a[4]-a[5]!=a[6])	return;
	if(x==10 && a[7]*a[8]!=a[9])	return;
	if(x==13 && a[11]*a[12]!=a[10])	return;
	
	for(int i=1;i<=13;i++){		// 遍历所有的位置 
		if(v[i]==false){		// 这个位置没有放数字，可以放 x 
			v[i]=true;
			a[x]=i;				// x 这个位置放了 i
			dfs(x+1);			// 继续看下一个位置放什么数字 
			v[i]=false;
		}
	}
}

int main(){
	dfs(1);
	cout<<cnt; 
	
	return 0;
}

7 【填空】剪邮票

题目

如图, 有12张连在一起的12生肖的邮票。

现在你要从中剪下 5 张来，要求必须是连着的。（仅仅连接一个角不算相连）

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

解析

🟠 全排列；用 dfs 判断连通性。 从 12 个数中选 5 个数，遍历每种可能，再判断它们是否符合条件。从选取的第 1 个下标开始 dfs，如果最终剩余的 4 个下标都能被搜索到，说明这 5 个数是连通的。

🟡 压缩，用一维数组存储 3×4 的二维空间。 坐标在上、下、左、右方向上的变换为：-4，4，-1，1 。要注意左右边缘的情况要额外判断：4，8，5，9。

 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


#include <bits/stdc++.h>
using namespace std;

int d[4]={-4,4,-1,1};				// 索引的变换 
int v[13];							// 标记该索引是否访问过 
int i1,i2,i3,i4,i5,t,cnt;
void dfs(int index){
	if(cnt>=5)	return;
	
	for(int j=0;j<4;j++){
		if((d[j]==-1 && (index==5||index==9)) || (d[j]==1 && (index==4||index==8)))	continue;
		t=d[j]+index;
		if(t>=1 && t<=12 && v[t]==0 && (t==i2||t==i3||t==i4||t==i5)){
			v[t]=1;cnt++;
			dfs(t);
		}
	}
}

int main()
{
	int ans=0;
    for(i1=1;i1<=12;i1++){
    	for(i2=i1+1;i2<=12;i2++){
    		for(i3=i2+1;i3<=12;i3++){
    			for(i4=i3+1;i4<=12;i4++){
    				for(i5=i4+1;i5<=12;i5++){
    					cnt=1;memset(v,0,sizeof(v));
    					dfs(i1);
    					if(cnt==5)	ans++;
					}
				}
			}
		}
	}
    
    cout<<ans;
    return 0;
}

8 四平方和

题目

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 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<5×10^6$ )。

输出描述

要求输出 4 个非负整数，按从小到大排序，中间用空格分开。

解析

🟠 直接暴力枚举，在枚举过程中保证 i*i+j*j+k*k+r*r<=n 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    for(int i=0;i*i<=n;i++){
        for(int j=i;i*i+j*j<=n;j++){
            for(int k=j;i*i+j*j+k*k<=n;k++){
                for(int r=k;i*i+j*j+k*k+r*r<=n;r++){
                    if(i*i+j*j+k*k+r*r==n){
                        cout<<i<<" "<<j<<" "<<k<<" "<<r;
                        return 0;
                    }
                }
            }
        }
    }
    
    return 0;
}

9 密码脱落

题目

X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

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

输入描述

输入一行，表示现在看到的密码串（长度不大于 1000）。

输出描述

要求输出一个正整数，表示至少脱落了多少个种子。

解析

🟠 先从原串中找到一个 【最长回文子序列】 ，对于原串中不属于这个回文子序列的字符，只需在相应位置添加对称字符。 因此脱落的种子数=原串长度-最长回文子序列长度。问题转化为求原串的最长回文子序列。

🔵 【动态规划】 设 dp[i][j] 为从 i 到 j 的最长回文子序列长度，每次的判断条件为 s[i]==s[j] 。若相等，则 dp[i][j]=dp[i+1][j-1]+2 ，否则 dp[i][j]=max(dp[i+1][j],dp[i][j-1]) 。

🟢 用递归会超时，因此采用 自底向上的备忘录方法 。遍历的顺序是为了保证最先计算 dp[i][j] 里面的最长回文子序列。

 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 <bits/stdc++.h>
using namespace std;

int main(){
	string s;
	cin>>s;
	int len=s.length();				// 注意这里要加 static 或者调整堆栈大小！！！ 
	static int dp[1000][1000];		// dp[i][j]：从 i 到 j 的最长回文子序列长度 
	memset(dp,0,sizeof(dp));		// base case 
	for(int i=0;i<len;i++)
		dp[i][i]=1; 
	
	for(int i=len-1;i>=0;i--){		// 动态规划：计算 dp[i][j]
		for(int j=i+1;j<len;j++){	// 遍历的顺讯保证最先计算里面的 dp 
			if(s[i]==s[j])
				dp[i][j]=dp[i+1][j-1]+2;
			else
				dp[i][j]=max(dp[i+1][j],dp[i][j-1]); 
		}
	}
	
	int ans=len-dp[0][len-1];
	cout<<ans;
	return 0;
} 

Contents