第十二届蓝桥杯B组国赛真题详解及考点总结

200M的带宽理论下载速率为1024×200÷8＝25600KB/s＝25M/s
1Mbps代表每秒传输1, 000, 000位（bit），即每秒传输的数据量为：1, 000, 000/8 Byte，即125, 000Byte/s = 125KB/s
200Mbps = 200 * 125KB/s = 25, 000 KB/s = 25 MB/s

一位的质数为2，3，5，7，对于一个数字的每一位判断是否为上面4个数字之一，且它本身是不是质数，可以先预处理出1-20210605中所有质数，这一块需要用质数筛做这，当然也可以直接暴力找就是时间需要比较长（可能比赛结束也跑不出来），然后在累计是质数且每一位都是质数的数即可，总数据量很小，直接暴力循环判断即可。

#include
using namespace std;
const int N = 20210605;
int st[N];
bool check(int x)
{
	while (x)
	{   
		int t = x % 10;
		if (t==2||t==3||t==5||t==7)x /= 10;
		else return 0;
	}
	return 1;
}
int main()
{    
	for (int i = 2; i <= N; i++)//埃氏筛大约需要5s时间可以跑出结果
	{
		if (st[i] == 0)
			for (int j = 2; j * i <= N; j++)
				st[i * j] = 1;
	}
	int res = 0;
	for (int i = 2; i <= N; i++)
	{
		if (!st[i] && check(i))res++;
	}
	cout << res << endl;
}

日期也是蓝桥杯最最最频繁的考点了，只要注意一下闰年，然后暴力循环即可，判断完全平方数我们可以看出一共8位数那所有数的和不超过72，至多为8的平方，把1-8的平方预处理出来然后枚举每一天即可，。
解法1
Excel处理数据，由于可能自己模拟时间的时候会出错，所以可以从Excel得到所有日期，储存到记事本中，然后借助c++程序进行判断是否为完全平方数即可。

#include
#include
#include
using namespace std;

int res = 0;

void solve(int x) {
	for(int i = 0; i < 100; i++) {
		if(i * i == x) res++;
	}
}

int main() {
	string line;
	while(getline(cin, line)) {
		int len = line.length();
		int sum = 0;
		for(int i = 0; i < len; i++) {
			if(isdigit(line[i])) sum += line[i] - '0';
		}
		solve(sum);
		cout << res << endl;
	}
}

解法2
思路一致不过是直接在程序中模拟日期。

#include 
using namespace std;
const int maxn = 1e5 * 2 + 5;
int f[maxn];
int m[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31};
bool Run(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
        return true;
    }
    return false;
}
bool check(int y, int m, int d) {
    int sum = 0;
    while (y > 0) {
        sum += y % 10;
        y /= 10;
    }
    while (m > 0) {
        sum += m % 10;
        m /= 10;
    }
    while (d > 0) {
        sum += d % 10;
        d /= 10;
    }
    if (f[sum] == 1) {
        return true;
    }
    return false;
}
void init() {
    f[1] = 1;
    for (int i = 2; i * i < 100; i++) {
        f[i * i] = 1;
    }
}
int main() {
    //从2001.1.1到2021.12.31 // 平年2月 28天 闰年29天
    init();
    int ans = 0;
    for (int i = 2001; i <= 2021; i++) {//year
       
        if (Run(i)) {//如果是闰年
            m[2] = 29;
        }
        else m[2] = 28;
        for (int j = 1; j <= 12; j++) {//month
            for (int k = 1; k <= m[j]; k++) {
                if (check(i, j, k)) {
               
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

很明显递归直接求解会超时，那我们就转换思路，递归转递推，我们需要求得是有2021个节点的二叉树值最小，那我们dp[i]就设为有i个节点的二叉树最小值，然后我们状态改如何转移呢，当多一个节点作为父节点时，我们只需要考虑左右子树节点个数的搭配从中取个最小值即可，所以枚举左子树节点个数，右子树节点个数为i-j-1，然后根据上面的权值方程进行赋值即可。

#include
#define ll long long
using namespace std;
ll dp[2022];//dp[i]表示有i个节点的二叉树的最小值
int main()
{
    memset(dp,0x7f,sizeof(dp));//初始化最大值；
    dp[0]=0;//根据题意，当子树为空时权值为0；
    for(int i=1;i<=2021;i++)//自下而上；
        for(int j=0;j 
试题E： 
 
考点：字符串处理 
题解： 
签到送分题，c可以用toupper 或者直接减去32 c++中有transform
 
#include
using namespace std;
int main()
{
	string str;
	cin >> str;
	transform(str.begin(), str.end(), str.begin(), ::toupper);
	// for(int i=0;i 
试题F： 

 
 
考点：预处理、前缀和、二分 
题解： 
解法1
 很容易想到用前缀和来处理[l,r]的区间和，那么有个问题就是l，r数据过大直接预处理整个区间会爆空间，那我们来考虑如何来压缩空间
 首先将数列分层
 
1
1 2
1 2 3
1 2 3 4
 
我们会发现第i层数的数的个数为i，其和为
    
     
      
       
        （
       
       
        1
       
       
        +
       
       
        i
       
       
        ）
       
       
        ∗
       
       
        i
       
       
        /
       
       
        2
       
      
      
       （1+i）*i/2
      
     
    （1+i）∗i/2数的总数为1e12，那么用1e7层就可以存下所有的前缀和，具体的做法是，前缀和记录1-n层的值，先找到具体在哪一层（x），然后值就为x-1层的值+多出来的数的值，多出来多少个的值也是也是一个等差数列
    
     
      
       
        (
       
       
        n
       
       
        +
       
       
        1
       
       
        )
       
       
        ∗
       
       
        n
       
       
        /
       
       
        2
       
      
      
       (n+1)*n/2
      
     
    (n+1)∗n/2
 
（参考博客）
估计层数 – (1+x)*x/ 2>=1e12 ==> x = 1500000层
所以1500000层可以容纳1e12个数，也可以用数组存下
关键公式：sum = 前缀和求ab中间层数的和 + a当前层后面几个数量 + b当前层前面几个数量
解决给定第n个数，求出他在第几层第几个数。
解决求中间层数
#include
#include
#define ll long long
using namespace std;

ll dp[1500000]; // 每一层的和
ll dpSum[1500000]; // 层的前缀和

 //函数思路是找到a和b是第几层的第几个
 //sum = 前缀和求ab中间层数的和 + a当前层后面几个数量 + b当前层前面几个数量
 ll check(ll a,ll b){
 	ll temp = 1;
 	ll flag = 1;
 	while((temp+1)*(temp)/2 < a){
 		temp++;
 	}
 	ll aDeep = temp,aCnt = aDeep - (((aDeep+1)*(aDeep)/2) - a);
 	temp = 1;
 	flag = 1;
 	while((temp+1)*(temp)/2 < b){
 		temp++;
 	}
 	ll bDeep = temp,bCnt = bDeep - (((bDeep+1)*(bDeep)/2) - b);
 	ll sum = 0;
 	//cout << aDeep << ' ' << aCnt << ' ' << bDeep << ' ' << bCnt << endl; 
	if(bDeep > aDeep)
	  sum = dpSum[bDeep-1] - dpSum[aDeep];
	if(bDeep > aDeep){
		sum += (aDeep+aCnt)*(aDeep+1-aCnt)/2;
 		sum += (1+bCnt)*(bCnt+1-1)/2;
	}else{
		sum += (aCnt + bCnt)*(bCnt + 1 - aCnt)/2;
	}
 	
 	return sum;
 }
 
int main(){
	dp[0] = 0;
	dpSum[0] = 0;
    //推算到 1500000层正好大约1e12次方个数
    //处理1500000层的数据
	for(int i = 1; i <= 1500000; i++){
		dp[i] = dp[i-1] + i;
		dpSum[i] = dpSum[i-1] + dp[i];
	}
    //输入数据
	ll n;
	cin >> n;
	for(ll i = 0; i < n; i++){
		ll a, b;
		cin >> a >> b;
		cout << check(a,b) << endl;
	}
	return 0;
} 

————————————————
版权声明：本文为CSDN博主「404name」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45590872/article/details/117596582
 
解法2
 思路与解法1大致相同，做了两个优化。
 优化1：发现每一层的数的值为
    
     
      
       
        
         C
        
        
         3
        
        
         
          i
         
         
          +
         
         
          2
         
        
       
      
      
       C_{3}^{i+2}
      
     
    C3i+2​
 优化2：二分找在哪一层
 
根据前缀和得出区间之和为 s u m [ r ] − s u m [ l − 1 ] sum[r] - sum[l-1]sum[r]−sum[l−1]。

题目明显是分段来求的，具体来说是将序列看做 { 1 } , { 1 , 2 } , { 1 , 2 , 3 } , { 1 , 2 , 3 , 4 } , . . . {1},{1,2},{1,2,3}, {1,2,3,4},...{1},{1,2},{1,2,3},{1,2,3,4},...

其中每一块的长度刚好是 1 , 2 , 3 , 4... 1,2,3,4...1,2,3,4...，而每一块的所有元素之和是 1 , 3 , 6 , 10... 1,3,6,10...1,3,6,10...，每块元素之和的前缀和为 p r e [ i ] = { 1 , 4 , 10 , 20... } pre[i] = {1,4,10,20...}pre[i]={1,4,10,20...}，这个前缀和的第 i ii 项刚好对应了组合数 C i + 2 3 C_{i + 2}^3C 
i+2
3
​
 。

因此思路就很明确了，二分确定前面有多少个完整的块，然后 O ( 1 ) O(1)O(1) 算出这些块的和，最后拿 n nn 减去前面块的元素个数，得到的一定是一个新的块中的从1开始的连续若干个自然数，根据等差数列公式 n ( n + 1 ) 2 frac{n(n + 1)}{2} 
2
n(n+1)
​
 即可求出，累加上述二者即可。

#include 

using namespace std;
#define ENDL "n"
typedef long long ll;
typedef pair pii;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;

ll cal1(ll n) {
    return n * (n + 1) * (n + 2) / 6;
}

ll cal2(ll n) {
    return n * (n + 1) / 2;
}

ll getSeg(ll n) {
    ll l = 1, r = 1e9, mid, ans;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (cal2(mid) <= n) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    return ans;
}

ll solve(ll n) {
    if (n == 0) return 0;
    ll s = getSeg(n);
    return cal2(n - cal2(s)) + cal1(s);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    ll l, r;
    cin >> T;
    while (T--) {
        cin >> l >> r;
        cout << solve(r) - solve(l - 1) << ENDL;
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「Happig丶」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44691917/article/details/118546911

 
试题G： 

 
 
 
考点：找规律 
题解： 
随机打表后发现循环节为，求出来的循环节是大于等于n的最小的2的幂次，对t取余后暴力模拟。
 
#include
#define ll long long
using namespace std;

ll n, t;
const int N = 1e4 + 10;
char ch[N];
int a[N], b[N];

int main()
{
	scanf("%lld %lld", &n, &t);
	scanf(" %s", ch);
	ll len = 1;
	while (len < n)len *= 2;
	if (t % len == 0) {
		puts(ch);
		return 0;
	}
	t %= len;
	for (int i = 0; i < n; ++i) {
		a[i] = ch[i] - '0';
	}
	b[0] = a[0];
	for (int i = 1; i <= t; ++i) {
		
		for (int j = 1; j < n; ++j) {
			b[j] = a[j] ^ a[j - 1];
		}
		
		for (int j = 1; j < n; ++j) a[j] = b[j];
	}
	for (int j = 0; j < n; ++j) {
		printf("%d", b[j]);
	}
	return 0;
}

 
试题H： 

 
 
考点：数位DP 
题解：(待补) 
#include 
using namespace std;
typedef long long ll;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 10;
ll d[105][55][2];
int digit[105];
int k;

ll dfs(int pos, int sum, bool flag) {
    if (pos == 0) return sum == k;
    if (d[pos][sum][flag] != -1) return d[pos][sum][flag];
    int up = flag ? digit[pos] : 1;
    ll ans = 0;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos - 1, sum + (i == 1), flag & (i == up));
    }
    return d[pos][sum][flag] = ans;
}

ll solve(ll n) {
    int len = 0;
    while (n) {
        digit[++len] = n & 1;
        n /= 2;
    }
    memset(d, -1, sizeof d);
    return dfs(len, 0, 1);
}

int main() {
  
    ll n;
    cin >> n >> k;
    cout << solve(n) << endl;
    return 0;
}


 
试题I： 

 
 
考点：线段树、二分 
题解： 
暂时补不动
 参考博客
 
试题J： 

 
 
 
考点：DP 
题解：（待补） 
（代码参考知乎）
#include
using namespace std;
#define int long long
int n2[60];
int dp[60][2][4];
int len = 0;
void parse(int x)
{
    while(x)
    {
        n2[len] = x&1;
        x>>=1;
        len++;
    }
}

signed main()
{
    int n;
    cin>>n;
    parse(n);
    dp[len][1][0] = 1;
    for(signed i = len - 1;i>=0;i--)
    {
        for(signed j = 0;j<4;j++)
        {    // 4 a1b1c0 2 a1b0c1 1 a0b1c1 0 > 4 > 2 > 1
            dp[i][0][j] += (j + 1) * dp[i+1][0][j]; // 0 1 2 3 -
            if(j > 0)
                dp[i][0][j] += dp[i+1][0][j-1]; // 0 1 2 +
            if(n2[i])
            {
                if(j>0)
                {
                    dp[i][1][j] += min(j,2) * dp[i+1][1][j];    // 1 2 3 -
                    if(j<3)
                        dp[i][1][j] += dp[i+1][1][j-1]; //0 1 +
                }
                dp[i][0][j] += dp[i+1][1][j];      //0 1 2 3 0
                if(j==3)
                    dp[i][0][j] += dp[i+1][1][j-1] + dp[i+1][1][j]; // 2 +
            }
            else
            {
                dp[i][1][j] += dp[i+1][1][j];  //0 1 2 3 0
                if(j==3)
                    dp[i][1][j] += dp[i+1][1][j-1] + dp[i+1][1][j]; // 2 + 3 -
            }
//           cout< 
总结 
填空题比第12届省赛简单，大题前三道难度适中，后面三道有点难，线段树、数位dp还是知识盲区，压轴的dp暂时也搞不懂，要是有人搞懂了或者有看到详细的讲解可以私信我，感激不尽。