BZOJ4171 : Rhl的游戏
2023-09-11 14:15:04 时间
把第一行每个位置设成未知量,对于之后每一行,都可以用第一行的未知量线性表示。
那么只需要加上最后一行的$m$个方程,对于不能按的那$k$个位置也列出对应的方程。
用高斯消元判断是否有解即可,时间复杂度$O(\frac{n^3}{64})$。
#include<cstdio> #include<algorithm> #include<bitset> #define N 260 using namespace std; int T,C,n,m,k,cnt,i,j,t,x,y;char s[N][N];bitset<N>f[N][N],a[N*2]; bool solve(){ scanf("%d%d%d",&n,&m,&k); for(i=1;i<=n;i++)scanf("%s",s[i]+1); for(j=1;j<=m;j++)f[1][j].reset(),f[1][j][j]=1; for(i=2;i<=n;i++)for(j=1;j<=m;j++){ f[i][j]=f[i-1][j]^f[i-2][j]; if(j>1)f[i][j]^=f[i-1][j-1]; if(j<m)f[i][j]^=f[i-1][j+1]; if(s[i-1][j]=='B')if(f[i][j][m+1])f[i][j][m+1]=0;else f[i][j][m+1]=1; } cnt=0; for(j=1;j<=m;j++){ a[++cnt]=f[n][j]; if(j>1)a[cnt]^=f[n][j-1]; if(j<m)a[cnt]^=f[n][j+1]; if(n>1)a[cnt]^=f[n-1][j]; if(s[n][j]=='B')if(a[cnt][m+1])a[cnt][m+1]=0;else a[cnt][m+1]=1; } while(k--)scanf("%d%d",&x,&y),a[++cnt]=f[x][y]; for(i=j=1;i<=m;i++){ for(t=0,k=j;k<=cnt;k++)if(a[k][i]){t=k;break;} if(!t)continue; swap(a[j],a[t]); for(k=j+1;k<=cnt;k++)if(a[k][i])a[k]^=a[j]; j++; } for(i=1;i<=cnt;i++){ for(j=1;j<=m;j++)if(a[i][j])break; if(j>m&&a[i][m+1])return 0; } return 1; } int main(){ scanf("%d",&T); for(C=1;C<=T;C++)printf("Case #%d:\n",C),puts(solve()?"YES":"NO"); return 0; }
相关文章
- (NO.00001)iOS游戏SpeedBoy Lite成形记(二十一)
- (NO.00001)iOS游戏SpeedBoy Lite成形记(十八)
- 101editor编辑游戏快速通关
- Direct3D 开发之旅 3D 游戏基本概念的介绍1
- win8 开发之旅(5) --五子棋游戏开发
- Java实现 蓝桥杯 算法提高 抽卡游戏
- Java实现 LeetCode 488 祖玛游戏
- java实现 洛谷 P1427 小鱼的数字游戏
- java实现第八届蓝桥杯生命游戏
- Java实现 蓝桥杯 历届试题 数字游戏
- Qt项目实战:方块游戏
- 【肝帝游戏】手把手教你python处理视频,越学越有趣,全部源码奉上,不信试试?
- 【LeetCode Python实现】二次元日麻游戏 雀魂麻将
- Python游戏开发入门:pygame实例运动的小球-5
- Unity3D游戏开发之开发游戏带来的问题
- C#开发的OpenRA的游戏主界面怎么样创建2
- Cocos2D-X2.2.3学习笔记9(处理重力感应事件,移植到Android加入两次返回退出游戏效果)
- 3D游戏从入门到精通-20
- 汪子熙趣味成语接龙游戏的设计初衷