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

杨利霞

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

5 y* x7 J5 Q5 K  u* \1 l求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
% _+ o: m/ k# E) D. d5 d1 ^0 F结果: 55965365465060
$ P$ u+ h9 Y8 c$ W* w代码:
5 N# K0 ~( B1 A& F* M1 I6 k1 ]) {$ P#include<bits/stdc++.h>
4 q4 |# O7 M' s" b* ^#define mem(a,b) memset(a,b,sizeof(a))
3 m  a& D. d, q4 B9 |* }using namespace std;
1 Z2 B+ [2 W; d7 e* R1 Jtypedef long long ll;
# Q* N7 `8 v$ a- Pconst int inf = 0x3f3f3f3f;
6 S! z0 @! R! Pconst int maxn = 3e5+55555;
; C8 S8 A, X& |, K; L- zconst ll mod = 998244353;
  g9 k5 f6 j& _6 M  F4 w; iconst double eps = 1e-7;

bool vis[12345];
6 }6 M% O  I, D1 h- b9 z+ hvector<int>prime;
$ `9 Y" K" a, C2 J& Z, Q1 z/ Lll f[3000][3000];

. k1 f/ G0 |, lvoid init() { //素数筛
    for(int i = 2;i<= 3000;i++) {
2 N0 ?4 i. A. }" ~        if(!vis) {
            for(int j = i*i;j<= 3000;j+= i) {
* X# G# x7 m- B9 o1 `                vis[j] = true;
            }
& }$ W" V* z% c' l: L        }
    }
, l& q1 W" D( Z5 _4 F    for(int i = 2;i<= 2019;i++) {
# t3 a9 Z/ r. O) O$ k$ ?3 R        if(!vis) prime.push_back(i);
! ^% U) _. |+ [+ }. C2 i+ @    }
}

% }3 n* ?4 J% z' O3 Tll dfs(int pos,int sum) {
6 Y; J5 W! {2 I7 S* Z    if(f[pos][sum]!= -1) return f[pos][sum];
8 o: L# }7 i, q2 ]* v! D( b    if(sum == 2019) return 1;
    if(pos>= prime.size()||sum> 2019) return 0;

    ll ans = 0;
7 t, N* f, j% @& ?1 B; m    ans+= dfs(pos+1,sum);// 不要当前这个素数
( `" s, P( N( N: A5 x! D    ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
    return f[pos][sum] = ans;
, U/ D5 t+ \- m  p}
' a: h8 I& R* @$ o) {
int main() {
    init();

    mem(f,-1);
    ll ans = dfs(0,0);
    cout<<ans<<endl;
) a* S- N# g$ m& h8 r
    return 0;
( N* a$ Q" q. u9 a, ?$ [}
---------------------
5 @" z, y) A# _: C3 ?作者：nka_kun