第十二届蓝桥杯国赛C++大学B组
一、带宽
问题描述
小蓝家的网络带宽是200Mbps，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少MB的内容。
1MB = 8Mbps
答案
25
二、纯质数
问题描述
如果一个正整数只有 1 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
Code
#include<iostream>
using namespace std;
bool check(int x)
{
while(x)
{
if(x % 10 == 0 || x % 10 == 1 || x % 10 == 4 || x % 10 == 6 || x % 10 == 8 || x % 10 == 9) return false;
x /= 10;
}
return true;
}
bool is_prime(int x)
{
for(int i = 2;i <= x / i;i ++)
{
if(x % i == 0) return false;
}
return true;
}
int ans;
int main()
{
for(int i = 2;i <= 20210605;i ++)
if(check(i))
if(is_prime(i))
ans ++;
cout<<ans<<endl;
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
Code
#include<iostream>
#include<cmath>
using namespace std;
int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans;
bool check(int i,int j,int k)
{
int x = 0;
while(i){
x += i % 10;
i /= 10;
}
while(j){
x += j % 10;
j /= 10;
}
while(k){
x += k % 10;
k /= 10;
}
int y = sqrt(x);
if(y * y == x) return true;
else return false;
}
int main()
{
for(int i = 2001;i <= 2021;i ++)
for(int j = 1;j <= 12;j ++)
{
int x = month[j];
if(((i % 4 == 0 || i % 100 == 0) && i % 400 != 0) && j == 2)
x = month[j] + 1;
for(int k = 1;k <= x;k ++)
if(check(i,j,k))
ans ++;
}
cout<<ans<<endl;
}
四、最小权值
问题描述
对于一棵有根二叉树 T，小蓝定义这棵树中结点的权值 W(T) 如下：
空子树的权值为 0。
如果一个结点 v 有左子树 L, 右子树 R，分别有 C(L) 和 C(R) 个结点，则：
W(v)=1+2W(L)+3W(R)+(C(L))2C(R)。树的权值定义为树的根结点的权值。
小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多少？
答案
2653631372
Code
#include<iostream>
#include<cstring>
using namespace std;
long long f[2022]; //f[i]表示权值为i的二叉树的最小权值
int main()
{
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 1;i <= 2021;i ++)
{
for(int j = 0;j < i;j ++)
f[i] = min(f[i],1 + 2 * f[j] + 3 * f[i - 1 - j] + j * j * (i - 1 - j));
}
cout<<f[2021]<<endl;
return 0;
}
五、大写
问题描述
给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母 转换成大写字母后将字符串输出。
Code
#include<iostream>
using namespace std;
int main()
{
char ch;
while(~scanf("%c",&ch))
{
if(ch <= 'z' && ch >= 'a')
printf("%c",ch - 32);
else printf("%c",ch);
}
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 行包含两个整数 li 和 ri，表示询问数列中第 li 个数到第 ri 个数的和。
输出格式
输出 T 行，每行包含一个整数表示对应询问的答案。
评测用例规模与约定
对于 10% 的评测用例， 1 ≤ T ≤ 30, 1 ≤ li ≤ ri ≤ 100。
对于 20% 的评测用例， 1 ≤ T ≤ 100, 1 ≤ li ≤ ri ≤ 1000。
对于 40% 的评测用例， 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 6。
对于 70% 的评测用例， 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 9。
对于 80% 的评测用例， 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 12。
对于 90% 的评测用例， 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 12。
对于所有评测用例， 1 ≤ T ≤ 100000, 1 ≤ li ≤ ri ≤ 10 ^ 12。
Code
用scanf读入比cin快很多
#include<iostream>
using namespace std;
long long sum(long long x)
{
if(x == 0) return 0;
long long l = 1,r = 2e6;
while(l < r)
{
long long mid = l + r + 1 >> 1;
if(x >= mid * (mid + 1) / 2) l = mid;
else r = mid - 1;
}
long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
x -= l * (l + 1) / 2;
a += x * (x + 1) / 2;
return a;
}
int main()
{
int t = 0;
scanf("%d",&t);
while(t--)
{
long long l = 0,r = 0;
scanf("%lld%lld",&l,&r);
printf("%lld\n",sum(r) - sum(l - 1));
}
return 0;
}
七、异或变换
问题描述
小蓝有一个 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 = si-1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0，当 a 和 b不同时结果为 1。
请问，经过 t 次变换后的 01 串是什么？
Code
八、
问题描述
Code
