题目是这样的，游戏规则，每个人轮流将二维空间上的皇后往下，往左或者往斜下45度的方向移动。
谁第一个移动到0,0的位置就获胜。
题目给定你若干个矩形，求矩形中任取一点且该点必胜的概率有概率。
其实是这样的，我们需要把所有的必败点的坐标都求出来。发现在10^6以内的必败点的数量只有70多万个，这样我们可以全部存下来。
其实必败点是这样求得，第一个点为(0,0)，接下来第i个点的坐标为(x,y)，其中x为第一个没有在前面的坐标中间出现过的数字，y=x+i。
这样就把所有的必败的点都求出来了呢，同时由于对称性，我们要把另外一边的点也全部求出来。
这样相当于是存到了两个数组里面。
接下来的就是询问了。对于每个矩形，由于点的坐标是递增的，所以我们可以二分求出边界的满足矩形条件的点，然后就可以瞬间知道有多少个点在矩形里面了。
嗯，题目大概就是这样的。 好好理解吧，很好的一个博弈题目。
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000100
#define ll long long
using namespace std;
bool b[maxn];
int x[2][maxn],y[2][maxn],cur,n,tot,l,r,mid,T,x1,x2,y1,y2,cas=0;
int pos1,pos2;
ll ans,sum,G;
ll gcd(ll A,ll B) { return B==0?A:gcd(B,A%B); }
ll find(int k)
{
l=0,r=tot;
while (l<r)
{
mid=(l+r)>>1;
if (x1<=x[k][mid] && y1<=y[k][mid]) r=mid;
else l=mid+1;
}
pos1=l;
l=0,r=tot;
while (l<r)
{
mid=(l+r)>>1;
if (x[k][mid]<=x2 && y[k][mid]<=y2) l=mid+1;
else r=mid;
}
pos2=l;
return max(0,pos2-pos1);
}
int main()
{
memset(b,false,sizeof b);
cur=n=x[0][0]=y[0][0]=tot=0;
b[0]=true;
while (cur<maxn)
{
n++;cur++;
while (n<maxn && b[n]) n++;
if (n>=maxn) break;
x[0][++tot]=n,y[0][tot]=n+cur;
x[1][tot]=y[0][tot],y[1][tot]=x[0][tot];
b[n]=true;
if (n+tot>maxn) break;
b[n+tot]=true;
}
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
ans=find(0)+find(1);
if (x1==0 && y1==0) ans--;
sum=(ll)(x2-x1+1)*(y2-y1+1);
ans=sum-ans;
printf("Board %d: ",++cas);
if (ans==0)
{
printf("0 / 1
");
continue;
}
G=gcd(ans,sum);
ans/=G,sum/=G;
printf("%lld / %lld
",ans,sum);
}
}