P9420 [蓝桥杯 2023 国 B] 子 2023 / 双子数--2024冲刺蓝桥杯省一

点击跳转例题

子2023思路：dp。最开始想着枚举，但是超时，想着优化以下，但是还是不行。

那么切换算法，应该是dp：
1.f [i] 表示当前字符串 以 2023  为第 i 位的数量方案：如f [0] 表示 前i个字符串中2 的数量， f [1] 表示 前i个字符串中 20 的数量， f [2] 表示 前i个字符串中202 的数量， f [3] 表示 前i个字符串中 2023 的数量.

 2. 状态转移方程

3.初始化

4.迭代更新

双子数思路：枚举即可，线性筛法，因为最大为2e14次方，所以筛出1e7的素数即可，时间为0.1秒左右。然后枚举所有的可能性即可，注意枚举的时候，如果判断不当可能会爆longlong，可以开int 128， 单独修改int为int128即可

现在测评出了问题，算出答案后，直接用答案测评。

 

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'
#define LL __int128using namespace std;const int N=2e6+10,M=1e3+10,mod=998244353,INF=0x3f3f3f3f;int a[N],b[N],c[N],pre[N];int prime[N],cnt;
bool st[N];
int sum[N];void get_prime(int n)
{for(int i=2;i<=n;i++){if(!st[i])prime[cnt++]=i;for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i%prime[j]==0)break;}}
}signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);if(getchar()=='A'){string s;for(int i=1;i<=2023;i++)s+= to_string(i);vector<int>f(5);for(int i=0;i<s.size();i++){//状态转移方程，如当s[i]=='2'的时候，2的数量++，//202的数量为原来202的数量加上新产生的数量，就是当前的2与以前的20形成的202.if(s[i]=='2')f[0]++,f[2]=f[2]+f[1];if(s[i]=='0')f[1]=f[1]+f[0];if(s[i]=='3')f[3]=f[3]+f[2];}cout<<f[3]<<endl;}else{get_prime(1e7);int l=2333,r=23333333333333;int ans=0;for(int i=0;i<cnt;i++){//提前退出，优化枚举，避免超时if(prime[i]*prime[i]*prime[i+1]*prime[i+1]>r)break;for(int j=i+1;j<cnt;j++){int p1=prime[i],p2=prime[j];if(p1*p1*p2*p2<l)continue;if(p1*p1*p2*p2>r)break;ans++;}}cout<<ans<<endl;}return 0;
}