博弈

SHU 418 丢史蒂芬妮

Posted on

史蒂芬妮,空,白都是no game no life 里的人物,正值这个月15号剧场版即将上映,看得出来,出题人也是同道中人

这是一道勉强算得上博弈的博弈题。因为很那个……有点无法描述

题意:
给你一个 n × m 的棋盘,每次都只能向右,向下,向右下走质数个位置,哪个人先没路走哪个就算输。

思路:
为什么只能是勉强算得上是博弈,整个局势从最开始就是确定的,先手的空只能走一步,要么必赢,要么必输。嘛~ 这倒是很像空白风格的游戏。
我对每个格子从左上向右下判断,如果我能在之前的格子找到任意一个必输的局势,那么我当前位置必赢。由此不断往下递推即可。

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 505;
int Np[MAXN];
bool win[MAXN][MAXN];
vector<int> pr;

bool check(int x, int y)
{
    int l = max(x - 1, y - 1);
    bool res = false;
    for (int i = 0; !res && pr[i] <= l; i++) {
        if (x > pr[i])
            res |= (!win[x - pr[i]][y]);
        if (y > pr[i])
            res |= (!win[x][y - pr[i]]);
        if (x > pr[i] && y > pr[i])
            res |= (!win[x - pr[i]][y - pr[i]]);
    }
    return res;
}

void init()
{
    for (int i = 2; i < MAXN; i++) {
        if (!Np[i])
            pr.push_back(i);
        for (int j = 0; j < (int)pr.size(); j++) {
            int t = pr[j] * i;
            if (t >= MAXN)
                break;
            Np[t] = true;
            if (i % pr[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            win[i][j] = check(i, j);
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%s\n", win[n][m] ? "Sora" : "Shiro");
    }
    return 0;
}