P9420 [蓝桥杯 2023 国 B] 子 2023 / 双子数

zhlzt · 2023-06-23 14:37:34 · 题解

第一题 DP 做法

其实第一题并不难，我们设在 s 的截止到当前位置的前缀字符串中，为 2,20,202,2023 的子序列分别有 dp_{0},dp_{1},dp_{2},dp_{3} 个，那么不难推出，dp_{0},dp_{1},dp_{2},dp_{3} 要用以下规则更新：

• 若当前数字为 2，可以单独作一个子序列，即 dp_{0}\gets dp_{0}+1，也可以接在子序列 20 之后构成 202，即 dp_{2}\gets dp_{2}+dp_{1}。
• 若当前数字为 0，可以接在子序列 2 之后构成 20，即 dp_{1}\gets dp_{1}+dp_{0}。
• 若当前数字为 3，可以接在子序列 202 之后构成 2023，即 dp_{3}\gets dp_{3}+dp_{2}。

最后答案就是为 2023 的子序列的数量 dp_{3}。

第二题埃氏筛与暴力枚举做法

第二题更水，直接埃氏筛求素数，再暴力枚举 p,q，剪枝优化即可，具体见代码注释。

需要注意的是，由于 p,q 的平方都不超过 23333333333333，所以这里埃氏筛只需要筛到 \sqrt{23333333333333}，约 5\times 10^6，其实还可以再缩小，因为 p,q 中较小的数的平方至少为 4（值为 2 时取到），此时另一个数最多还不到 2.5\times10^6，开个 3\times 10^6 就已经够保险了。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e6;
long long dp[5]; string s;
int isprime[N+10],prime[N+10];  
int main(){
    if(getchar()=='A'){
        for(int i=1;i<=2023;i++) s+=to_string(i);
        // to_string(i) 是将 i 变为字符串
        // s+=t 代表将字符串 t 添加到 s 末尾 
        for(int i=0;i<s.size();i++){
            if(s[i]=='2') dp[0]++,dp[2]=dp[2]+dp[1];
            else if(s[i]=='0') dp[1]=dp[1]+dp[0];
            else if(s[i]=='3') dp[3]=dp[3]+dp[2];
        }
        printf("%lld",dp[3]);
    }
    else{ 
        int cnt=0,ans=0;
        for(int i=2;i<=sqrt(N);i++){
            if(!isprime[i]){
                for(int j=i*i;j<=N;j+=i) isprime[j]=1;
            }
        }
        for(int i=2;i<=N;i++){ 
            if(!isprime[i]) prime[++cnt]=i;
        }
        for(int i=1;i<=cnt;i++){
            long long p2=1LL*prime[i]*prime[i];
            if(1LL*p2*p2>23333333333333) break;
            for(int j=i+1;j<=cnt;j++){
                long long q2=1LL*prime[j]*prime[j];
                if(1LL*p2*q2<2333) continue;
                // p*p*q*q 太小，不能更新答案 
                if(1LL*p2*q2>23333333333333) break; 
                ans++;
            }
        }
        printf("%d",ans); 
    }
    return 0;
}