2021第十二届蓝桥杯决赛C++B组

- - 带宽
  - 纯质数
  - 完全日期
  - 最小权值
  - 大写
  - 123
  - 异或变换
  - 二进制问题
  - 翻转括号序列
  - 异或三角

带宽

【问题描述】
小蓝家的网络带宽是 200 Mbps，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 MB 的内容。
【答案提交】
说明：这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要提交能输出正确答案的程序即可。

经常搞混
位 bits
字节Bytes
字words
32位计算机：1字=32位=4字节，64位计算机：1字=64位=8字节
1字节Bytes = 8 位bits

正解：200 Mb / 8 = 25 MB

纯质数

【题目描述】
如果一个正整数只有 11和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：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中，有多少个纯质数。

正解：1903

暴力

#include
using namespace std;
typedef long long LL;
LL ans;
bool check1(int k){
	if(k == 1) return false;
	if(k == 2) return true;
	int m = sqrt(k);
	for(int i = 2; i <= m; i++)
		if(k % i == 0)
			return false;
	return true;
}
bool check2(int k){
	while(k){
		int m = k % 10;
		if(m == 0 || m == 1 || m == 4 || m == 6 || m == 8 || m == 9)//注意这里位数位0得情况	
			return false;
		k /= 10;
	}
	return true;
}
int main(){
	for(int i = 1; i <= 20210605; i++){
		if(check1(i) && check2(i)){
			ans++;
//			cout << i << endl;
		}
			
	}
//	check1(13);
//	check2(13);
	cout << ans;
	return 0;
}

完全日期

【问题描述】
如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。
例如: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日中，一共有多少个完全日期?

暴力
正解：977

#include
using namespace std;
typedef long long LL;
LL ans;
int date[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//判断日期是否有效 
bool check1(int i){
	int y = i / 10000 , m = i / 100 % 100, d = i % 100;
	if(m <= 0 || m > 12) return false;
	if(m != 2 && ( d <= 0 || d > date[m])) return false;
	else if(m == 2){
		bool leap = (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0));
		if(d <= 0 || d > (date[m] + leap)) return false; 
	} 
	return true;
}
//判断是否是完全日期
bool check2(int n){
	int k = sqrt(n);
	return k * k == n;
} 
int main(){
	for(int i = 20010101; i <= 20211231; i++){
		if(check1(i)){
			int sum = 0, t = i;
			while(t){
				sum += (t % 10);
				t /= 10;
			}
			if(check2(sum)){
				ans++;
				//cout << i << endl; 
			} 
				
		}
	}
	cout << ans;
	return 0;
}

最小权值

【问题描述】
对于一棵有根二叉树T，小蓝定义这棵树中结点的权值W(T’)如下:空子树的权值为0。
如果一个结点v有左子树L,右子树R，分别有C(L)和C®个结点，则wv)= 1＋2W(L)+3W®+(C(L))"C( R)。
树的权值定义为树的根结点的权值。
小蓝想知道，对于一棵有2021个结点的二叉树，树的权值最小可能是多少?

动态规划
大佬思路和代码
正解：2653631372

#include
using namespace std;
typedef long long LL;
LL dp[10010];
int main(){
	//dp[i]代表有i个结点来组成这棵树
	memset(dp, 0x7f, sizeof dp);
	dp[0] = 0;
	for(int i = 1; i <= 2021; i++){
		for(int j = 0; j < i; j++)//j是枚举所有左子树中结点的个数
			dp[i] = min(dp[i], 1 + 2 * dp[j] + 3 * dp[i - j - 1] + j * j * (i - j - 1));
	}
	cout << dp[2021];
	return 0;
}

大写

【问题描述】
给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母转换成大写字母后将字符串输出。
【输入格式】
输入一行包含一个字符串。
【输出格式】
输出转换成大写后的字符串。
【样例输入1】
LanQiao
【样例输出1】
LANQIAO
【评测用例规模与约定】
对于所有评测用例，字符串的长度不超过100。

#include
using namespace std;
typedef long long LL;
int main(){
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++)
		s[i] = toupper(s[i]);
	cout << s;
	return 0;
}

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;和r;，表示询问数列中第l;个数到第r;个数的和。
【输出格式】
输出T行，每行包含一个整数表示对应询问的答案。
【样例输入】
31 11 35 8
【样例输出】
1
4
【评测用例规模与约定】
对于10%的评测用例，1≤T ≤30,1≤l≤r ≤ 100。
对于20%的评测用例，1≤T ≤ 100,1 ≤ l ≤r; ≤1000。
对于40%的评测用例，1≤T ≤ 1000,1 ≤l≤ri≤ 10⁶。
对于70%的评测用例，1≤T ≤10000,1 ≤l≤r ≤10⁹。
对于80%的评测用例，1≤T ≤ 1000,1 ≤ l≤ri ≤10¹²。
对于90%的评测用例，1≤T ≤ 10000,1≤l,≤r ≤10¹²。
对于所有评测用例，1≤T ≤100000,1 ≤ l≤ri≤10¹²。

参考题解

#include
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
LL a[N], s[N];
int main(){
    for(int i = 1; i < N; i++)
        a[i] = 1ll * i * (i + 1) / 2;
        //每个a相当于每次重新开始数列得个数
        //比如a[1] = 1，a[2] = 3, a[3] = 6，方便后面用二分进行位置查找
    for(int i = 1; i < N; i++)
        s[i] = s[i - 1] + 1ll * i * (i + 1) / 2;
        //求每个重新开始数列的总和
        //如a[1] = 1, a[2] = 1 + 2, a[3] = 1 + 2 + 3
    LL n, l, r;
    cin >> n;
    while(n--){
        cin >> l >> r;
        l--;
        //upper_bound第一个大于等于的位置
        //lower_bound第一个大于的位置
        LL x = upper_bound(a + 1, a + N, l) - a - 1;
        LL y = upper_bound(a + 1, a + N, r) - a - 1;
        LL u = l - a[x], v = r - a[y];
        //u表示左边超出多少要减的，v表示右边超过多少要加的
        LL ans = s[y] + v * (v + 1) / 2 - s[x] - u * (u + 1) / 2;
        cout << ans << endl;
    }
    
    return 0;
}

异或变换

找规律
大佬题解

#include
using namespace std;
typedef long long LL;
int main(){
	int n;
	LL t;
	cin >> n >> t;
	LL k = 1; 
	while(k < n) k *= 2;
	//规律是当大于等于n的一个2的整数次幂情况下，必定存在循环 
	t %= k;
	string s;
	cin >> s;
	for(int i = 0; i < t; i++){
		string tp = s;
		for(int j = 1; j < n; j++)
			s[j] = (tp[j] == tp[j - 1] ? '0' : '1');
			//s[i] = (tp[i - 1] - '0') ^ (tp[i] - '0') + '0';这样也可以异或
	}
	cout << s;
	return 0;
}

二进制问题

【问题描述】
小蓝最近在学习二进制。他想知道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
using namespace std;
typedef long long LL;
LL n, k, ans;

int main(){
	cin >> n >> k;
	bitset<100> S;
	LL flag = 0;
	for(int i = 1; i <= n; i++){
		S = i;
		for(int i = 0; i <= 100; i++)
			if(S[i])
				flag++;
		if(flag == k)
			ans++;
		flag = 0;
	}
	cout << ans;
	return 0;
}

使用数位DP
数位DP
参考文章

#include
using namespace std;
typedef long long LL;
const int N = 60;
LL r, k;
LL f[N][N]; 
void init(){
	for(int i = 0; i < N; i++)
		for(int j = 0; j <= i; j++){
			if(!j) f[i][j] = 1;
			else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
		}
} 
LL dp(LL n){
	vector nums;
	while(n) nums.push_back(n % 2), n /= 2;
	
	LL res = 0;
	LL last = 0;
	for(int i = nums.size() - 1; i >= 0; i--){
		int x = nums[i];
		if(x){
			
			res += f[i][k - last];
			
			last++;
			
			if(last > k) break;
		}
		
		if(!i && last == k) res++;
	}
	return res;
}
int main(){
	cin >> r >> k;
	init();
	cout << dp(r);
	return 0;
}

翻转括号序列

异或三角

2021第十二届蓝桥杯决赛C++B组

C/C++/C#相关栏目本月热门文章