查看: 2478|回复: 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) {; S% q" |0 _& V9 G
         for(int j = i*i;j<= 3000;j+= i) {6 g) [8 r9 {% q, @; r
            vis[j] = true;
$ D! j5 l) j4 y1 C          }$ `- t/ I2 r* w- f8 L: A
      }! Q0 H) e: W2 c2 n& x3 L9 T
}
8 D' l+ O+ i3 k9 `4 a for(int i = 2;i<= 2019;i++) {
) a2 t3 m# i. |( {4 T) Q( Y# G/ E       if(!vis) prime.push_back(i);* V2 `6 @. c) w- w) ^
}
  i: e$ [2 A$ y* u, W. E}
8 V1 z& t4 h6 f& z( k4 [
" k0 e  `+ z6 c! kll dfs(int pos,int sum) {! g. j( G$ t! T* b3 }+ s! {
if(f[pos][sum]!= -1) return f[pos][sum];8 d5 [5 _+ `% q9 R& @2 ?
if(sum == 2019) return 1;
- o3 \1 ^- V( x* o; T  s if(pos>= prime.size()||sum> 2019) return 0;
2 u) @! r5 @" P7 b+ ]
% o9 j/ F% ]( @5 B) S ll ans = 0;
8 X) ^9 I( Z" x7 o) `" z ans+= dfs(pos+1,sum);// 不要当前这个素数
+ i3 S0 H9 i8 i+ x% f; C ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数( [8 d9 ^# z& V1 _$ D4 }
return f[pos][sum] = ans;6 {/ }8 ]9 ^5 h. ^  u
}7 T, a8 ~, h/ [3 U
* P+ p2 w, v9 D& [' \* G
int main() {
4 V' B$ r' B$ q: Q" y/ i init();
8 i; v3 d# }6 U2 e: F! S9 y( P( B* Z9 o) K1 Y$ }7 z$ |
mem(f,-1);
, t7 [% `% ]) E0 w2 D( f- W: ] ll ans = dfs(0,0);3 e; i7 x6 }2 f. A* @1 C- w5 _- l
cout<<ans<<endl;  e! L5 X0 m, {
) P0 n+ A7 a4 C, m
return 0;
. o/ R2 E$ X7 A6 J$ F4 N}1 ^- }# E- Q# j  O. [: e5 T" c
---------------------
6 `7 k& H2 n* I. V$ Q1 A* k1 y+ ]作者：nka_kun   }2 B% S5 j: N2 W2 K# ^
* h& r' ^" F7 x$ }9 L' i4 a0 v
  L# [( Y. c7 x