数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第二题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:49
标题:
2019第十届蓝桥杯B组决赛题解第二题
2019第十届蓝桥杯B组决赛题解第二题
) b" h) G* \' C
m2 x& u) q( e: B
求两两不同的素数组成2019的方案数
! r( o4 w3 C3 {6 f( i! O0 c
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
+ F9 k3 ?- Z2 r+ o6 Y
结果: 55965365465060
) G# g8 {' \6 ^2 j) v( b
代码:
) ~7 x9 G& h* c1 u: _: W
#include<bits/stdc++.h>
4 g7 J g; ?, N7 m
#define mem(a,b) memset(a,b,sizeof(a))
# S% L9 f' s4 w" A
using namespace std;
$ M* b. |1 i a' c q
typedef long long ll;
/ x/ u/ J8 N7 N# ]" [! @' ^* i
const int inf = 0x3f3f3f3f;
, z- B" y$ m U" V
const int maxn = 3e5+55555;
& M9 L% F9 H' V9 q' ?
const ll mod = 998244353;
7 Y- j0 e- i7 f% X6 \+ v4 a
const double eps = 1e-7;
$ C$ U/ f- k. t4 V! N h
+ E0 u9 H, M$ o, Q3 f
bool vis[12345];
8 ?! ~% i2 S1 R' N# m1 n
vector<int>prime;
- P- t: r+ V6 W, ` h4 s
ll f[3000][3000];
0 n/ k5 z, \' X0 T+ c6 G- X
1 f0 O7 V; F: ^) h8 Z! T8 z$ ^1 R
void init() { //素数筛
1 S8 A4 n" z. ?: x# K1 U
for(int i = 2;i<= 3000;i++) {
3 ]. E0 L; \6 D' a: _
if(!vis
) {
' m% d {# a3 f# e s: t4 R7 t8 R3 m
for(int j = i*i;j<= 3000;j+= i) {
, t2 U. x& m8 |) _: n0 C. j: x! g
vis[j] = true;
: {+ D. s' i& J1 y; F
}
. d& d* L: m" q `2 D
}
4 i- b3 d4 ~/ i4 l
}
0 U/ D+ u3 }2 n' n
for(int i = 2;i<= 2019;i++) {
( y! f7 D! f o1 x* L% u; ~2 |
if(!vis
) prime.push_back(i);
2 ?. M5 M( f* ~! i
}
9 y9 b: {; T( u
}
) M2 Q/ ~/ f5 u, I, D
: W; x- x8 e- j8 @
ll dfs(int pos,int sum) {
* p+ E9 s' s, {+ T
if(f[pos][sum]!= -1) return f[pos][sum];
x o5 W# V) t5 s) H$ x# V
if(sum == 2019) return 1;
( {8 j+ h# }- I A2 m2 y
if(pos>= prime.size()||sum> 2019) return 0;
* F2 ~/ G- w6 o6 x, t9 Y* h9 ^
' X7 y- S/ G. r* |1 v" l+ O3 o
ll ans = 0;
7 |' j# {# }2 D+ ] t1 z
ans+= dfs(pos+1,sum);// 不要当前这个素数
* ]( Q3 n5 m, R! @9 M
ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
' i. \$ P, R8 Z6 H, A) @% S; h! d# D
return f[pos][sum] = ans;
" c; t2 n* h! P U$ C
}
, k5 ?) M4 F- [( A8 q2 x; }
' Y; ~. o" @8 x. ^$ c4 C
int main() {
1 l* Z" m& \" q$ f! J8 g& e
init();
2 @9 K7 v* \* Y( @3 J* R
" b. x. Y6 p0 B% K2 P
mem(f,-1);
/ Y* L1 v' |1 o# n0 r* O7 C
ll ans = dfs(0,0);
; ~5 h+ d% b% H- C' O
cout<<ans<<endl;
; d; [" M' O4 S- z: w7 I5 _
+ _4 P( x% Z& ~5 n* L8 ]9 ~$ \0 n- d
return 0;
; M1 S5 w; w+ {. L' G# _3 t6 B
}
; m0 d; r% w" H& |! v; I& u
---------------------
) c s# S2 ~6 ?$ y
作者：nka_kun
) @* c+ \, B/ @5 L' s
0 r2 m8 u" B! {4 {
/ q$ ^' ~, r' B8 s7 ]. a
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5