蓝桥杯2023国B A、B题

A题

分析

dp问题

根据子序列：2，20，202，2023分为4个状态；

当前数字为2时，处于dp[0]，或者和dp[1]结合成dp[2]；

当前数字为0时，和dp[0]结合成dp[1];

当前数字为3时，和dp[2]结合成dp[3]

要求的2023子序列的个数就是dp[3]的值

代码：

to_string(int i);  //将int转换为string，头文件：<string>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int main()
{ll dp[4] = {0};string s;for(int i = 1;i <= 2023;i ++){s += to_string(i);}for(int i = 0;i < s.size();i ++){if(s[i] == '2'){dp[0] ++;dp[2] += dp[1];}else if(s[i] == '0') dp[1] += dp[0];else if(s[i] == '3') dp[3] += dp[2];}cout << dp[3] << endl;return 0;
}

B题

分析

1.用埃氏筛求素数（时间复杂度比朴素做法好）

由于x = p^2*q^2，需要找的素数范围为sqrt(23333333333333)

又由于p是素数，最小为2，故q最大为sqrt(23333333333333/4)

求出2~3*10^6即可

2.枚举p,q

代码 

埃氏筛：

将2~n范围内的整数写在表中：

2是最小的数，将表中所有2的倍数划去；

3是最小的数，将表中所有3的倍数划去；

……

m是表中最小的数，m就是素数，将表中所有m的倍数划去

实现：bool isprime[]

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;const int N = 5000010;
bool isprime[N];
int prime[N];
typedef long long ll;//埃氏筛求素数
void sieve()
{for(int i = 2;i <= N;i ++){if(!isprime[i]){for(int j = 2 * i;j <= N;j += i){isprime[j] = true;}}}
}int main()
{sieve();int k = 0;for(int i = 2;i <= N;i ++){if(!isprime[i]){prime[k ++] = i;}}long long cnt = 0;for(int i = 0;i < k;i ++){//如果p^4爆了，p^2*q^2肯定要爆（longlong的范围大概是10^16）//必须要写这句，不然会超出long long范围，结果错误if(1ll*prime[i]*prime[i]*prime[i]*prime[i] > 23333333333333) break;for(int j = i + 1;j < k;j ++){if(1ll*prime[i]*prime[i]*prime[j]*prime[j] < 2333)continue;else if(1ll*prime[i]*prime[i]*prime[j]*prime[j] > 23333333333333)break;cnt ++;}}cout << cnt << endl;return 0;
}