查看: 2512|回复: 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) {
3 d& o# J/ ?1 F6 [4 N9 m          for(int j = i*i;j<= 3000;j+= i) {6 `# i+ J. K+ v3 {/ {
            vis[j] = true;# U+ Y4 i' R, P" J$ E5 {3 l. H+ A
         }
1 X2 i! h' k2 `7 e* b       }
( H% J) D* z2 b9 f }/ |" A" \2 F! T: }5 N: i5 Z# {
for(int i = 2;i<= 2019;i++) {  I' {+ v- ]+ ~: F# I
      if(!vis) prime.push_back(i);
+ q7 y8 M' m9 s$ J/ H4 e0 G. d }1 O& v$ {9 d9 n" Q8 _+ q, V( ^
}
: p; f: ]* J4 }4 U2 R: v# Z* C9 c  s! ^2 z" k
ll dfs(int pos,int sum) {
: g" ?) J1 i7 k+ @- |( }# l0 o if(f[pos][sum]!= -1) return f[pos][sum];, P: S' K. _; I9 t
if(sum == 2019) return 1;5 N1 a8 J3 ?2 E- v
if(pos>= prime.size()||sum> 2019) return 0;
' P, Z) \0 z+ n7 R( p( A! m- p
/ B, Y7 A# Z4 ^7 S' W. D9 v* \ ll ans = 0;
- \8 Z* ?2 x* P! m ans+= dfs(pos+1,sum);// 不要当前这个素数
1 }. U) o0 b7 }& y- M ans+= dfs(pos+1,sum+prime[pos]);// 要当前这个素数5 p' y2 h3 V7 R. a% l/ t6 \
return f[pos][sum] = ans;# k$ T/ G, K' k4 w! J1 b# u# s
}
* s' Z, L* l3 B1 v5 B, Y! v  V6 l
int main() {+ @5 j4 q# i- R. E
init();
% Y- w8 u7 d# x" R! M. y$ D3 Y+ f/ h" {& j" ], c( b
mem(f,-1);
5 R* o  P- P8 ]) ^+ y) S9 T ll ans = dfs(0,0);
) q" h3 M4 \; e3 R" u& ^ cout<<ans<<endl;
. V( v; i! {4 M! z$ _4 l4 y
4 g  W& z( H8 d3 w1 ?$ k3 p. ? return 0;
% k! v: \$ h1 g1 I0 j+ w}
- q# E5 s+ J( b" T3 {$ |# I; K---------------------
6 w% y  n( Y8 l7 @2 B$ o9 N6 E6 k4 y作者：nka_kun 3 P- s" u& p5 R: ]8 S% X

8 W- d# p; V+ a  }
5 U- q& H9 h* L9 h( i8 O7 _; N7 W