- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565623 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174910
- 相册
- 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组决赛题解第二题
; B5 [7 y' o$ P' q* T4 G
7 i e" U4 D( v9 D! f( Y" h( i4 O求两两不同的素数组成2019的方案数
6 R, _/ w B% w8 q1 b$ v% S注意点:并不是两个不同的素数,再者直接搜索应该会TimeLimited,所以用dp或者记忆化搜索,方案数可能很多,记得用long long
9 D; H5 f# C3 q: A结果: 55965365465060
$ n1 `6 x; v: F) K3 u. k$ ~代码:
1 `) X& B+ o7 I* n9 c9 E( l#include<bits/stdc++.h> D/ l+ o; A% c$ `; ~$ t( g
#define mem(a,b) memset(a,b,sizeof(a))
' r0 h! Y2 b6 Z* Jusing namespace std;
4 H" V- f/ @0 Q$ n7 @typedef long long ll;
1 Z# }. G$ O* e2 T9 z7 J ^const int inf = 0x3f3f3f3f;
* o. H6 X$ Q/ sconst int maxn = 3e5+55555;
: N5 o5 ^% l7 @0 }const ll mod = 998244353;2 R% g+ j" x# }! Q, W
const double eps = 1e-7;" D1 G" k" R$ t: ]# }$ y$ T
8 A/ `: K. x/ ~: m$ {! S1 B, H
bool vis[12345];' g2 b5 s2 }% g2 v+ P
vector<int>prime;
7 j& I3 Y& u- `' E% dll f[3000][3000];2 {% F4 e' e ?$ J% I- e
) e6 b) Y4 _3 a3 |& b! }void init() { //素数筛$ P& C, w- u( R) B
for(int i = 2;i<= 3000;i++) {
' ]* B; P1 J: ?5 V6 C if(!vis) {2 [9 v; q/ u: U k
for(int j = i*i;j<= 3000;j+= i) {
/ `9 T( m2 F( Y vis[j] = true;
/ A# a0 Z& A4 U. n }% a0 j7 x, _+ I, E) r1 D
}
+ v z! p- d: e# e6 d [; ? }
: G4 b( X. \* a' L; J for(int i = 2;i<= 2019;i++) {
- ]( C+ a9 B A" m if(!vis) prime.push_back(i);1 P: D' W/ f5 T Q% M) s; L
}& I! S$ T$ B2 H/ t; j
}
5 H* _" O+ b, I, Y _
2 N! H1 s5 Y: oll dfs(int pos,int sum) {
' }4 q2 M& o# H if(f[pos][sum]!= -1) return f[pos][sum];
6 D& D& J% ?$ Q; L9 c3 T9 L if(sum == 2019) return 1;1 X2 E% Z9 p0 E/ v4 z& ?
if(pos>= prime.size()||sum> 2019) return 0;
3 x1 V, T* Q9 f- P# l, b5 x% B' x5 J7 [: k+ j- o
ll ans = 0;% M! ]4 }; S3 ?$ N
ans+= dfs(pos+1,sum);// 不要当前这个素数
3 u4 \3 C4 ?7 P6 K% X' K ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
/ n- r7 B& n9 h; [/ ~ return f[pos][sum] = ans;+ P! k4 R, s" E2 v4 Y, l
}- Z; b4 d: S1 t. H. T/ M! H
2 E$ W- B' |6 @8 F- ]int main() {$ K; p- K6 [: `) R" O$ K* R0 h& z; ]# H
init();
) G7 N4 s! p `7 Z! ^+ J/ a& y& t" o- n
mem(f,-1);+ \" L8 I1 {; P3 W7 _
ll ans = dfs(0,0);) x! X( G/ I5 O" |& y3 m0 D% P/ }9 a
cout<<ans<<endl;% G4 x" G* D4 |& a
7 o- C+ F9 Y2 ^6 t% h8 N: o return 0;! q4 n8 l% u* A. Z- E- @; Q
}1 h; m& V" y/ U- |4 w S
---------------------
/ L( k" x9 X5 Q4 K3 i作者:nka_kun
_* z ]' P6 S3 ~* Y7 {$ b8 t g) q. x5 y( |$ k: n( u+ u7 ?
, S5 o/ l- Q* V8 G- a+ D8 X1 p
|
zan
|