hdu 4642 Fliping game

http://acm.hdu.edu.cn/showproblem.php?pid=4642

对于给定的矩阵 操作步数的奇偶性是确定的

奇数步Alice赢 否则Bob赢

从左上角向右下角遍历遇到1就进行一次处理 遍历到 (x,y) 的时候必须保证 所有(x,y)左上方的点都处理完了

可以根据左上方处理时对(x,y)产生的影响 判断(x,y)的状态

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<list>
using namespace std; typedef long long ll;
typedef pair<double,double>ppd;
const double PI = acos(-1.);
const double eps = (1e-9);
const int MOD=10007;
const int N=105;
int a[N][N];
int c[N][N];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
for(int i=x;i<N;i=i+lowbit(i))
for(int j=y;j<N;j=j+lowbit(j))
++c[i][j];
}
int get(int x,int y)
{
int tmp=0;
for(int i=x;i>=1;i=i-lowbit(i))
for(int j=y;j>=1;j=j-lowbit(j))
tmp+=c[i][j];
return tmp;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
for(int ca=1;ca<=T;++ca)
{
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
int ans=0;
for(int i=1;i<=n;++i)
{
for(int x=i,y=1;x>=1&&y<=m;--x,++y)
if((a[x][y]+get(x,y))&1)
{
++ans;
add(x,y);
}
}
for(int j=2;j<=m;++j)
{
for(int x=n,y=j;x>=1&&y<=m;--x,++y)
if((a[x][y]+get(x,y))&1)
{
++ans;
add(x,y);
}
}
if((ans&1))
printf("Alice\n");
else
printf("Bob\n");
}
return 0;
}
上一篇:“一寸光阴一寸金,寸金难买寸光阴。”


下一篇:Python | Seaborn可视化合集 | 分布图(Distribution)之小提琴图