数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第二题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:49
标题:
2019第十届蓝桥杯B组决赛题解第二题
2019第十届蓝桥杯B组决赛题解第二题
) V/ \# s- Z+ q) J, w1 S6 U+ }
" G( r$ b2 j8 `3 H' r
求两两不同的素数组成2019的方案数
( j( ^# n8 z* u) @" v+ N
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
% y0 B! ^$ q; n
结果: 55965365465060
, H( F6 Q: K$ C) }7 q
代码:
/ B. N4 @' D- R/ _- `' o
#include<bits/stdc++.h>
3 U9 g _3 ~; U. H7 X9 U& q: \% i
#define mem(a,b) memset(a,b,sizeof(a))
- I- b( S, Z7 a; [
using namespace std;
+ `, d5 X; }5 p
typedef long long ll;
2 o r; r: f' ~$ W8 q1 X
const int inf = 0x3f3f3f3f;
3 o/ y' W/ b/ Z0 Q! ~
const int maxn = 3e5+55555;
$ _" @( q; X3 ^: q) F9 x7 e. D. y
const ll mod = 998244353;
$ X, {# v/ L0 r
const double eps = 1e-7;
- ?/ G3 ]- Q. j; Z) ]- \- |0 O1 C
; H, E0 @+ m8 J+ s* Z
bool vis[12345];
( i; ^! F# {; V! B0 Q
vector<int>prime;
- q( o2 p r2 L% _6 m
ll f[3000][3000];
% e x) b/ _0 F' U
& ^6 q+ v8 M5 L
void init() { //素数筛
& R9 B5 |6 e$ k$ {4 L
for(int i = 2;i<= 3000;i++) {
: S% f' D- m% L2 ]" M+ E
if(!vis
) {
4 r0 p E. U, i
for(int j = i*i;j<= 3000;j+= i) {
: A# ] s# G* I, x5 m
vis[j] = true;
, |% n n1 r: T0 t7 I
}
& F2 Z" S: s8 t. k( v/ i
}
2 Q7 w2 o4 T: n( B& X- G0 L
}
2 ]' \, l- Y$ ~9 R, S: Z
for(int i = 2;i<= 2019;i++) {
8 [/ V) g; x9 ^' {2 T& @
if(!vis
) prime.push_back(i);
7 K- _8 D5 @7 \% w- \
}
: m% r2 C! F' |
}
b- f; V8 c+ K1 Y3 K
& s: e ~& P# {: w- [+ c
ll dfs(int pos,int sum) {
: s( O6 Q7 E) d" K- t
if(f[pos][sum]!= -1) return f[pos][sum];
% Z5 I% G5 H( E
if(sum == 2019) return 1;
2 n t5 x+ m$ U; @5 M4 i
if(pos>= prime.size()||sum> 2019) return 0;
$ O/ d0 e& f7 p3 Y5 z% y
4 w8 L) _/ o/ m2 k9 I ~
ll ans = 0;
! J) R9 D P' W# H- C
ans+= dfs(pos+1,sum);// 不要当前这个素数
! c# V5 }5 I r
ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
8 A7 E3 x- F3 Y" Q
return f[pos][sum] = ans;
0 j0 T4 H% @! _% r- |
}
: W) b T0 ]2 A0 }+ Z2 o( ?3 o0 m
: z |( D+ a- r8 q$ n% K0 [9 I
int main() {
3 r: m9 T' p0 U' H- X% @0 e
init();
) I' X% N. K f
& `! L" }6 Z5 p, Y, ]' g
mem(f,-1);
% ~0 D$ Y, L9 q- P6 p% Z
ll ans = dfs(0,0);
; k/ F! z2 Z7 i. P6 S
cout<<ans<<endl;
5 t; x r# S! t7 U% | m5 L9 j8 i
; @% n$ O. R# I9 e! i" i
return 0;
o! X. O+ i$ a
}
5 d, X' C# L5 v
---------------------
) [: M6 O x( m" T" d( r; v8 a" p* }
作者：nka_kun
: c7 F" ~8 H2 c* S9 _; e# T3 s
; l/ }0 b3 \8 | q( L8 l
" S8 Z' E, a0 A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5