试题A：带宽
解题思路：
由于小蓝家的网络带宽是200Mbps，即200Mb/s，所以一秒钟可以下载200Mb的内容，根据1B=8b的换算规则，所以200Mb=200/8MB=25MB。所以小蓝家的网络理论上每秒钟最多可以从网上下载25MB的内容。
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
cout<<200/8<<endl;
return 0;
}
试题B：纯质数
解题思路：
由于题目要求的是本身是质数而且其所有十进制数位都是质数的数的个数，于是直接先用线性筛对1~20210605的数字进行质数筛选，筛选后的质数存储在prime数组中，再对prime数组（全是质数）进行遍历，依次判断每个质数的每个数位是否都是质数（mp数组用于快速判断某个数是否为质数），如果是，答案加1，否则直接进行下一个质数的判断。
最终答案为：1903
代码实现：
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define int long long
const int N=20210610;
//prime数组用于存储1~20210605之间的质数
//vis数组用于在线性筛法中判断一个数是否被标记过，
//如果未被标记过，则表示该数为质数，否则代表该数不是质数
//mp数组用于标记某个数是否为质数，便于快速判断一个数是否为质数
int prime[N],vis[N],mp[N],cnt;
void init(int n){
for(int i=2;i<=n;i++){
//如果该数未被标记过，则该数一定为质数
//存储该质数并标记该数为质数
if(!vis[i])prime[cnt++]=i,mp[i]=1;
//利用质数的倍数来标记合数，被标记的一定不是质数
for(int j=0;prime[j]*i<=n;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
signed main(){
init(20210605);
int res=0;
//遍历1~20210605中的所有质数
for(int i=0;i<cnt;i++){
int temp=prime[i],flag=1;
while(temp){
//如果存在某个数位不是质数，直接退出
if(!mp[temp%10]){
flag=0;
break;
}
temp/=10;
}
//如果满足该质数所有位都是质数，则答案加1
if(flag)res++;
}
cout<<res<<endl;
return 0;
}
试题C：完全日期
解题思路：
直接模拟，遍历日，如果日大于当前月份的天数，则日变为1，月份加1，如果月份大于12，则月变为1，年加1。
最终答案为：977
\(\textcolor{red}{注意不要忘了判断最后一天即2021-12-31该天是否为完全日期数}\)
代码实现：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<unordered_map>
using namespace std;
#define int long long
//用于初始化闰年和平年每个月的天数
//month[1][1~12]表示闰年的1-12月的天数
//month[0][1~12]表示平年的1-12月的天数
int month[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
0,31,29,31,30,31,30,31,31,30,31,30,31};
//判断闰年
int isrun(int x){
if(x%400==0||(x%4==0&&x%100!=0))return 1;
return 0;
}
signed main(){
int res=0;
//y表示年，m表示月，d表示日
int y=2001,m=1,d=1;
//如果当前不是2021年12月31日就继续遍历
while(y!=2021||m!=12||d!=31){
//num用于计算年月日的各个数字之和
int num=y%10+y/10%10+y/100%10+y/1000%10+m%10+m/10%10+d%10+d/10%10;
//求num的平均数
int temp=sqrt(num);
//如果是完全平方数，则答案加1
if(temp*temp==num)res++;
//日加1
d++;
//如果日大于当前月份的最大值，则日变为1，月加1
if(d>month[isrun(y)][m])d=1,m++;
//如果月大于12，则月变为1，年加1
if(m>12)m=1,y++;
}
//最后别忘记判断2021-12-31
//由于可以手算：2+0+2+1+1+2+3+1=12,不是完全日期，答案不用加1
cout<<res<<endl;
return 0;
}
试题D：最小权值
解题思路：
递推：
设dp[i]表示总结点个数为i的二叉树的最小权值，通过遍历总结点，同时遍历左子树的结点个数，右子树的结点个数为总结点树-左子树结点数-1（根结点数），然后直接套公式，每次取最小值即可。
最终答案为：2653631372
\(\textcolor{red}{注意右节点数一定不要忘了减去根节点个数1}\)
代码实现：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<unordered_map>
using namespace std;
#define int long long
const int N=2500;
//dp[i]表示总结点个数为i的二叉树的最小权值
int dp[N];
signed main(){
//初始化为最大
memset(dp,0x3f,sizeof dp);
//没有结点时，权值为0
dp[0]=0;
//遍历总结点个数
for(int i=1;i<=2021;i++){
//遍历左子树结点个数，左子树结点个数最小可以为0，最大为总结点数-1，因为根结点需要消耗一个结点数
for(int j=0;j<i;j++){
//按照公式计算，取所有情况的最小值
dp[i]=min(1+2*dp[j]+3*dp[i-j-1]+j*j*(i-j-1),dp[i]);
}
}
//输出结点个数为2021的二叉树的最小权值
cout<<dp[2021]<<endl;
return 0;
}
试题E：大写
解题思路：
纯签到题，有手就行
直接遍历一遍，如果是小写字母，则根据大小写字母ASCII值相差32进行转换即可
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]>='a'&&s[i]<='z')s[i]=s[i]-32;
cout<<s[i];
}
return 0;
}
试题F：123
解题思路：
数列中的每一个连续的部分可以看作一个小区间。
1 1,2 1,2,3 1,2,3,4 ...每一个小区间都是一个 a1=1，d=1 的等差数列，且区间的长度也能构成等差数列。
由于l,r<=10^12,即
所以最多有 1414214 个小区间构成该数列，满足任意 l,r 都能落在里面。
这意味着虽然我们不能直接查询某一位置的前缀和，但可以通过这些小区间来定位和计算某一位置的前缀和。
- 第 i 个区间的元素个数为 i。
- 定义a[i]表示前i个小区间的元素的个数（1-n的和）。则有：a[i]=a[i-1]+i。
- 定义s[i]表示前i个小区间的和。则有：s[i]=s[i-1]+a[i]。
- 对于数列中任意位置i，一定存在一个最大的j满足a[j]<=i，这表示第i个数落在第j+1区间内。
- 对于数列中任意位置i，当它落在第j+1个区间，它是该区间第k个数，则它在数列中的前缀和为：s[j]+a[k]，其中k=i-a[j]。
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1500005;
//a[i]表示前i个组包含的数的总个数
//s[i]表示前i个组的所有的数的总和
int a[N],s[N];
int query(int x){
//利用二分查找一个最大的l，使得a[l]（前l组的数的个数）小于等于x
int l=0,r=N;
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
//由于1+2+...+i的和就等同于前i组数的总个数，所以1~x-a[l]的和就等同于a[x-a[l]]
//前x项的和等同于前l组的和s[l]加上1~x-a[l]的和a[x-a[l]]
return s[l]+a[x-a[l]];
}
signed main()
{
for(int i=1;i<=N;i++){
//预处理a[i]：前i组的数的个数和
//预处理s[i]：前i组的数的总和
a[i]=a[i-1]+i;
s[i]=s[i-1]+a[i];
}
int t;
cin>>t;
while(t--){
int l,r;
cin>>l>>r;
//利用前缀和求解：l~r的和就等同于前r项的和减去前l-1项的和
cout<<query(r)-query(l-1)<<endl;
}
return 0;
}