81 条题解
-
3
Sky1231 (sky1231) LV 10 @ 2017-02-15 18:13:06
#include <cstdio> #include <cstring> using namespace std; int n,a[10001],f[10000][2][2]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,0,sizeof(f)); if (a[1]==0) f[1][0][0]=1; else if (a[1]==1) f[1][1][0]=f[1][0][1]=1; else if (a[1]==2) f[1][1][1]=1; for (int i=2;i<n;i++) { if (a[i]==0) f[i][0][0]=f[i-1][0][0]; else if (a[i]==1) { f[i][0][1]=f[i-1][0][0]; f[i][1][0]=f[i-1][0][1]; f[i][0][0]=f[i-1][1][0]; } else if (a[i]==2) { f[i][1][1]=f[i-1][0][1]; f[i][0][1]=f[i-1][1][0]; f[i][1][0]=f[i-1][1][1]; } else f[i][1][1]=f[i-1][1][1]; } if (a[n]==0) printf("%d\n",f[n-1][0][0]); else if (a[n]==1) printf("%d\n",f[n-1][0][1]+f[n-1][1][0]); else if (a[n]==2) printf("%d\n",f[n-1][1][1]); } -
2
数字 | 状态 0 | (0,0,0) 1 | (1,0,0), (0,1,0), (0,0,1) 2 | (1,1,0), (0,1,1), (1,0,1) 3 | (1,1,1)额， 状态一共8个 ，貌似并不需要压缩2333
#include<cstdio> #include<iostream> #define MAXN 10005 using namespace std; int dp[MAXN][2][2][2] = {0}; const int pn[4][3][3] = { {{0, 0, 0}} , {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}} , {{1, 1, 0}, {1, 0, 1}, {0, 1, 1}} , {{1, 1, 1}} }; const int ps[4] = {1, 3, 3, 1}; int main(){ int n, a[MAXN]; cin >> n; for(int i=1; i<=n; i++){ cin >> a[i]; } dp[0][0][0][1] = dp[0][0][0][0] = 1; for(int i=1; i<=n; i++){ int pno = a[i]; int psize = ps[pno]; for(int j=0; j<psize; j++){ dp[i][pn[pno][j][0]][pn[pno][j][1]][pn[pno][j][2]] = dp[i-1][0][pn[pno][j][0]][pn[pno][j][1]] + dp[i-1][1][pn[pno][j][0]][pn[pno][j][1]]; } } int ans = 0; int pno = a[n]; int psize = ps[pno]; for(int j=0; j<psize; j++){ ans += dp[n][pn[pno][j][0]][pn[pno][j][1]][0]; } cout << ans; return 0; }评测情况
O(n)的复杂度跑起来都是毫秒级别~Accepted # 状态 耗时 内存占用 #1 Accepted 3ms 336.0 KiB #2 Accepted 2ms 352.0 KiB #3 Accepted 5ms 344.0 KiB #4 Accepted 2ms 340.0 KiB #5 Accepted 3ms 360.0 KiB #6 Accepted 4ms 384.0 KiB #7 Accepted 4ms 384.0 KiB #8 Accepted 6ms 600.0 KiB #9 Accepted 3ms 600.0 KiB #10 Accepted 5ms 728.0 KiB -
2
并不认为这是个状压DP2333 代码写丑了 对于扫雷资深玩家简直是毁灭性打击，格子里面的数，可能会是0... #include<iostream> using namespace std; int a[10010],dp[10010][2][2][2]; int main() { int i,n,k; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; if(a[1]==0) { dp[1][0][0][0]=1; } if(a[1]==1) { dp[1][0][0][1]=1; dp[1][0][1][0]=1; } if(a[1]==2) { dp[1][0][1][1]=1; } if(a[1]==3) { cout<<"0"; return 0; } for(i=2;i<=n;i++) { if(a[i]==0) { dp[i][0][0][0]=dp[i-1][0][0][0]+dp[i-1][1][0][0]; } if(a[i]==1) { dp[i][1][0][0]=dp[i-1][0][1][0]+dp[i-1][1][1][0]; dp[i][0][1][0]=dp[i-1][0][0][1]+dp[i-1][1][0][1]; dp[i][0][0][1]=dp[i-1][0][0][0]+dp[i-1][1][0][0]; } if(a[i]==2) { dp[i][0][1][1]=dp[i-1][0][0][1]+dp[i-1][1][0][1]; dp[i][1][0][1]=dp[i-1][1][1][0]+dp[i-1][0][1][0]; dp[i][1][1][0]=dp[i-1][0][1][1]+dp[i-1][1][1][1]; } if(a[i]==3) { dp[i][1][1][1]=dp[i-1][0][1][1]+dp[i-1][1][1][1]; } } if(a[n]==0) cout<<dp[n][0][0][0]; if(a[n]==1) cout<<dp[n][1][0][0]+dp[n][0][1][0]; if(a[n]==2) cout<<dp[n][1][1][0]; if(a[n]==3) cout<<"0"; return 0; } -
1
这难度不太对啊，就只考虑当前输入的当前位雷，和之前一位雷，就可以过了。
说明一下：
之前一位和当前位雷是00，也包括开始状态，开始时就当最左边之前雷数都是0：
雷数：000 001
输入： 0 1
之前一位和当前位雷是01：
雷数：010 011
输入： 1 2
之前一位和当前位雷是10：
雷数：100 101
输入： 1 2
之前一位和当前位雷是11：
雷数：110 111
输入： 2 3
每次根据输入做状态转移就行，更像是DFA。具体看下面代码吧。
last表示上一次输入结束的状态转移结果，now表示这次输入的状态转移结果。#include <iostream> using namespace std; int n; long long last[4]={1,1,0,0}; long long now[4]; void exch(int num) { int i; for(i=0;i<4;i++) { now[i]=0; } if(num==0) { now[0]=last[0]; } if(num==1) { now[1]=last[0]; now[2]=last[1]; now[0]=last[2]; } if(num==2) { now[3]=last[1]; now[1]=last[2]; now[2]=last[3]; } if(num==3) { now[3]=last[3]; } for(i=0;i<4;i++) { last[i]=now[i]; } } int main() { cin>>n; int i; int num; for(i=0;i<n-1;i++) { cin>>num; exch(num); } cin>>num; int ans=0; if(num==0) { ans+=now[0]; } if(num==1) { ans+=now[1]; ans+=now[2]; } if(num==2) { ans+=now[3]; } cout<<ans<<endl; return 0; } -
1
完全没有它的分类那么高端。。
一个简单的推理就行。
时间复杂度最大为O(2n)
#include<bits/stdc++.h>
using namespace std;
int a[10010],n,l[10010];
int fs(int x){
if(x==n+1) return 1;
if(x==1){
if(a[x]==0) return fs(x+1);
if(a[x]==1){
l[1]=1;
int ans=fs(x+1);
memset(l,0,sizeof(l));
l[2]=1;
ans+=fs(x+1);
return ans;
}
if(a[x]==2){
l[1]=l[2]=1;
return fs(x+1);
}
return 0;
}
if(l[x-1]+l[x]==a[x]) return fs(x+1);
if(l[x-1]+l[x]>a[x]) return 0;
if(l[x-1]+l[x]+1<a[x]) return 0;
if(x==n) return 0;
l[x+1]=1;
return fs(x+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
printf("%d",fs(1));
return 0;
} -
1
/* f[i][t][k]表示第i行状态为k，下一行状态为t时的种数。 即k==1表示当前i行有雷否则无雷 t==1表示下一行有雷否则无雷 我们知道每一行的状态由之前一行和现在这行和下一行决定 而状态中又包含了当前行和下一行 所以我们只需要从上面行推来即可即dp[i-1][][]推来 即我们就可以根据当前i行的雷数递推 因为我们要求的是方案数 我们知道i行目前某个状态可能的方案数 是要能满足条件的所有方案数递推上来 然后一直推啊推推到第n行即可 根本不用状态压缩OTZ 毕竟我太弱了 其实这道题根本不用保存a[]数组 也可以省去那个f[][][]的第一维变成2维 但是如果用一个二维优化的话 一定要注意因为里面的f[][]是迭代更新的 所以我们不能直接先赋值给一个值再用已经改变了的值去赋值给另一个 而且会有环的关系你会发现不管咋交换都gg 所以我们先用变量存起来再交换就好了 嗯代码在下面2333 */ #include <iostream> #include <cstring> #include <cstdio> using namespace std; int a[10010]; int f[10010][2][2]; //1下一行还需要一个1,0下一行不需要1 int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,0,sizeof(f)); f[0][0][0]=1; f[0][1][0]=1; for (int i=1;i<=n;i++) { if (a[i]==0)//即i-1,i,i+1都无雷 { f[i][0][0]=f[i-1][0][0];//只有f[i][0][0]有值为f[i-1][0][0] } else if (a[i]==1)//有一个雷 { f[i][1][0]=f[i-1][0][0];//下一行有雷，所以上一个状态的当前行和下一行都应该无雷 f[i][0][1]=f[i-1][1][0];//当前行有雷，所以上一个状态的当前行无雷但下一行有雷 f[i][0][0]=f[i-1][0][1];//当前行和下一行无雷，则上一个状态的当前行有雷下一行无雷 } else if (a[i]==2)//有两个雷 { f[i][0][1]=f[i-1][1][1];//当前行有雷且下一行无雷，所以上一个状态的当前行和下一行有雷 f[i][1][0]=f[i-1][0][1];//下一行有雷当前行无雷，所以上一个状态的当前行有雷下一行无雷 f[i][1][1]=f[i-1][1][0];//当前行和下一行有雷，所以上一个状态的下一行有雷当前行无雷 } else if (a[i]==3)//有三个雷 { f[i][1][1]=f[i-1][1][1];//三个都一样要有雷直接从f[i-1][1][1]推过来 } } printf("%d\n",f[n][0][0]+f[n][0][1]);//分成最后一行有无雷的情况相加 } /* #include <iostream> #include <cstring> #include <cstdio> using namespace std; int f[2][2]; int n,w; int main() { scanf("%d",&n); f[0][0]=1; f[1][0]=1; for (int i=1;i<=n;i++) { scanf("%d",&w); if (w==0) { //f[0][0]=f[0][0]; f[1][1]=f[1][0]=f[0][1]=0; } else if (w==1)//有一个雷 { int x=f[0][1],y=f[1][0],z=f[0][0]; f[0][0]=x; f[1][0]=z; f[0][1]=y; f[1][1]=0; } else if (w==2)//有两个雷 { int x=f[1][1],y=f[1][0],z=f[0][1]; f[0][1]=x; f[1][1]=y; f[1][0]=z; f[0][0]=0; } else if (w==3)//有三个雷 { //f[1][1]=f[1][1]; f[1][0]=f[0][1]=f[0][0]=0; } } printf("%d\n",f[0][0]+f[0][1]); } */ -
1
WIZeaz (dg_zyh) LV 8 @ 2016-03-04 18:30:38
状态压缩DP，聪明人可以只更新4种状态。
trick:一看到这种题目大家都觉得第i个数只跟i-1，i，i+1个雷区有关，于是直接保存三个雷区的状态，那么状态总数为8。但是实际上第i-1个雷区的状态已经被d[i-1]保存了，所以实际上只用保存i和i+1雷区的状态就好了。代码：
c++
#include <iostream>
using namespace std;
long d[2][2][10001];
long num[10001];
int main()
{
long i,n;
cin>>n;
for (i=1;i<=n;i++) cin>>num[i];
if (num[1]==1) {d[0][1][1]=1;d[1][0][1]=1;}
else if (num[1]==2) {d[1][1][1]=1;}
else d[0][0][1]=1;
for (i=2;i<n;i++){
if (num[i]==0) d[0][0][i]=d[0][0][i-1];
else if (num[i]==1) {d[0][1][i]=d[0][0][i-1]; d[1][0][i]=d[0][1][i-1]; d[0][0][i]=d[1][0][i-1];}
else if (num[i]==2) {d[1][1][i]=d[0][1][i-1]; d[1][0][i]=d[1][1][i-1]; d[0][1][i]=d[1][0][i-1];}
else {d[1][1][i]=d[1][1][i-1];}
}
if (num[n]==1) {cout<<d[0][1][n-1]+d[1][0][n-1];}
else if (num[n]==2)cout<<d[1][1][n-1];
else cout<<d[0][0][n-1];
return 0;
}
###**其实 cout<<rand()%3 才是真正的做法**
-
1
#include<stdio.h> #include<string.h> bool vis[10010]={0},w[2][10010]; char s[10010]; int ans=0,n; bool daf(){ for(int i=1;i<n;++i){ int t=s[i]-vis[i]-vis[i+1]-vis[i-1]; if(t<0||t>1) return 0; if(t==0) vis[i+1]=0; else vis[i+1]=1; } if(s[n]-vis[n]-vis[n+1]-vis[n-1]) return 0; else { for(int i=1;i<=n;++i) w[ans][i]=vis[i]; return 1; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",s+i); vis[1]=0; ans+=daf(); memset(vis,0,sizeof vis); vis[1]=1; ans+=daf(); printf("%d\n",ans); for(int i=0;i<ans;++i,puts("")) for(int j=0;j<n;++j) printf("%d ",w[i][j+1]); } -
0
/* 看了别人的分析后.... https://blog.csdn.net/chenxiaoran666/article/details/83210584 不用DP, 就一个简单的递推 */ #include <iostream> //[SCOI2005]扫雷 #include <algorithm> #include <cstring> using namespace std; const int maxn = 10002; int B[maxn]; //炸弹行 int num[maxn], n; //提示行 bool check(int b) //判断是否合法 { return b == 1 || b == 0; } int Ans(int start) { memset(B, 0, sizeof(B)); B[1] = start; int i, ans = 0; for (i = 2; i <= n; i++) { B[i] = num[i - 1] - B[i - 1] - B[i - 2]; if (!check(B[i])) break; } if (i == n + 1) if(B[n] + B[n - 1] == num[n]) //最后一项要特判 ans++; return ans; } int main() { int ans = 0; cin >> n; for (int i = 1; i <= n; i++) cin >> num[i]; if(num[1] == 0) ans = Ans(0); else if(num[1] == 2) ans = Ans(1); else if(num[1] == 1) ans = Ans(0) + Ans(1); cout << ans << endl; return 0; } -
0
3344251547 LV 4 @ 2019-07-11 19:12:00
扫雷代码，了解一下
#include<stdio.h>
#include<windows.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
#include<queue>
#include<ctype.h>
#define A 17 //地图的高
#define B 17 //地图的宽
#define C 30 //雷的总数
using namespace std;//全局变量
DWORD a,b;
char map[A][B],news,spare;
int BoomTotalNum,floatx,floaty,flag[A][B],flagnum,mode,slect[A][B],game;//颜色属性
const WORD FORE_BLUE = FOREGROUND_BLUE; //蓝色文本属性
const WORD FORE_GREEN = FOREGROUND_GREEN; //绿色文本属性
const WORD FORE_RED = FOREGROUND_RED; //红色文本属性//开垦地图结构体
struct node {
int x;
int y;
};
queue <node> dui;//打印位置
void position(int x,int y) {
COORD pos={x,y};
HANDLE Out=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(Out,pos);
}//隐藏光标
void Hide() {
HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_CURSOR_INFO CursorInfo;
GetConsoleCursorInfo(handle, &CursorInfo);//获取控制台光标信息
CursorInfo.bVisible = false; //隐藏控制台光标
SetConsoleCursorInfo(handle, &CursorInfo);//设置控制台光标状态
}//初始化
void Beginning() {
while(!dui.empty()) {
dui.pop();
}
game=1;
//BoomTotalNum=C;
floatx=A/2;
floaty=B/2;
flagnum=0;
BoomTotalNum=C;
mode=0;
HANDLE handle_out = GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备句柄
CONSOLE_SCREEN_BUFFER_INFO csbi; //定义窗口缓冲区信息结构体
GetConsoleScreenBufferInfo(handle_out, &csbi); //获得窗口缓冲区信息
int x,y;
srand((unsigned)time(0));
for(int i=0;i<A;i++) for(int j=0;j<B;j++) {
map[i][j]=' ';
flag[i][j]=0;
slect[i][j]=0;
}
while(BoomTotalNum) {
x=rand()%A;
y=rand()%B;
if(map[x][y]==' ') {
map[x][y]='@';
BoomTotalNum--;
}
}
SetConsoleTextAttribute(handle_out, FORE_GREEN);
for(int i=0;i<A;i++) {
for(int j=0;j<B;j++) printf("??");
printf("\n");
}
position(floaty*2,floatx);
SetConsoleTextAttribute(handle_out, FORE_RED);
printf(""); //光标位置
position(44,9);
printf("扫雷模式");
position(44,5);
printf("剩余雷数：%d ",C-flagnum);
SetConsoleTextAttribute(handle_out, FORE_GREEN);
position(5,22);
printf("按“空格”切换模式");
position(5,23);
printf("按“Enter”确认");
position(5,24);
printf("按“方向键”选择方块");}
//打印地图的一块儿
void Lump(int xx,int yy) {
switch(map[xx][yy]) {
case '1' : printf("①");break; //周围雷的数量（下同）
case '2' : printf("②");break;
case '3' : printf("③");break;
case '4' : printf("④");break;
case '5' : printf("⑤");break;
case '6' : printf("⑥");break;
case '7' : printf("⑦");break;
case '8' : printf("⑧");break;
case ' ' :
if(xx==floatx&&yy==floaty) {
if(flag[xx][yy]==0) {
if(mode%2==0) printf("");
else printf("");
}
else printf("");
}
else {
if(flag[xx][yy]==0) printf("??");
else printf("");
}
break;
case '@' :
if(xx==floatx&&yy==floaty) {
if(flag[xx][yy]==0) {
if(mode%2==0) printf("");
else printf("");
}
else printf("");
}
else {
if(flag[xx][yy]==0) printf("??");
else printf("");
}
break;
case 'x' : if(floatx==xx&&floaty==yy) printf(""); else printf(" ");break; //已经挖开的空白
}
}//移动光标
void Move() {
HANDLE handle_out = GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备句柄
CONSOLE_SCREEN_BUFFER_INFO csbi; //定义窗口缓冲区信息结构体
GetConsoleScreenBufferInfo(handle_out, &csbi); //获得窗口缓冲区信息
int xxx,yyy;
xxx=floatx;
yyy=floaty;
switch(news) {
case 72 : floatx--;break; //上
case 80 : floatx++;break; //下
case 75 : floaty--;break; //左
case 77 : floaty++;break; //右
}
if(floatx==-1) floatx=A-1; floatx%=A; //两端穿模处理
if(floaty==-1) floaty=B-1; floaty%=B;position(yyy*2,xxx);
SetConsoleTextAttribute(handle_out, FORE_GREEN);
Lump(xxx,yyy); //删除原位置if(map[floatx][floaty]=='x') {
position(floaty*2,floatx);
printf(" ");
}position(floaty*2,floatx);
SetConsoleTextAttribute(handle_out, FORE_BLUE);
Lump(floatx,floaty); //更新新位置
}//插旗和排雷模式切换
void Mode() {
HANDLE handle_out = GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备句柄
CONSOLE_SCREEN_BUFFER_INFO csbi; //定义窗口缓冲区信息结构体
GetConsoleScreenBufferInfo(handle_out, &csbi); //获得窗口缓冲区信息
mode++;
SetConsoleTextAttribute(handle_out, FORE_BLUE);
position(floaty*2,floatx);
if(mode%2==0) printf("");
else printf("");position(44,9);
if(mode%2==0) {
SetConsoleTextAttribute(handle_out, FORE_BLUE);
printf("扫雷模式");
}
else {
SetConsoleTextAttribute(handle_out, FORE_RED);
printf("插旗模式");
}
}//该点周围地雷数
int Boomnum(int xx,int yy) {
int num=0;
if((xx-1>=0)&&(yy-1>=0)&&(map[xx-1][yy-1]=='@')) num++;
if((xx-1>=0)&&(yy+0>=0)&&(map[xx-1][yy]=='@')) num++;
if((xx-1>=0)&&(yy+1<B) &&(map[xx-1][yy+1]=='@')) num++;
if((xx+0>=0)&&(yy-1>=0)&&(map[xx][yy-1]=='@')) num++;
if((xx+0>=0)&&(yy+1<B) &&(map[xx][yy+1]=='@')) num++;
if((xx+1<A)&&(yy-1>=0) &&(map[xx+1][yy-1]=='@')) num++;
if((xx+1<A)&&(yy+0>=0) &&(map[xx+1][yy]=='@')) num++;
if((xx+1<A)&&(yy+1<B) &&(map[xx+1][yy+1]=='@')) num++;
return num;
}//更新地图
void Open() {
node c;
node d;
while(!dui.empty()) {
dui.pop();
}
c.x=floatx;
c.y=floaty;
dui.push(c);
slect[c.x][c.y]=1;
while(!dui.empty()) {
c=dui.front();
dui.pop();
if(Boomnum(c.x,c.y)!=0) {
map[c.x][c.y]=(Boomnum(c.x,c.y)+48);
continue;
}
else {
map[c.x][c.y]='x';
if((c.x-1>=0)&&(c.y-1>=0)&&(map[c.x-1][c.y-1]==' ')&&(slect[c.x-1][c.y-1]==0)) {
d.x=c.x-1;
d.y=c.y-1;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x-1>=0)&&(c.y-0>=0)&&(map[c.x-1][c.y]==' ')&&(slect[c.x-1][c.y]==0)) {
d.x=c.x-1;
d.y=c.y-0;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x-1>=0)&&(c.y+1<B)&&(map[c.x-1][c.y+1]==' ')&&(slect[c.x-1][c.y+1]==0)) {
d.x=c.x-1;
d.y=c.y+1;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x-0>=0)&&(c.y-1>=0)&&(map[c.x][c.y-1]==' ')&&(slect[c.x][c.y-1]==0)) {
d.x=c.x-0;
d.y=c.y-1;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x-0>=0)&&(c.y+1<B)&&(map[c.x][c.y+1]==' ')&&(slect[c.x][c.y+1]==0)) {
d.x=c.x-0;
d.y=c.y+1;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x+1<A)&&(c.y-1>=0)&&(map[c.x+1][c.y-1]==' ')&&(slect[c.x+1][c.y-1]==0)) {
d.x=c.x+1;
d.y=c.y-1;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x+1<A)&&(c.y-0>=0)&&(map[c.x+1][c.y]==' ')&&(slect[c.x+1][c.y]==0)) {
d.x=c.x+1;
d.y=c.y-0;
dui.push(d);
slect[d.x][d.y]=1;
}
if((c.x+1<A)&&(c.y+1<B)&&(map[c.x+1][c.y+1]==' ')&&(slect[c.x+1][c.y+1]==0)) {
d.x=c.x+1;
d.y=c.y+1;
dui.push(d);
slect[d.x][d.y]=1;
}
}
}
}int main() {
freopen("排名.txt","r",stdin);
Relife: //重玩处
HANDLE handle_out = GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备句柄
CONSOLE_SCREEN_BUFFER_INFO csbi; //定义窗口缓冲区信息结构体
GetConsoleScreenBufferInfo(handle_out, &csbi); //获得窗口缓冲区信息Hide(); //隐藏光标
Beginning();//初始化地图
a=GetTickCount();
while(1) {
if(kbhit()!=0) {
spare=getch();//按其他
if((spare!=(-32))&&(spare!=13)&&(spare!=' ')) continue;//跳过//按Enter
if(spare==13) { //确认
//排雷
if(mode%2==0) {
if(map[floatx][floaty]=='@'&&flag[floatx][floaty]==0) {
break; //触雷
game=0;
}if(flag[floatx][floaty]==1) continue; //有旗跳过
Open();
position(0,0);
SetConsoleTextAttribute(handle_out, FORE_GREEN);
for(int i=0;i<A;i++) {
for(int j=0;j<B;j++) Lump(i,j);
printf("\n");
}
position(floaty*2,floatx);
SetConsoleTextAttribute(handle_out, FORE_BLUE);
Lump(floatx,floaty);
}//插拔旗
else {//不能插旗的地方
if(map[floatx][floaty]=='x'||(map[floatx][floaty]>'0'&&map[floatx][floaty]<'9'))
continue; //跳过//插旗
if(flag[floatx][floaty]==0) {
flagnum++;
flag[floatx][floaty]=1;
position(floaty*2,floatx);
SetConsoleTextAttribute(handle_out, FORE_BLUE);
Lump(floatx,floaty);
}//拔旗
else {
flagnum--;
flag[floatx][floaty]=0;
position(floaty*2,floatx);
SetConsoleTextAttribute(handle_out, FORE_BLUE);
Lump(floatx,floaty);
}
}
}//按空格
if(spare==' ') Mode(); //切换模式//按方向键
if(spare==-32) {
news=getch();
Move(); //移动光标
}
for(int i=0;i<A;i++) for(int j=0;j<B;j++) if(map[i][j]=='x'||(map[i][j]>'0'&&map[i][j]<'9')) game++;
if(game==A*B-C+1) break;
else game=1;
SetConsoleTextAttribute(handle_out, FORE_RED);
position(44,5);
printf("剩余雷数：%d ",C-flagnum);
}
else Sleep(10);
b=GetTickCount();
SetConsoleTextAttribute(handle_out, FORE_RED);
position(44,7);
printf("用时："); //用时
if((b-a)/60000<10) printf("0");
printf("%d:",(b-a)/60000);
if(((b-a)/1000)%60<10) printf("0");
printf("%d:",((b-a)/1000)%60);
if(((b-a)/10)%100<10) printf("0");
printf("%d",((b-a)/10)%100);
}
SetConsoleTextAttribute(handle_out, FORE_RED);
position(5,5);
if(game==1) printf("游戏结束！");
else printf("恭喜通关！");
position(5,8);
printf("任意键重玩");
scanf("%c%c",&spare,&spare);
system("cls");
position(0,0);
goto Relife;
1. 1. 1. 1. 1. > > } -
0
xianggulinger LV 8 @ 2017-10-08 18:30:27
讨论前两个，递推。
#include <iostream> using namespace std; #define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks) #define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks) int n; int nu[20000]; bool bo[20000]; int ans = 0; int main(){ cin >> n; For(i, 1, n){ cin >> nu[i]; if (nu[i] > 3 || nu[i] < 0){ cout << 0 << endl; return 0; } } if (n == 1){ if (nu[1] == 0 || nu[1] == 1){ cout << 1 << endl; return 0; } else{ cout << 0 << endl; return 0; } } if (n == 2){ if (nu[1] != nu[2]){ cout << 0 << endl; return 0; } else if (nu[1] == 0 || nu[1] == 2){ cout << 1 << endl; return 0; } else if (nu[1] == 1){ cout << 2 << endl; return 0; } else { cout << 0 << endl; return 0; } } if (nu[1] == 0){ bo[1] = bo[2] = 0; For(i, 2, n - 1){ if (bo[i - 1] + bo[i] == nu[i]){ bo[i + 1] = 0; } else if (bo[i - 1] + bo[i] == nu[i] - 1){ bo[i + 1] = 1; } else{ cout << 0 << endl; return 0; } } if (bo[n - 1] + bo[n] == nu[n]){ cout << 1 << endl; return 0; } else{ cout << 0 << endl; return 0; } } if (nu[1] == 2){ bo[1] = bo[2] = 1; For(i, 2, n - 1){ if (bo[i - 1] + bo[i] == nu[i]){ bo[i + 1] = 0; } else if (bo[i - 1] + bo[i] == nu[i] - 1){ bo[i + 1] = 1; } else{ cout << 0 << endl; return 0; } } if (bo[n - 1] + bo[n] == nu[n]){ cout << 1 << endl; return 0; } else{ cout << 0 << endl; return 0; } } if (nu[1] == 1){ bo[1] = 1; bo[2] = 0; For(i, 2, n - 1){ if (bo[i - 1] + bo[i] == nu[i]){ bo[i + 1] = 0; } else if (bo[i - 1] + bo[i] == nu[i] - 1){ bo[i + 1] = 1; } else{ goto A; } } if (bo[n - 1] + bo[n] == nu[n]){ // cout << 1 << endl; // return 0; ans++; } else{ goto A; } A:; bo[1] = 0; bo[2] = 1; For(i, 2, n - 1){ if (bo[i - 1] + bo[i] == nu[i]){ bo[i + 1] = 0; } else if (bo[i - 1] + bo[i] == nu[i] - 1){ bo[i + 1] = 1; } else{ goto B; } } if (bo[n - 1] + bo[n] == nu[n]){ ans++; // return 0; } else{ goto B; } B:; cout << ans << endl; return 0; } if (nu[1] == 3){ cout << 0 << endl; return 0; } return 0; } -
0
Accepted
状态 耗时 内存占用
#1 Accepted 1ms 380.0KiB
#2 Accepted 2ms 256.0KiB
#3 Accepted 2ms 256.0KiB
#4 Accepted 3ms 256.0KiB
#5 Accepted 1ms 348.0KiB
#6 Accepted 3ms 256.0KiB
#7 Accepted 4ms 256.0KiB
#8 Accepted 4ms 380.0KiB
#9 Accepted 5ms 256.0KiB
#10 Accepted 3ms 372.0KiB
代码#include<iostream> using namespace std; short a[10010]={0},n,ans=0; bool m[10010][3]={0},f[2]={0}; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(a[1]==0) { m[1][0]=0; f[1]=1; } else { if(a[1]==1) { m[1][0]=1; m[1][1]=0; } else { if(a[1]==2) { m[1][0]=1; f[1]=1; } else { cout<<0; return 0; } } } for(int i=1;i<=n;i++) { for(int j=0;j<2;j++) { if(f[j]==0) { if(a[i]<m[i][j]+m[i-1][j]||a[i]>m[i][j]+m[i-1][j]+1) f[j]=1; if(a[i]==m[i][j]+m[i-1][j]) m[i+1][j]=0; if(a[i]==m[i][j]+m[i-1][j]+1) m[i+1][j]=1; } } } for(int j=0;j<2;j++) if(f[j]==0&&m[n+1][j]==0) ans++; cout<<ans; } -
0
1476073873 LV 5 @ 2016-10-01 17:48:56
编译成功
Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(3,7) Note: Local variable "j" not used
foo.pas(3,9) Note: Local variable "m" not used
Linking foo.exe
26 lines compiled, 0.0 sec, 27792 bytes code, 1268 bytes data
2 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 4712 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 4716 KiB, score = 10
Accepted, time = 0 ms, mem = 4716 KiB, score = 100 -
0
wang_yanheng LV 10 @ 2015-08-12 21:01:58
其实根本不算动态规划。
由于第一行的雷确定，剩下行的雷的分布是可以根据输入信息唯一确定的，因此只需枚举第一行有雷或无雷两种情况，分别确定雷图，判定其是否合法即可。显然，答案仅可能为0，1或2。//vijos p1193
#include <stdio.h>
#include <string.h>
int main(){
int count[10001];
int array[10001];
int num, i, k, flag, answer=0;scanf("%d", &num);
for(i=1; i<=num; i++)
scanf("%d",&count[i]);//case 1: the first grid is empty --> array[1]=0
//case 2: the first grid is non-empty --> array[1]=1
for(k=0; k<=1; k++){
memset(array, 0, sizeof(array));
array[1] = k;
flag = 1;
for(i=1; i<num; i++){
array[i+1] = count[i]-array[i]-array[i-1];
if(array[i+1]>1 || array[i+1]<0){
flag = 0;
break;
}
}
if(array[num]+array[num-1] != count[num])
flag = 0;
if(flag)
answer++;
}
printf("%d\n",answer);return 0;
} -
0
visit_world LV 8 @ 2015-07-18 19:48:22
突然发现答案只有0、1、2的我眼泪掉下来
-
0
。。。这题哪门子的状压。。。裸递推啊：
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 520 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 512 KiB, score = 10
Accepted, time = 0 ms, mem = 520 KiB, score = 100#include <cstdio>
#include <cstring>
#define MAXN 10002
int a[MAXN],f[MAXN],n,ans=0;
bool check() {
for (int i=0;i++<n;) {
int sum=f[i-1]+f[i];
if (sum>a[i]||sum+1<a[i]) return false;
f[i+1]=sum==a[i]?0:1;
}
return f[n+1]?false:true;
}
int main() {
scanf("%d",&n);
for (int i=0;i++<n;) scanf("%d",&a[i]);
for (int i=0;i<2;i++) {
memset(f,0,sizeof(f));
f[1]=i;
if (check()) ans++;
}
printf("%d\n",ans);
return 0;
} -
0
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int sl[8]={0,1,1,2,1,2,2,3};
int n,a[10010];
int f[10010][8];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0][0]=1;
f[0][1]=1;
for(int i=1;i<n;i++)
for(int j=1;j<=7;j++)
if (sl[j]==a[i])
for(int k=0;k<=1;k++)
f[i][j]+=f[i-1][(k<<2)+(j>>1)];
int sum=0;
for(int i=1;i<=7;i++)
if (sl[i]==a[n])
for(int k=0;k<=1;k++)
sum+=f[n-1][(k<<2)+(i>>1)];
printf("%d\n",sum);
return 0;
}70分。。求大神看看哪里错了
-
yzc60991 @ 2013-08-05 18:20:14
真是太坑了。。。竟然会有数字0。。大家一定要注意啊
-
晒下AC代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int sl[8]={0,1,1,2,1,2,2,3};
int n,a[10010];
int f[10010][8];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0][0]=1;
f[0][1]=1;
for(int i=1;i<n;i++)
for(int j=0;j<=7;j++)
if (sl[j]==a[i])
for(int k=0;k<=1;k++)
f[i][j]+=f[i-1][(k<<2)+(j>>1)];
int sum=0;
for(int i=0;i<=7;i++)
if (sl[i]==a[n]&&i==(i>>1<<1))
for(int k=0;k<=1;k++)
sum+=f[n-1][(k<<2)+(i>>1)];
printf("%d\n",sum);
return 0;
}
-
-
0
f[i,j,k]表示前i个位置，第i个空格有j个炸弹（j=0,1)，第i-1个空有k个炸弹，满足a[1]..a[i-1]的总数。
注意a[i]在f[i,j,k]中，不考虑，
最后输出f[n+1,0,1]+f[n+1,0,0]
var
a:array[0..10001]of longint;
f:array[0..10001,0..1,0..1]of longint;
i,j,k,m,n:Longint;
begin
read(n);
for i:=1 to n do
read(a[i]);
f[1,1,0]:=1;
f[1,0,0]:=1;
for i:=2 to n+1 do
for j:=0 to 1 do
for k:=0 to 1 do
begin
if j+k=a[i-1] then
inc(f[i,j,k],f[i-1,k,0]);
if j+k=a[i-1]-1 then
inc(f[i,j,k],f[i-1,k,1]);
end;
writeln(f[n+1,0,0]+f[n+1,0,1]);
end.
Sky1231 (sky1231)
LV 10
@ 2017-02-15 18:13:06
