数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第二题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:49
标题:
2019第十届蓝桥杯B组决赛题解第二题
2019第十届蓝桥杯B组决赛题解第二题
* R2 w7 K' F i+ t8 p( Q: {
$ r3 D3 M+ x X: f* J
求两两不同的素数组成2019的方案数
( [# A [' ^' @1 g$ h2 J
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
5 p! D, v( M9 X# a _
结果: 55965365465060
2 e6 D r+ x4 Q* [+ e: k6 B
代码:
0 F9 ^* Z5 l1 w5 Z
#include<bits/stdc++.h>
& m- {' y9 \8 K" D2 _
#define mem(a,b) memset(a,b,sizeof(a))
- q, m( W9 I2 U7 l% ~. v/ s
using namespace std;
7 a. w2 D y2 C- e7 {" W
typedef long long ll;
- ~, N# B' {6 J. T4 x9 q' Z
const int inf = 0x3f3f3f3f;
# e, j. F- K8 t$ F+ Q
const int maxn = 3e5+55555;
/ \, X- d6 s, }9 {3 P- r# B
const ll mod = 998244353;
' B! k% D( S3 x
const double eps = 1e-7;
% t4 ]: K% F) l* ^- H- {( o# W
9 v7 l: N h E- }: P# [- M5 P5 b+ P( J
bool vis[12345];
2 X; k1 r+ C7 o3 U" o% Y3 r
vector<int>prime;
+ s2 n6 c% j; T: T# a
ll f[3000][3000];
0 K* Q( Y3 f/ Y) o- V/ Y( m
) F$ W- n9 x0 m0 k' O
void init() { //素数筛
( t. g, q, i2 N# x+ ]- i
for(int i = 2;i<= 3000;i++) {
" F5 L& j n" e# n
if(!vis
) {
, \, v! O$ {. V
for(int j = i*i;j<= 3000;j+= i) {
' z6 R3 J5 G) r6 ~' h
vis[j] = true;
?# i# H; Q- z- E$ d) @" o
}
9 s; f# _5 Z( @( K" @
}
, x3 T: _1 @7 k* y2 M: F
}
* {3 U; a1 F d
for(int i = 2;i<= 2019;i++) {
/ D R. s7 v* j" c! U3 V" a5 n
if(!vis
) prime.push_back(i);
" |' }* x4 ^9 I0 q! m
}
( J" W3 {# E. Q: V2 J N$ Z2 K! ?
}
" z* C& k# [3 ^; i, }
. I: W2 q* r, V. ]4 V4 h
ll dfs(int pos,int sum) {
) j7 F4 w) g+ Z% ]* J
if(f[pos][sum]!= -1) return f[pos][sum];
' R8 R, m U Q0 `) [! d/ q! r
if(sum == 2019) return 1;
$ M; l, |1 U* _' F3 O
if(pos>= prime.size()||sum> 2019) return 0;
4 U& H: J7 `; C% r. e4 u3 b- v. R
' \* O6 q: Y$ A1 N
ll ans = 0;
" x0 c" U$ [' D' r/ l* ?
ans+= dfs(pos+1,sum);// 不要当前这个素数
7 ~4 Q. c) c' c5 K8 O
ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
% o& ?, i; t8 c+ B; _1 x7 R1 F
return f[pos][sum] = ans;
$ v% Y% o( q- A5 K
}
5 J2 T) R2 P: S/ e6 N
& q5 z! i4 z. m" ~1 V2 \% j' {
int main() {
3 Y+ ~4 }8 W+ E# `, |. o! ^5 A
init();
) R J5 R1 q \1 a j
7 B! \5 h! [2 M' C8 `- C
mem(f,-1);
, m) L7 y3 {- K0 U) O4 R1 `
ll ans = dfs(0,0);
; i0 L: |; [) @/ D
cout<<ans<<endl;
) x3 }5 S/ q7 j4 Q* k
' ]6 U3 B5 p" a7 ^( `
return 0;
# Q) j% b* H: ?4 I# y" q1 c- C
}
% H4 z! y* \1 C* `; a& t4 [
---------------------
4 T6 _$ ]! |1 O( A7 ?+ \0 P1 U9 ^
作者：nka_kun
' S, B) ]% G' C8 [$ t3 l. X
8 p- k+ r* B0 i7 x7 l
, ^- b: f0 }! p% a
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5