2019第十届蓝桥杯B组决赛题解第二题

杨利霞

2019第十届蓝桥杯B组决赛题解第二题

6 ^1 w+ [: |% e0 I* |求两两不同的素数组成2019的方案数
# a$ E3 f" c+ G% Z; X1 ]9 r5 X注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
+ |( ]6 o) [( c) T; |/ G" [1 C代码:
+ u, D5 ~# j9 m2 U, K; R2 K#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
- w  b% a1 x1 R' xusing namespace std;
% N7 G1 k, c- b$ {: \1 @typedef long long ll;
/ g2 C$ U  v* p0 l; E* }  N$ C( Pconst int inf = 0x3f3f3f3f;
% b1 x- R1 f3 I% lconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
! Y% \: P; I! |/ v/ Y. N
/ _; d0 j/ z+ u( E5 {& Qbool vis[12345];
vector<int>prime;
ll f[3000][3000];
6 ~" U9 C: D) J8 T8 }
void init() { //素数筛
3 V8 Q% o1 K! H' x( W6 F    for(int i = 2;i<= 3000;i++) {
- m# k8 g' z0 X6 B2 R& \. f        if(!vis) {
5 K7 I& C7 C4 E0 S            for(int j = i*i;j<= 3000;j+= i) {
8 q! W) @" \1 f' S8 B' F                vis[j] = true;
+ ^( O6 a$ O4 @& c            }
        }
    }
  U3 o+ w6 Q7 g3 \    for(int i = 2;i<= 2019;i++) {
6 y. O) F& S5 Q" e% J; j6 W$ m8 T        if(!vis) prime.push_back(i);
; F+ a; O9 i- Z( M$ h8 y    }
. S) A/ B6 u) ~( I! m" r$ Z; X}
- d0 e( m. O' f: ?
) `' p% ]/ n5 X1 pll dfs(int pos,int sum) {
    if(f[pos][sum]!= -1) return f[pos][sum];
+ P1 ~/ E; Y+ {- v    if(sum == 2019) return 1;
- b9 o8 s. S+ f/ k- S    if(pos>= prime.size()||sum> 2019) return 0;

- O' L% O* K* F  ^: @6 [    ll ans = 0;
    ans+= dfs(pos+1,sum);// 不要当前这个素数
    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
}

int main() {
2 \4 l- S/ Y- N% m7 x. R2 S4 F0 y    init();

    mem(f,-1);
  u9 B+ K9 G0 O) h) C: E    ll ans = dfs(0,0);
    cout<<ans<<endl;
& D& }" @  u# B/ b% F
    return 0;
; \) t/ ?* j4 ?/ _0 a/ |" H# e}
---------------------
作者：nka_kun


) P$ j9 X7 m8 K1 v- T- _. M  t