第十二届蓝桥杯决赛 大学 B 组 C/C++ 做题记录

昨天才从外地返校,早上赶去做了核酸买了食物进考场,很困,不过比赛过程还是比较放松的,除了 C 题手残把模拟写错了,其他的算发挥正常吧。

A: 带宽

【问题描述】

小蓝家的网络带宽是 (200 Mbps),请问,使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 (MB) 的内容。

【我的解答】

(200Mbpsdiv 8=25MB/s)

B: 纯质数

【问题描述】

如果一个正整数只有 1 和它本身两个约数,则称为一个质数(又称素数)。

前几个质数是:(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。)

如果一个质数的所有十进制数位都是质数,我们称它为纯质数。例如:(2, 3, 5, 7, 23, 37) 都是纯质数,

(11, 13, 17, 19, 29, 31) 不是纯质数。当然 (1, 4, 35) 也不是纯质数。

请问,在 (1)(20210605) 中,有多少个纯质数?

【我的解答】

按照题意,先判断当前数知否为质数再逐位拆分看是否为质数,模拟即可。

#include <bits/stdc++.h>
using namespace std;
int p[]={0,1,4,6,8,9};
inline bool check(int x) {
	for (int i=2;i<=sqrt(x);i++)
		if (!(x%i)) return false;
	while (x) {
		for (int i=0;i<6;i++) 
			if ((x%10)==p[i]) return false;
		x/=10;
	}
	return true;
}
int main() {
	int cnt=0;
	for (int i=1;i<=20210605;i++)
		if (check(i)) cnt++;
	cout<<cnt;
	return 0;
}

答案:(1903)

C: 完全日期

【问题描述】

如果一个日期中年月日的各位数字之和是完全平方数,则称为一个完全日期。

例如:(2021)(6)(5) 日的各位数字之和为 (2 + 0 + 2 + 1 + 6 + 5 = 16),而 (16) 是一个完全平方数,它是 4 的平方。所以 2021 年 6 月 5 日是一个完全日期。

例如:(2021)(6)(23) 日的各位数字之和为 (2 + 0 + 2 + 1 + 6 + 2 + 3 = 16),是一个完全平方数。所以 (2021)(6)(23) 日也是一个完全日期。

请问,从 (2001)(1)(1) 日到 (2021)(12)(31) 日中,一共有多少个完全日期?

【我的解答】

这题写挂了是真的好生气啊,白送的 (10) 分无了。

挂的原因是开记录该月有几天的数组下标是从 (0) 开始的,但是我再遍历写的从 (1) 开始的,这样就把日期算少了。

懒得改了,上一个 (zkx) 的代码,答案 (977)

#include<bits/stdc++.h>
using namespace std;
int rn[5]= {29,28,28,28};
int rz[15]= {0,31,0,31,30,31,30,31,31,30,31,30,31};
bool pd(int x) {
	int sx=sqrt(x);
	return sx*sx==x;
}
int main() {
	int ans=0;
	for(int y=2001,ty; y<=2021; y++) {
		for(int m=1,tm; m<=12; m++) {
			for(int d=1,td,cnt; d<=(rz[m]?rz[m]:rn[y%4]); d++) {
				ty=y,tm=m,td=d,cnt=0;
				for(; ty; ty/=10)cnt+=ty%10;
				for(; tm; tm/=10)cnt+=tm%10;
				for(; td; td/=10)cnt+=td%10;
				if(pd(cnt))ans++;
			}
		}
	}
	cout<<ans<<endl;


	return 0;
}

D: 最小权值

【问题描述】

对于一棵有根二叉树 (T),小蓝定义这棵树中结点的权值 (W(T)) 如下:空子树的权值为 (0)

如果一个结点 (v) 有左子树 (L), 右子树 (R),分别有 (C(L))(C(R)) 个结点,则 (W(v) = 1 + 2W(L) + 3W(R) + {(C(L))}^2C(R))

树的权值定义为树的根结点的权值。

小蓝想知道,对于一棵有 (2021) 个结点的二叉树,树的权值最小可能是多少?

【我的解答】

(O(n^2)) 复杂度的树形 (DP)(dp(x)) 函数解决包括根节点在内共 (x) 节点的最小权值 ,(f[]) 数组进行记忆化处理

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
ll ans,f[3007];
ll dp(ll x) {
	if (f[x]!=-1) return f[x];
	ll minn=min(2*dp(x-1),3*dp(x-1))+1;
	for (ll i=1;i<x-1;i++)
		minn=min(minn,1+2*dp(i)+3*dp(x-1-i)+i*i*(x-1-i));
	return f[x]=minn;
}
int main() {
	memset(f,-1,sizeof(f));
	f[0]=0,cout<<dp(2021);
	return 0;
}

答案:(2653631372)

E: 大写

【问题描述】

给定一个只包含大写字母和小写字母的字符串,请将其中所有的小写字母转换成大写字母后将字符串输出。

【我的解答】

模拟。

#include <bits/stdc++.h>
using namespace std;
string in;
int main() {
	cin>>in;
	for (int i=0;i<(int)in.size();i++)
		if (in[i]>='a' && in[i]<='z')
			in[i]='A'+in[i]-'a';
	cout<<in;
	return 0;
}

F: 123

【问题描述】

小蓝发现了一个有趣的数列,这个数列的前几项如下:(1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ...)

小蓝发现,这个数列前 (1) 项是整数 (1),接下来 2 项是整数 (1)(2),接下来 (3) 项是整数 (1)(3),接下来 (4) 项是整数 (1)(4),依次类推。

小蓝想知道,这个数列中,连续一段的和是多少。

【输入格式】

输入的第一行包含一个整数 (T),表示询问的个数。

接下来 (T) 行,每行包含一组询问,其中第 (i) 行包含两个整数 (l_i)(r_i),表示

询问数列中第 (l_i) 个数到第 (r_i) 个数的和。

【输出格式】

输出 (T) 行,每行包含一个整数表示对应询问的答案。

【样例输入】

3
1 1
1 3
5 8

【样例输出】

1
4
8

【我的解答】

一道比较显然的数学题,但在考场上还是写写画画了不少时间,需要 (O(T)) 的时间复杂度才可以通过所有的数据。

区间内数字的和可以转化成两个端点的前缀和相减的问题,即 (sum(l,r)=sum(1,r)-sum(1,l-1))

我的做法是把每个 (1,2,3..i) 都视一组,这样第 (i) 组就有 (1~i)(i) 个数,我们考虑查询下标为 ([1,x]) 的数列和,

首先需要确定 (x) 是落在第几个组,通过二元一次方程的万能公式 (+) 周边探测可以 (O(1)) 找出 (c*(c+1)/2<x) 的最大的 (c)

这样数列和就被我们分割成了两个部分,第一个是前 (c) 段的完整求和,第二个是最后那段的部分求和

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll T,l,r;
inline ll readint() {
	ll X=0,w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
inline ll te(ll x) { return x<0?0:x*(x+1)/2; } // 1,2,3..n 求和 
inline ll qe(ll x) { return x*(x+1)*(2*x+1)/6; } // 1^2+2^2+3^2..n^2 求和 
ll func(ll x) {
	 
	int c=(sqrt(8*x+1)-1)/2;
	// 写这么多判断是去除开方和除造成的误差
	// 要找到比 x 小的最大的 c*(c+1)/2 的 c 
	if (te(c+4)<x) c=c+4;
	else if (te(c+3)<x) c=c+3;
	else if (te(c+2)<x) c=c+2;
	else if (te(c+1)<x) c=c+1;
	else if (te(c)<x) c=c;
	else if (te(c-1)<x) c=c-1;
	else if (te(c-2)<x) c=c-2;
	else if (te(c-3)<x) c=c-3;
	else if (te(c-4)<x) c=c-4;
	return (qe(c)+te(c))/2+te(x-te(c));
}
int main() {
	T=readint();
	while (T--) {
		l=readint(),r=readint();
		cout<<func(r)-func(l-1)<<'
';
	}
	return 0;
}

G: 异或变换

【问题描述】

小蓝有一个 (01)(s = s1 s2 s3 · · · sn)

以后每个时刻,小蓝要对这个 (01) 串进行一次变换。每次变换的规则相同。

对于 (01)(s = s1 s2 s3 · · · sn),变换后的 (01)(s'=s_1's_2's_3' · · · s_n')

(s_1'=s1;)

(s_i'=s_{i-1}⊕s_i)

其中 (a ⊕ b) 表示两个二进制的异或,当 (a)(b) 相同时结果为 (0),当 (a)(b) 不同时结果为 (1)

请问,经过 (t) 次变换后的 (01) 串是什么?

【输入格式】

输入的第一行包含两个整数 (n, t),分别表示 (01) 串的长度和变换的次数。

第二行包含一个长度为 (n)(01) 串。

【输出格式】

输出一行包含一个 (01) 串,为变换后的串。

【样例输入】

5 3
10110

【样例输出】

11010

【样例说明】

初始时为 (10110),变换 (1) 次后变为 (11101),变换 (2) 次后变为 (10011),变换 (3) 次后变为 (11010)

【评测用例规模与约定】

对于 (40\%) 的评测用例,(1 ≤ n ≤ 100, 1 ≤ t ≤ 1000)

对于 (80\%) 的评测用例,(1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9)

对于所有评测用例,(1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18})

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string a;
ll n,t,v[107];
int main() {
	v[0]=1;
	for (ll i=1;i<=60;i++) v[i]=v[i-1]<<1;
	cin>>n>>t;
	for (ll i=1;i<=60;i++) {
		if (n>v[i-1] && n<=v[i]) { t%=v[i]; break; }
	}
	if (n==1) t=0; cin>>a;
	while (t--) {
		for (ll i=n-1;i>=1;i--) {
			if (a[i]=='1' && a[i-1]=='0') a[i]='1';
			else if (a[i]=='0' && a[i-1]=='1') a[i]='1';
			else a[i]='0';
		}
	}
	cout<<a<<endl;
	return 0;
}

H: 二进制问题

【问题描述】

小蓝最近在学习二进制。他想知道 (1)(N) 中有多少个数满足其二进制表示

中恰好有 (K)(1)。你能帮助他吗?

【输入格式】

输入一行包含两个整数 (N)(K)

【输出格式】

输出一个整数表示答案。

【样例输入】

7 2

【样例输出】

3

【评测用例规模与约定】

对于 (30\%) 的评测用例,(1 ≤ N ≤ 106, 1 ≤ K ≤ 10)

对于 (60\%) 的评测用例,(1 ≤ N ≤ 2 × 109, 1 ≤ K ≤ 30)

对于所有评测用例,(1 ≤ N ≤ 1018, 1 ≤ K ≤ 50)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,ans,v[107],C[107][107];
void init() {
	v[0]=1,C[0][0]=C[1][0]=C[1][1]=1; 
	for (ll i=1;i<=100;i++) v[i]=v[i-1]<<1;
	for (ll i=2;i<=100;i++) 
		for (ll j=0;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
}
void func(ll p,ll r,ll sum) {
	if (sum>n) return;
	if (!r) { ans++; return; }
	for (ll i=p-1;i>=0 && i+1>=r;i--)
		func(i,r-1,sum+v[i]); 
}
int main() {
	init(); cin>>n>>k;
	for (ll i=59;i>=0;i--) {
		if (v[i]-1==n) { ans+=C[i][k]; break; } 
		else if (v[i]-1<n) {
			ans+=C[i][k];
			func(i,k-1,v[i]);
			break;
		} 
	}
	cout<<ans;
	return 0;
}

I: 翻转括号序列

【问题描述】

给定一个长度为 (n) 的括号序列,要求支持两种操作:

  1. ([L_i, R_i]) 区间内(序列中的第 (L_i) 个字符到第 (R_i) 个字符)的括号全部翻转(左括号变成右括号,右括号变成左括号)。

  2. 求出以 (L_i) 为左端点时,最长的合法括号序列对应的 (R_i) (即找出最大的 (R_i) 使 ([Li, Ri]) 是一个合法括号序列)。

【输入格式】

输入的第一行包含两个整数 (n, m),分别表示括号序列长度和操作次数。

第二行包含给定的括号序列,括号序列中只包含左括号和右括号。

接下来 (m) 行,每行描述一个操作。如果该行为 (“1 Li Ri”),表示第一种操作,

区间为 ([L_i, R_i]) ;如果该行为 (“2 L_i”) 表示第二种操作,左端点为 (L_i)

【输出格式】

对于每个第二种操作,输出一行,表示对应的 (R_i)。如果不存在这样的 (R_i),请输出 (0)

【样例输入】

7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

【样例输出】

4
7
0
0

【评测用例规模与约定】

对于 (20\%) 的评测用例,(n, m ≤ 5000)

对于 (40\%) 的评测用例,(n, m ≤ 30000)

对于 (60\%) 的评测用例,(n, m ≤ 100000)

对于所有评测用例,(1 ≤ n ≤ 10^6, 1 ≤ m ≤ 2 × 10^5)

#include <bits/stdc++.h>
using namespace std;
int n,m,len;
string s;
int main() {
	cin>>n>>m>>s,len=(int)s.size();
	while (m--) {
		int opt; cin>>opt;
		if (opt==1) {
			int l,r;
			cin>>l>>r,l--,r--;
			for (int i=l;i<=r;i++) {
				if (s[i]=='(') s[i]=')';
				else s[i]='(';
			}
		}
		else {
			int l,c=1,ans=0; cin>>l,l--;
			if (s[l]==')') { printf("0
"); continue; }
			for (int i=l+1;i<len;i++) {
				if (s[i]=='(') c++; else c--;
				if (!c) ans=i; else if (c<0) break; 
			}
			if (!ans) printf("0
");
			else printf("%d
",ans+1);
		}
	}
	
	return 0;
}

J: 异或三角

【问题描述】

给定 (T) 个数 (n_1, n_2, · · · , n_T),对每个 ni 请求出有多少组 a, b, c 满足:

(1. 1 ≤ a, b, c ≤ ni;)

(2. a ⊕ b ⊕ c = 0),其中 ⊕ 表示二进制按位异或;

(3.) 长度为 (a, b, c) 的三条边能组成一个三角形。

【输入格式】

输入的第一行包含一个整数 (T)

接下来 (T) 行每行一个整数,分别表示 (n_1, n_2, · · · , n_T)

【输出格式】

输出 (T) 行,每行包含一个整数,表示对应的答案。

【样例输入】

2
6
114514

【样例输出】

6
11223848130

【评测用例规模与约定】

对于 (10\%) 的评测用例,(T = 1, 1 ≤ n_i ≤ 200)

对于 (20\%) 的评测用例,(T = 1, 1 ≤ n_i ≤ 2000)

对于 (50\%) 的评测用例,(T = 1, 1 ≤ n_i ≤ 2^{20})

对于 (60\%) 的评测用例,(1 ≤ T ≤ 100000, 1 ≤ n_i ≤ 2^{20})

对于所有评测用例,(1 ≤ T ≤ 100000, 1 ≤ n_i ≤ 2^{30})

#include <bits/stdc++.h>
#define MAXN 2007
using namespace std;
int T,n,ans=0;
int main() {
	scanf("%d",&T);
	for (int i=1;i<=T;i++) scanf("%d",&n);
	for (int a=1;a<=n;a++) {
		for (int b=1;b<=n;b++) {
			int c=0^a^b;
			if (c>=1 && c<=n && a+b>c && a+c>b && b+c>a) ans++;
		}
	}
	cout<<ans;
	return 0;
}
原文地址:https://www.cnblogs.com/zhwer/p/14853421.html