- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565622 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174909
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
2019第十届蓝桥杯B组决赛题解第二题, Y7 y' ]! @6 [, | @( J* i4 [. ~2 R
6 g! ?+ ~& S" F7 m* s0 _# E; L% y) S
求两两不同的素数组成2019的方案数
* _9 a5 k" I0 T6 C* w8 L% g! w注意点:并不是两个不同的素数,再者直接搜索应该会TimeLimited,所以用dp或者记忆化搜索,方案数可能很多,记得用long long
: f" W' t$ g6 H( j; Y* U! j结果: 55965365465060
& M- f" N7 t+ c( k代码:6 `* N! D; A! i
#include<bits/stdc++.h>. g" y6 S/ ^& \% R) o J5 Y
#define mem(a,b) memset(a,b,sizeof(a))
! [6 d, H' h# } W+ susing namespace std;
) U# e; F. G, v0 X6 M& ftypedef long long ll;
! Z5 V ^7 i9 t' D& nconst int inf = 0x3f3f3f3f;& j( p+ }$ H( b7 J! } A; ?
const int maxn = 3e5+55555;6 P0 k' Q# h, V( M
const ll mod = 998244353;
5 x2 D5 m1 ~( z9 |/ A" ]) {0 |8 n9 Zconst double eps = 1e-7;6 F9 ^2 X$ b% \6 p' t+ f
+ s0 K0 ]# u% U# X0 a/ g4 wbool vis[12345];
$ m& C: w" m0 d0 a$ @2 k8 W- dvector<int>prime;
R6 S" o) r( x0 K6 I+ U: |4 ^$ Dll f[3000][3000];. Y2 Q) ~$ e6 x
1 U5 O) I9 W4 Y) `+ n1 B' J, }void init() { //素数筛
3 _- O4 P3 I u# D; d5 B! N2 u for(int i = 2;i<= 3000;i++) { ~$ |1 _+ q7 |' P( v/ R
if(!vis) {- D5 p! o' t1 ]4 n0 ?% k, x" a9 P% P/ A
for(int j = i*i;j<= 3000;j+= i) {2 G$ K4 J/ `% b
vis[j] = true;
+ ] k; O! ?+ F: N7 m b7 V }" e8 F% ]' r0 {( D* Y1 v
}: b0 z w( H& d" }
}# G; x6 y4 q$ V, O5 m
for(int i = 2;i<= 2019;i++) {
8 L' g7 H1 n; a2 |$ W( j" W! \ if(!vis) prime.push_back(i);
) ^3 a4 a: S9 v# X' i: { }
$ Q& N3 Y) l8 |% x2 X8 e}" C7 K. ^2 k" t5 ?
8 R+ z9 w" T8 F0 Sll dfs(int pos,int sum) {
! q: } f- M" V. |& m if(f[pos][sum]!= -1) return f[pos][sum];
# o/ D, O- A" f2 z if(sum == 2019) return 1;
* a9 W* j8 B7 m Q" q9 b if(pos>= prime.size()||sum> 2019) return 0;
5 n' M- ~" O9 ?# I2 C
) |" H* A. c3 O5 O7 T9 t, \ ll ans = 0;( U$ P% Y( _; r3 K% ?# X0 v
ans+= dfs(pos+1,sum);// 不要当前这个素数
2 T& e9 S5 r! S* z% z/ _' k, _ ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数& y* d1 n. T8 o$ Y' b) Q
return f[pos][sum] = ans;( k) H# i% o5 Y9 z6 }0 k6 ]5 v
}7 k! f- y: S0 U
: X, `6 S/ k: kint main() {/ Y5 A4 l; u* h+ Z2 O. a
init();, Z. T* C% L5 V- v1 r# O) G
- d/ F) `; r6 i7 F6 R& ` mem(f,-1); F0 q6 R# A0 K' e
ll ans = dfs(0,0);, X( y; q, o2 w# Z( b
cout<<ans<<endl;
' W' b K0 d: W/ p$ E: u7 B' a- U- q# k$ |" k/ L9 ~' x9 ?
return 0;% I& T* @8 d: ?/ m. t! u- P! I7 ~
}# s' O9 q: X: |, \7 l$ G
--------------------- ! E+ X1 I& y9 y( E: A: W( ]! G
作者:nka_kun * G+ [# l7 k; f- k( P
; N; l( i. l# \5 y9 }9 |8 P8 C4 ]8 l. ~7 P( P- N F# C0 N( a y
|
zan
|