数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第二题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:49
标题:
2019第十届蓝桥杯B组决赛题解第二题
2019第十届蓝桥杯B组决赛题解第二题
# l# J6 v% i* @1 _/ G
4 h$ p& v0 N3 i7 l8 o3 [2 [& K
求两两不同的素数组成2019的方案数
% d$ q7 [2 Q, x- f; {
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
* k, c, x: }8 Y. a
结果: 55965365465060
+ F) _+ ? ^- T% m2 H( J
代码:
) R8 P2 D- M) a# Q
#include<bits/stdc++.h>
8 ?1 ^& e g2 |6 f h# g) {
#define mem(a,b) memset(a,b,sizeof(a))
) l! m; ?' M5 ]2 y2 c g, r5 }
using namespace std;
9 p, c# h; V! m4 r# h2 x
typedef long long ll;
9 m. O; w1 J4 ]' |$ b8 R
const int inf = 0x3f3f3f3f;
- c* X( R' B: S- v! w4 E* i: [" v
const int maxn = 3e5+55555;
* X7 z U& E* N8 M
const ll mod = 998244353;
3 v. w) h' Y5 C
const double eps = 1e-7;
: _: n. B" E/ d5 ^4 J& I
) ~) K8 x8 ~. C5 E! ~/ r1 o
bool vis[12345];
* m0 I J" f! _/ r
vector<int>prime;
6 n* E) H3 w; s( D3 x W
ll f[3000][3000];
, ~6 t4 D( [8 P6 K4 T, C6 G, |
; V! M1 b. z/ Y
void init() { //素数筛
9 H! ?" h7 K( r# P$ K4 G
for(int i = 2;i<= 3000;i++) {
1 [" x9 K0 o6 X1 K2 H' Z- I8 X
if(!vis
) {
) g3 ^& @ M9 p( v
for(int j = i*i;j<= 3000;j+= i) {
: n0 G# y8 c% ~1 ]3 ?5 E' i
vis[j] = true;
% L1 T& r$ n6 N3 ?. S
}
" N$ x% P' m) }9 w2 O. ^: D! L* Q0 y
}
& d% H6 C6 z2 Q4 j3 ^( W: o* \# {5 I
}
, Q+ { g+ Q4 ^& N/ i
for(int i = 2;i<= 2019;i++) {
4 e/ M) M. v$ w! a
if(!vis
) prime.push_back(i);
3 i2 q2 t0 R( u% V
}
0 z; H' k" i3 X P6 E& t8 g
}
1 I. s! P+ P. _+ g3 m/ r7 Z6 u
. f4 d. O' B0 t' y6 L( t
ll dfs(int pos,int sum) {
% o" ]' y+ N* i( d, y
if(f[pos][sum]!= -1) return f[pos][sum];
) c! A# r1 E2 V
if(sum == 2019) return 1;
% k. g6 l' y1 @+ ]
if(pos>= prime.size()||sum> 2019) return 0;
* n- b6 R0 r, O3 M' D* v
7 g1 I9 h, q" L( R: d* K
ll ans = 0;
; p4 u) J- c$ I3 o1 z
ans+= dfs(pos+1,sum);// 不要当前这个素数
! V2 T) X1 J. N
ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
# e2 h6 i3 ?5 \- ^
return f[pos][sum] = ans;
2 V, k( K. ?( \6 k" w9 P5 M
}
( {+ g* w% {' X/ t* F1 Z4 R6 Z
* k+ G1 h# {. {
int main() {
6 E* B2 S x7 ^; B
init();
1 B' v" i$ S' a: F$ @
9 h$ {1 Y) [! W- x1 L! E- w" V3 M
mem(f,-1);
$ t+ q+ Q! [: d3 n
ll ans = dfs(0,0);
3 u9 L: E5 f+ f9 R% t
cout<<ans<<endl;
! ?- @* p0 l9 `; `
0 D' \1 H2 p5 {8 ?0 o
return 0;
0 ~+ o3 Z! ]; d F
}
- d- f) x$ z+ m: D" P! V
---------------------
; k0 Z% S) L! k9 W+ c
作者：nka_kun
$ E9 E# N& E1 o, ^0 n3 ~! o: j# u
c4 S3 k+ N1 ]; }2 t: g+ c
1 _7 f5 M$ n5 I, t! W5 K* w* a7 P
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5