查看: 2447|回复: 0

2019第十届蓝桥杯B组决赛题解第二题

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 15:49 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

2019第十届蓝桥杯B组决赛题解第二题

求两两不同的素数组成2019的方案数
注意点：并不是两个不同的素数，再者直接搜索应该会TimeLimited，所以用dp或者记忆化搜索，方案数可能很多，记得用long long
结果: 55965365465060
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[12345];
vector<int>prime;
ll f[3000][3000];

void init() { //素数筛
for(int i = 2;i<= 3000;i++) {
      if(!vis) {
  ~' g. E# }6 s/ C; E  H4 f+ E          for(int j = i*i;j<= 3000;j+= i) {
7 M5 W# v4 D( I" p0 A1 `8 R3 O9 b             vis[j] = true;, N) a* R" [* U
         }
8 Z9 m6 k6 ~* P2 U       }+ x: p+ n% Z8 K# @( @  t- ]) {
}8 K3 E/ v* B1 S0 d$ ^5 s
for(int i = 2;i<= 2019;i++) {
' C' p5 k" H% t! T2 }! j5 P       if(!vis) prime.push_back(i);- \8 ^0 v2 M3 Z% L- v
}, d% A! i( R1 g0 O3 g
}
, |% M" f+ |7 W
% Q! e$ |9 E4 J6 n5 cll dfs(int pos,int sum) {) d8 _3 E$ `0 ?: O
if(f[pos][sum]!= -1) return f[pos][sum];
- h* Y9 c* M$ D- k" Y% @- a if(sum == 2019) return 1;: P: S( D% o/ X$ {9 l% P
if(pos>= prime.size()||sum> 2019) return 0;1 @( n5 {2 e  z5 a
0 q/ `% f# T1 p+ ~5 y1 r' w
ll ans = 0;
3 t$ Y7 C, B. z# V8 I ans+= dfs(pos+1,sum);// 不要当前这个素数% b" O, k- ?, [: u2 l+ s
ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数
% }( P  u, n8 P  t) M& ~ return f[pos][sum] = ans;
0 S+ d6 r5 e9 O: ]/ b}
0 ]4 x& V" j8 R3 G8 N& W' p% {
% q+ `, Z# i  ^9 w) Aint main() {
' `! q- i1 p% h9 x' J init();
& W0 m5 @( r; F% @/ }1 n* l0 \5 H& ~0 i; O4 r
mem(f,-1);
4 g/ ^; @% m/ J* F% h ll ans = dfs(0,0);
5 a* r! ?$ `6 b' g  X3 q cout<<ans<<endl;, x5 d5 n$ B* F+ S9 B

% l* H" Z7 c. }+ p/ T; k; J return 0;% Y3 ~) g: |) z
}8 I) S9 B  [1 M8 S  K& }
--------------------- / e) f7 d) u  ^, S  q# V
作者：nka_kun
6 \; }, r2 C5 E2 ]0 [7 |1 N2 I
/ Z$ O4 u, w% q/ E+ @6 [$ A; A/ ~, i# K+ m  d4 m7 @2 l9 T