29. 坏巧克力

description

两个玩家轮流掰一块​mxn格的巧克力，其中一块1x1​的小块是坏的。每次掰只能顺着方格的边界，沿直线一掰到底。每掰一次，掰的人x把两块中不含坏巧克力的那块吃掉，谁碰到最后那块坏巧克力就算输了。在这个游戏中，先走好还是后走好。

输入描述

输入第一行包含一个整数T [1,100 000]​，表示数据组数。

接下来​T行，每行包括​4个整数m,n,x,y(1<=m,n<=10 000 1<=x<=m 1<=y<=n)​，表示整块巧克力有m​行​n列构成，其中坏的那一块在​x行y​列。

输出描述

对于每组用例，在一行内输出Alice或Bob，分别表示先走好还是后走好。

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 2↵ 1 1 1 1↵ 1 2 1 1↵	以文本方式显示 Bob↵ Alice↵	1秒	64M	0

code

1. 具体原理和算法来自于《算法设计与分析基础》一书

2. 然后这个题转化以后 是把 m-x,n-y,x-1,y-1,分别转换成二进制相加，忽略进位，只要某一位出现1，那么返回alice
3. 代码：

#include <iostream>using namespace std;int main()
{// freopen("file.txt", "r", stdin);int t;  // t组数据cin >> t;int m, n, x, y;int flag = 1;  //第2个while正常退出的标志while(t--) {cin >> m >> n >> x >> y;m -= x;n -= y;x--;y--;flag = 1;while(m || n || x || y) {  //只有全为0了才退出if((m % 2 + n % 2 + x % 2 + y % 2) % 2) {cout << "Alice" << endl;flag = 0;break;}m /= 2;n /= 2;x /= 2;y /= 2;}if(flag)cout << "Bob" << endl;}return 0;
}

贴一个另一个博主的解法，直接相乘https://blog.csdn.net/CN_BIT/article/details/104651239

# include<stdio.h>
#include<stdlib.h>int main(){int num;int i;int u;freopen("file.txt","r",stdin);scanf("%d",&num);int m[num],n[num],x[num],y[num],r[num],a,b,c,d;for(i=0;i<num;i++){scanf("%d %d %d %d",&m[i],&n[i],&x[i],&y[i]);}for(i=0;i<num;i++){a = m[i]-x[i];b=n[i]-y[i];c = x[i]-1;d=y[i]-1;r[i]=a^b^c^d;}for(u=0;u<num;u++){if(r[u])printf("Alice\n");elseprintf("Bob\n");}
}