C++B组国赛：

【线性dp，筛质数，背包问题求方案数，枚举，DFS】

1.子2023

动态规划

#include<bits/stdc++.h>
using namespace std;
long long f1,f2,f3,f4; //分别记录2 20 202 2023的个数 
int main()
{
    string s;
    for(int i=1;i<=2023;i++) s+=to_string(i);
    for(int i=0;s[i];i++)
    {
        if(s[i]=='0') f2+=f1;
        else if(s[i]=='2') f1++,f3+=f2;
        else if(s[i]=='3') f4+=f3;
    }
    cout<<f4;
    return 0;
}

答案：5484660609

2.双子数（代码目前有问题）

筛质数+优化枚举

#include<bits/stdc++.h>
using namespace std;
const int N = 3000010;
int p[N],cnt;
bool st[N];
long long res;

void getp(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) p[cnt++]=i;
        for(int j=0;p[j]<=n/i;j++)
        {
            st[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}

int main()
{
    getp(3000000);
    for(int i=0;i<cnt;i++)
    {
        long long pp=1ll*p[i]*p[i];
        if(pp*pp>23333333333333) continue;
        for(int j=i+1;j<cnt;j++)
        {
            long long qq=1ll*p[j]*p[j];
            if(pp*qq>=2333&&pp*qq<=23333333333333) res++;
        }
    }
    cout<<res;
    return 0;
}

答案：947293

3.2022

背包dp

答案：

4.钟表

模拟

答案：

5.带宽

答案：200/8=25

6.纯质数

筛质数+枚举

#include<bits/stdc++.h>
using namespace std;
int res;
const int N = 20210615;
int p[N],cnt;
bool st[N];
void getp(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) p[cnt++]=i;
        for(int j=0;p[j]<=n/i;j++)
        {
            st[i*p[j]]=true;
            if(i%p[j]==0) break;
        }
    }
}

bool check(int n)
{
    while(n)
    {
        if(n%10!=2&&n%10!=3&&n%10!=5&&n%10!=7) return false;
        n/=10;
    }
    return true;
}

int main()
{
    getp(20210605);
    for(int i=0;i<cnt;i++) if(check(p[i])) res++;
    cout<<res;
    return 0;
}

答案：1903

7.美丽的2

枚举

#include<bits/stdc++.h>
using namespace std;
int res;

bool check(int n)
{
    while(n)
    {
        if(n%10==2) return true;
        n/=10;
    }
    return false;
}

int main()
{
    for(int i=1;i<=2020;i++) if(check(i)) res++;
    cout<<res;
    return 0;
}

答案：563

8.扩散

9.平方序列

枚举

#include<bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=2020;i<10000;i++)
        for(int j=i+1;j<10000;j++)
            if(i*i-2019*2019==j*j-i*i)
                cout<<i+j<<endl;
    return 0;
}

答案：7020

10.质数拆分

筛质数+背包