UVA11735_Corner the Queens

题目是这样的，游戏规则，每个人轮流将二维空间上的皇后往下，往左或者往斜下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[][maxn],y[][maxn],cur,n,tot,l,r,mid,T,x1,x2,y1,y2,cas=;

int pos1,pos2;

ll ans,sum,G;

ll gcd(ll A,ll B) { return B==?A:gcd(B,A%B); }

ll find(int k)

{

    l=,r=tot;

    while (l<r)

    {

        mid=(l+r)>>;

        if (x1<=x[k][mid] && y1<=y[k][mid]) r=mid;

            else l=mid+;

    }

    pos1=l;

    l=,r=tot;

    while (l<r)

    {

        mid=(l+r)>>;

        if (x[k][mid]<=x2 && y[k][mid]<=y2) l=mid+;

            else r=mid;

    }

    pos2=l;

    return max(,pos2-pos1);

}

int main()

{

    memset(b,false,sizeof b);

    cur=n=x[][]=y[][]=tot=;

    b[]=true;

    while (cur<maxn)

    {

        n++;cur++;

        while (n<maxn && b[n]) n++;

        if (n>=maxn) break;

        x[][++tot]=n,y[][tot]=n+cur;

        x[][tot]=y[][tot],y[][tot]=x[][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()+find();

        if (x1== && y1==) ans--;

        sum=(ll)(x2-x1+)*(y2-y1+);

        ans=sum-ans;

        printf("Board %d: ",++cas);

        if (ans==)

        {

            printf("0 / 1\n");

            continue;

        }

        G=gcd(ans,sum);

        ans/=G,sum/=G;

        printf("%lld / %lld\n",ans,sum);

    }

}