NOIP2018 骗分指南

Cover Image

Prologue

据悉,CCF 本人予以承认。它的泄题行为在选手中造成一定的恐慌和混乱,干扰了正常的竞赛秩序,有损竞赛的声誉,也给组织方带来不必要的负担和干扰。

对于 NOI Pro 2018,只要会简单的 DP 和 DFS,就可以轻松在除浙江省外的省份混到 1=。

D1T1 铺设道路

NOIP2013 原题,幼儿园组级别的贪心。时间很宽松,强行做成 O(NlogN)O(N\log N) 也可以随便水过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
int t,d[100000];
void dig(int l,int r) {
if(l>=r) return;
int p,m=0x7fffffff;
for(int i=l;i<r;++i)
if(m>d[i]) m=d[p=i];
for(int i=l;i<r;++i) d[i]-=m;
t+=m;dig(l,p);dig(p+1,r);
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",d+i);
dig(0,n);
printf("%d",t);
return 0;
}

Download

D1T2 货币系统

凑钱让人很自然联想到筛法和背包。大胆猜想可知去掉原货币系统中可以被其他面额组合表示的面额即得到新的货币系统。再拿 100pts。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstring>
#include <algorithm>
int main() {
int T,n,ans,a[100],t[25001];
scanf("%d",&T);
for(;T;--T) {
scanf("%d",&n);
memset(t,0,sizeof(t));t[0]=1;ans=n;
for(int i=0;i<n;++i) scanf("%d",a+i);
std::sort(a,a+n);
for(int i=0;i<n;++i)
if(t[a[i]]) --ans;
else for(int j=0;j<=a[n-1]-a[0];++j) if(t[j]) t[j+a[i]]=1;
printf("%d\n",ans);
}
return 0;
}

Download

D1T3 赛道修建

TL;DR,不然部分分还是很好打的。考虑到已经拿了 200pts,可以放心玩扫雷。

D2T1 旅行

既然是骗分,那么打一个 DFS 拿 60pts 就差不多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
const int N=5e3+1;
int n,m,v[N],g[N][N];
void dfs(int p) {
printf("%d ",p);v[p]=1;
for(int i=1;i<=n;++i)
if(g[p][i]&&!v[i]) dfs(i);
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1,u,v;i<=m;++i)
scanf("%d %d",&u,&v),g[u][v]=g[v][u]=1;
dfs(1);
return 0;
}

Download

D2T2 填数游戏

真的不可做。随便输出点东西拿 20pts 就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <ctime>
#include <cstdio>
#include <cstdlib>
int main() {
srand((unsigned)time(0));
int n,m,ans[4][4]={{0,0,0,0},{0,2,4,8},{0,4,12,36},{0,8,36,112}};
scanf("%d %d",&n,&m);
if(n==1) printf("%d",1<<m);
else if(m==1) printf("%d",1<<n);
else if(n<4&&m<4) printf("%d",ans[n][m]);
else if(n==5&&m==5) puts("7136");
else printf("%d",rand()%1000000007);
return 0;
}

Download

D2T3 保卫王国

部分分给的很足。打个 44pts 的树形 DP 就行。对于要求的点,反向标无穷大即可,没有什么技巧性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
const int N=1e4,oo=1e8;
int _,n,m,p[N],dp[N][2],ver[N],nxt[N],hed[N];
void link(int u,int v) {
ver[++_]=v;nxt[_]=hed[u];hed[u]=_;
ver[++_]=u;nxt[_]=hed[v];hed[v]=_;
}
void init(int a,int x,int b,int y) {
memset(dp,0,sizeof dp);
dp[a][x^1]=dp[b][y^1]=oo;
}
void dfs(int u,int f) {
for(int i=hed[u],v;i;i=nxt[i])
if((v=ver[i])!=f) {
dfs(v,u);
dp[u][0]+=dp[v][1];
dp[u][1]+=min(dp[v][0],dp[v][1]);
}
dp[u][1]+=p[u];
return;
}
int main() {
char s[2];
scanf("%d %d %s",&n,&m,s);
for(int i=1;i<=n;++i) scanf("%d",p+i);
for(int i=1,u,v;i<n;++i) scanf("%d %d",&u,&v),link(u,v);
for(int i=0,a,x,b,y;i<m;++i) {
scanf("%d %d %d %d",&a,&x,&b,&y);
init(a,x,b,y);dfs(1,0);
if(dp[1][0]>=oo&&dp[1][1]>=oo) puts("-1");
else printf("%d\n",min(dp[1][0],dp[1][1]));
}
return 0;
}

Download

Epilogue

在比赛过程中你甚至可以自己写个扫雷玩。最后,你得了 100 + 100 + X + 60 + 20 +44 > 324pts。在浙江省外的省份稳拿 1=。如果不嫌麻烦的话还可以打 D1T3 的部分分再 O(N2)O(N^2) 地把 D2T1 的环跑掉,稳拿 400+pts。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。