蓝桥杯真题练习-2

2023-10-18

Word count: 4k | Reading time≈ 17 min

蓝桥杯真题练习

第七天

动态规划

【真题练习】蓝肽子序列

$\textcolor{red}{分析:}$

一个蓝肽表示方法为：首字母为大写，后面为小写字母；（一个蓝肽就相当于是一个单词）

公共蓝肽子序列的长度为：两个字符串中相同蓝肽的数量；

本题是经典的最长公共子序列(LCS)的变形题，先将每个蓝肽存储在数组中，再使用动态规划解决；

解决代码：

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

const int N = 1e3+5;

string s1, s2;
string a[N], b[N];
int dp[N][N]; // 第一个N代表的是第一个字符串s1单词化后的a数组，第二个N代表的是第二个字符串s2单词化后的b数组 

int main() {
	cin>>s1>>s2;
	// 对蓝肽序列以蓝肽为单位进行处理
	int n=0, m=0;
	for(int i=0;i<s1.length();){
		if(s1[i]>='A'&&s1[i]<='Z')a[n] += s1[i++];// 存储首字母 
		while(s1[i]>='a'&&s1[i]<='z'){// 存储后面的小写字母 
			a[n] += s1[i++];
		}
		n++;// 存储下一个蓝肽 
	}
	for(int i=0;i<s2.length();){
		if(s2[i]>='A'&&s2[i]<='Z')b[m] += s2[i++];// 存储首字母 
		while(s2[i]>='a'&&s2[i]<='z'){// 存储后面的小写字母 
			b[m] += s2[i++];
		}
		m++;// 存储下一个蓝肽 
	}
	// 动态规划处理
	dp[0][0] = 0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i-1] == b[j-1]){
				dp[i][j] = dp[i-1][j-1]+1;
			}else{
				dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
			}
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;	
}

【真题练习】合唱队形

$\textcolor{red}{分析：}$

本质是最长上升子序列(LIS)问题，但是本题不是单调上升，而是先上升在下降的形式，因此可以先正向运用一次LIS，之后再反向运用一次LIS；

最后将正向与反向的结果一一对应相加减1(因为自己计算了两次)，再取其中最大的即为队列中的最大人数。

解决代码：

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

const int N =105;
int h[N], dp1[N], dp2[N];
int n;

int main() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>h[i];
		dp1[i] = 1;
		dp2[i] = 1;
	}// 初始化
	//正向遍历
	for(int i=2;i<=n;++i){
		for(int j=1;j<i;++j){
			if(h[j]<h[i]){
				dp1[i] = max(dp1[i], dp1[j]+1);
			}
		}
	} 
	//反向遍历
	for(int i=n-1;i>0;--i){
		for(int j=n;j>i;--j){
			if(h[i]>h[j]){
				dp2[i] = max(dp2[i], dp2[j]+1);
			}
		}
	} 
	int max_num = 0;
	for(int i=1;i<=n;++i){
		max_num = max(max_num, dp1[i]+dp2[i]-1);
	}
	cout<<n - max_num;// 需要出列的人数 
	return 0;
}

【真题练习】字符串编辑距离

$\textcolor{red}{分析：}$

本题与LCS相似当又有很大的不同；

使用编辑距离的方式解决（详见：C++经典问题：编辑距离）；

由于是包含关系，并不是相等关系，所以当S多余T是，不需要进行插入操作。

所以这个题目不考虑插入的那个状态转移即可，同时本题只计修改字符的次数，不计删除字符的操作次数，因此删除字符的状态转移中不+1。

解决代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 99999 
const int N = 1e3+10;
string s, t;
int dp[N][N];

// 初始化 
void init(){
	for(int i=0;i<=s.size();++i)dp[i][0] = 0;
	for(int j=1;j<=t.size();++j)dp[0][j] = INF;// 这里不能用INT_MAX，因为后面有+1操作，这样会使得INT_MAX+1为负数,那么min求得的就是负数,不是最终答案 
}


int main() {
	cin>>s>>t;
	init();
	for(int i=1;i<=s.size();++i){
		for(int j=1;j<=t.size();++j){
			if(s[i-1] == t[j-1]){// 相同，不做修改 
				dp[i][j] = dp[i-1][j-1];
			}else{// 不相同，比较修改和删除方式中最小的修改次数 
				dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]);// 只计修改字符的次数，不计删除字符的操作次数
			}
		}
	}
	cout<<dp[s.size()][t.size()];
	return 0;
}

第八天

简单数论

【真题练习】阶乘约数

$\textcolor{red}{分析：}$

正约数是指一个正整数除了自身以外的所有因数。例如，6的正约数是1,2,3。

我们可以利用正约数来求一个数的因数个数和因数之和。例如，对于正整数n，它的因数个数为d(n)，可以通过以下公式计算(约数定理)：

d(n) = (k+1)(l+1)(m+1)…，其中n = 2^k * 3^l * 5^m * …

也就是将n分解质因数后，求出每个质因子的指数并加1，然后将它们相乘即可。

另外，如果我们已知一个正整数n的所有正约数，可以通过以下公式求出它们的和s(n)：

s(n) = (1+a1)(1+a2)(1+a3)…(1+ak)，其中n = p1^a1 * p2^a2 * p3^a3 * …

也就是将n分解质因数后，将每个质因子的指数加1，然后将它们相乘再加1即可。

需要注意的是，这里的正约数不包括1，因为1是所有正整数的因数。

计算代码：

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

int cnt[105];// 默认初始化为全0 
using ll = long long;

int main() {
	for(int i=1;i<=100;++i){// 100的阶乘的因数 
		int x = i;
		for(int j=2;j*j<=x;++j){
			if(x%j==0){
				while(x%j==0)x /= j, cnt[j]++;// 计算j的幂次 
			}
		}
		if(x>1)cnt[x]++;
	}
	ll ans = 1;
	for(int i=1;i<=100;++i){
		if(cnt[i]>0) ans *= (cnt[i]+1);
	} 
	cout<<ans;
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<39001250856960000;
  return 0;
}

【真题练习】质因子个数

$\textcolor{red}{分析：}$

首先是要有判断质数的方法；质数只能被1和本身整除，利用这个性质进行试除法判断是否为质数；

直接对数字 n 进行质因数分解即可。 i 从 2 开始枚举判断是否为n的因子：如果 i是因子，则把 n 不断除以 i 直到无法整除为止。最终如果 n!=1 ，说明在最后的 n 为质数，此时答案加 1。

也可以使用大数素数分解——Pollard_rho 算法：这是经典的大数素数分解算法模板，此处不展开赘述，可参考：

Miller-Rabin 素性测试：https://blog.csdn.net/weixin_43914593/article/details/107290663

Pollard_rho 大数素数分解：https://blog.csdn.net/weixin_43914593/article/details/107345370

解决代码：

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

using ll = long long;

int main() {
	ll n, ans = 0;
	cin>>n; 
	for(int i=2;i<=n/i;++i){
		int num = 0;
		while(n%i==0){
			num++;
			n /= i;
		}
		if(num>0)ans++;
	}
	if(n>1)ans++;
	cout<<ans;
	return 0;
}
// 以上代码原理没有看懂???

【真题练习】等差数列

$\textcolor{red}{分析：}$

如何确认等差数列中d的取值，首先将序列所有数升序排序，之后计算相邻两个数之间的差，将得到的所有的差值求最大公约数就是等差数列的d；

需要注意，如果所有的数相同，它也是等差数列，这种情况下就特殊判断；

解决代码：

第九天

思维训练

【真题练习】裁纸刀

$\textcolor{red}{分析：}$

根据题意易知：4+19+20*21=443；

这道题的思维很简单，一看就懂。

计算代码：

#include<bits/stdc++.h>
using namespace std;
const int R = 20, C = 22;// 定义行和列 
// 边缘必定要裁4刀 
// 20行中行与行之间需要裁1刀，也就是R-1
// 每一行中的22个二维码之间需要裁21刀，也就是C-1
// 所有行就需要R*（C-1） 
int main() {
	cout<<(4+R-1+R*(C-1));
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<443;
  return 0;
}

【真题练习】蛇形填数

$\textcolor{red}{分析：}$

$\textcolor{red}{左上三角形与右下三角形的填充规则是不同的}$ ；但是本题说明了填充的矩阵无限大，也就是说一直填充的都是上三角形，所以只需要用上三角形的填充规则：右，左下，下，右上即可；

这里可以使用定义方向数组dx与dy的方式或是while循环的方式来解决。

计算代码：

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

int M[100][100], row=0, col=0, cnt = 1;// 定义初值 

int main() {
	M[0][0] = cnt++;// 填第一个数 
	while(!M[19][19]){// 还未得到目标值 
		// 向右
		M[row][++col] = cnt++;
		// 向左下
		while(col){
			M[++row][--col] = cnt++;
		}
		// 向下
		M[++row][col] = cnt++;
		// 向右上 
		while(row){
			M[--row][++col] = cnt++;
		}
	}
	cout<<M[19][19];
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<761;
  return 0;
}

【真题练习】最大降雨量

$\textcolor{red}{分析：}$

分析，我们先理解题意，我们如果假设每周的中位数是a,b,c,x,e,f,g，这七个数是这七张

法术符数字上的中位数(即为能量)。降雨量为这七个数的中位数，我们要的是x最大，假设这此时x最大，我们可以看看需要满足什么条件。

七个数从小到大排列第四周x后三天要比x大，第五周第六周第七周的后四天都要比x大，所以共要有15个数比x大。

计算代码：

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

int a[7];
// 既然是求7周能量的中位数的最大值。那么每周能量的中位数保证最大。
// 从能取得的最大的中位数排起：最大的数和最小的数组合
// 1 2 3 46 47 48 49   => 中位数46
// 4 5 6 42 43 44 45   => 中位数42
// 7 8 9 38 39 40 41   => 中位数38
// 10 11 12 34 35 36 37  => 中位数34
// 13 14 15 30 31 32 33  => 中位数30
// 16 17 18 26 27 28 29  => 中位数26
// 19 20 21 22 23 24 25  => 中位数22
// 7周能量中位数最大为34
int main() {
	a[0] = 49 - 3;
	for(int i=1;i<7;++i){
		a[i] = a[i-1] - 4;// 减去4是因为上一个中位数与当前中位数之间的距离 
	}
	cout<<a[3];
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
/*
  * [][][][a][][][]
  * [][][][b][][][]
  * [][][][c][][][]
  * [][][][max][][][]
  * [][][][d][][][]
  * [][][][e][][][]
  * [][][][f][][][]
  * 
  * 此题意思为将1至49分为7组数字，求取七组数字中每组数字的中位数所构成的数列的中位数的最大值
  * 即如图所示，最大化[max]
  * 49个数字中需要比[max]大的有[max]行的后三位，d、e、f行的后四位，共3+3*4=15位
  * 结果为：49-15=34
  * */
  cout << 34 << endl;
}

【真题练习】排序

$\textcolor{red}{分析：}$

考虑冒泡排序的复杂度，对于拥有N个字母的字符串，最多需要交换N * (N-1)/2次（完全乱序时）；

易知N=15时，有15 * 14/2=105，即满足100次交换所需的最短字符串有15个字母；

要求字典序最小，那么显然要取a~o这15个字典序最小的字母；

逆向思考，目标字符串经过100次交换后，得到正序字符串abcdefghijklmno，而完全逆序的字符串onmlkjihgfedcba变成正序字符串需要105次交换，那么将完全逆序的字符串交换5次后，便能得到答案。而要求字典序最小，那么将j交换5次提到字符串最前面，就得到了最小的情况。

计算代码：

#include<bits/stdc++.h>
using namespace std;
	
int main() {
	int n = 0;
	while(n*(n-1)/2<100)n++;
	int m = n*(n-1)/2 - 100;// n*(n-1)/2是完全逆序的交换次数，减去100是为了得到需要提前交换的次数，从而使得得到的字符串只需要交换100次 
	char array[n];
	for(int i=0;i<n;++i){// 得到完全逆序的字符串 
		array[i] = 97 + n - i - 1;
	}
	// 针对完全逆序的字符串，将其变为符合交换次数刚好为100的字符串
	for(int i=m;i>0;--i){
		while(array[i]<array[i-1]){
			swap(array[i], array[i-1]);
		}
	} 
	for(int i=0;i<n;++i){
		cout<<array[i];
	}
	return 0;
}

解决代码：

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  cout<<"jonmlkihgfedcba";
  return 0;
}

第十天

图论

【真题练习】聪明的猴子

解决代码：

第十一天

排序算法

【真题练习】双向排序

$\textcolor{red}{分析：}$

这里需要注意的是对于p与q的理解：当p=0时表示的是前q个数为降序；当p=1时表示的是从第q位数开始到最后一位数为升序；

对于60%的数据使用sort函数或是使用权值数组的方式可以解决；

解决算法：

第十二天

组合数学

【真题练习】数列求值

$\textcolor{red}{分析：}$

注意如果直接计算的话会发现后面的数值会很大，导致数据溢出，所以根据题意，我们可以简化计算过程，因为只需要求得最后4位数，那么我们就截取所有数对10000的余数，这样就能够既达到目的又不会导致数据溢出。

解决代码：

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

int main() {
	int a = 5, b = 9, c = 17;
	for(int i=8;i<=20190324;++i){
		int t = (a+b+c)%10000;
		a = b;// 往后移动一位 
		b = c;
		c = t;
	} 
	cout<<c;
    // 请在此输入您的代码
  	// cout<<4659;
	return 0;
}

【真题练习】杨辉三角

$\textcolor{red}{分析：}$

因为杨辉三角是一个二项式展开的图形化表示，其中每个数字表示对应二项式系数的值， $\frac{n\times(n+1)}{2}=1+2+3+……+n$ ;

根据N最大可取10亿，因此可以知道该数出现的位置远小于10亿，根据10亿=n*(n+1)/2，可以得到大致的位置范围1~44723(向上取整)；

解决代码：

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

using ll = long long;
ll a[44723];

int main() {
	ll N;
	cin>>N;
	if(N==1){
		cout<<1;
		return 0;
	}
	a[0] = 1;// a[0] = 1,表示的是第1列 
	for(int i=3;i<44723;++i){// 控制行 
		for(int j=i/2;j>0;--j){// 控制列 
			if(j==i/2&&i%2==1){// 只计算左半边即可,不然要超时 
				a[j] = a[j-1] * 2;
			}else{
				a[j] = a[j-1] + a[j];
			}
			if(a[j]==N){
				cout<<(i-1)*i/2+j+1;// 第一次出现的位置 
				return 0;
			}
		}
	}
	cout<<N*(N+1)/2+2;
	return 0;
}

【真题练习】组合数问题

$\textcolor{red}{分析：}$

根据定理：C(n,k) = C(n-1,k) + C(n-1,k-1）定义递归函数；

解决代码：

#include <stdio.h>
#include <stdlib.h>

int f(int n, int m)
{
    if(m>n) return 0;
    if(m==0) return 1;

    return f(n-1,m-1) + f(n-1,m);
}

int main(int argc, char* argv[])
{
    printf("%d\n", f(10,3));
    printf("%d\n", f(5,3));
    printf("%d\n", f(5,2));

    return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.