2010-1158

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题目大意 ==

40000 * 40000 的格子，```(x, y) | (x == 0 || y == 0)``` 是河流。

一个具有人猪二象性的东西从 ```(x, y)``` 开始跳跃，每次跳跃可以到  ```(x - k * y, y)``` 或者 ```(x, y - k * x)``` 。
作为人的时候，他可以做出选择，作为猪的时候，它会随机跳跃。跳过之后会从人变成猪或者从猪变成人，但是如果跳到河里面就不能变了。

这个东西从 ```(x, y)``` 开始跳跃，可以从人和猪里面选择一个身份。

如果这个东西想要最终变成人，问应该选择什么？

== 分析 ==

博弈类题目，很容易确定边界条件（河流），然后按照人或者猪的思考方式，考虑每个格子即可。由于没有后效性，可以使用之前已经确定的格子的结果计算后面的格子。

== 参考程序 ==

{{{
#!cpp
#include <stdio.h>
#include <cstring>
#define N 60000
char a[N];
int x,y;

char& geta(int x0, int y0) {
    return a[x0*y+y0];
}
void calc(int px, int py) {
    // if can jump into river, must use pig
    //  printf("calc %d %d\n", px, py);
    /*if (px % py == 0 || py % px == 0) {
        geta(px,py) = 'P';
        return;
    }*/
    // jump left
    int jh = 0, jp = 0;
    for (int k = 1; k < N; k++) {
        // x - k * y, y
        int xt = (px - k * py);
        if (xt > 0) {
            jh += (geta(xt,py) == 'H');
            jp += (geta(xt,py) == 'P');
            if (jp) goto ret;
        } else break;
    }
    // jump top
    for (int k = 1; k < N; k++) {
        // x - k * y, y
        int yt = (py - k * px);
        if (yt > 0) {
            jh += (geta(px,yt) == 'H');
            jp += (geta(px,yt) == 'P');
            if (jp) goto ret;
        } else break;
    }
    //  printf("calc %d %d\n", px, py);
    // if can only jump to H, use pig
ret:
    if (jp == 0) {
        geta(px,py) = 'P';
        return;
    } else {
        geta(px,py) = 'H';
        return;
    }
}

int main(int argc, char const* argv[])
{
    int nc = 0;
    while(scanf("%d%d", &x, &y) == 2) {
        memset(a, '@', sizeof(a));
        geta(1,1) = 'P';
        for (int i = 2; i <= x; i++) {
            geta(i,1) = 'H';
        }
        for (int i = 2; i <= y; i++) {
            geta(1,i) = 'H';
        }
        for (int yi = 2; yi <= y; yi++) {
            for (int xi = 2; xi <= x; xi++) {
                calc(xi,yi);    
            }
        }
        printf("Case #%d:\n", ++nc);
        for (int xi = 1; xi <= x; xi++) {
            for (int yi = 1; yi <= y; yi++) {
                printf("%c", geta(xi,yi));
            }
            puts("");
        }
    }
    return 0;
}
}}}

题目大意

40000 * 40000 的格子，``(x, y) | (x == 0 || y == 0)`` 是河流。

一个具有人猪二象性的东西从 ``(x, y)` 开始跳跃，每次跳跃可以到 `(x - k * y, y)` 或者 `(x, y - k * x)`` 。

作为人的时候，他可以做出选择，作为猪的时候，它会随机跳跃。跳过之后会从人变成猪或者从猪变成人，但是如果跳到河里面就不能变了。

这个东西从 ``(x, y)`` 开始跳跃，可以从人和猪里面选择一个身份。

如果这个东西想要最终变成人，问应该选择什么？

分析

博弈类题目，很容易确定边界条件（河流），然后按照人或者猪的思考方式，考虑每个格子即可。由于没有后效性，可以使用之前已经确定的格子的结果计算后面的格子。

参考程序

#include <stdio.h>
#include <cstring>
#define N 60000
char a[N];
int x,y;
char& geta(int x0, int y0) {
    return a[x0*y+y0];
}
void calc(int px, int py) {
    // if can jump into river, must use pig
    //  printf("calc %d %d\n", px, py);
    /*if (px % py == 0 || py % px == 0) {
        geta(px,py) = 'P';
        return;
    }*/
    // jump left
    int jh = 0, jp = 0;
    for (int k = 1; k < N; k++) {
        // x - k * y, y
        int xt = (px - k * py);
        if (xt > 0) {
            jh += (geta(xt,py) == 'H');
            jp += (geta(xt,py) == 'P');
            if (jp) goto ret;
        } else break;
    }
    // jump top
    for (int k = 1; k < N; k++) {
        // x - k * y, y
        int yt = (py - k * px);
        if (yt > 0) {
            jh += (geta(px,yt) == 'H');
            jp += (geta(px,yt) == 'P');
            if (jp) goto ret;
        } else break;
    }
    //  printf("calc %d %d\n", px, py);
    // if can only jump to H, use pig
ret:
    if (jp == 0) {
        geta(px,py) = 'P';
        return;
    } else {
        geta(px,py) = 'H';
        return;
    }
}
int main(int argc, char const* argv[])
{
    int nc = 0;
    while(scanf("%d%d", &x, &y) == 2) {
        memset(a, '@', sizeof(a));
        geta(1,1) = 'P';
        for (int i = 2; i <= x; i++) {
            geta(i,1) = 'H';
        }
        for (int i = 2; i <= y; i++) {
            geta(1,i) = 'H';
        }
        for (int yi = 2; yi <= y; yi++) {
            for (int xi = 2; xi <= x; xi++) {
                calc(xi,yi);    
            }
        }
        printf("Case #%d:\n", ++nc);
        for (int xi = 1; xi <= x; xi++) {
            for (int yi = 1; yi <= y; yi++) {
                printf("%c", geta(xi,yi));
            }
            puts("");
        }
    }
    return 0;
}