【bzoj1088】扫雷Mine

  • 本文为博主原创，未经许可不得转载

随机程序又摇出了一道水题，好开心啊

我们发现只要确定了前2个格子是否有雷，就可以确定整列的状态

模拟即可

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 10010
using namespace std;
int n,ans,a[MAXN],f[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int check(){
	for(int i=3;i<=n;++i){
		f[i]=a[i-1]-f[i-1]-f[i-2];
		if(f[i]<0||f[i]>1)  return 0;
	}
	if(a[n]!=f[n]+f[n-1])  return 0;
	return 1;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read(); for(int i=1;i<=n;++i) a[i]=read();
	if(a[1]==0)  ans+=check();
	else if(a[1]==1){
		f[1]=1;  ans+=check(); memset(f,0,sizeof(f));
		f[2]=1;  ans+=check();
	}
	else f[1]=f[2]=1,ans+=check();
	printf("%d\n",ans);
	return 0;
}

本文标题:【bzoj1088】扫雷Mine

文章作者:chty

发布时间:2017年03月31日 - 19时29分

最后更新:2018年03月02日 - 17时32分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,