abc059d <博弈, 打表找规律>

标签：abc059d return int LL long solv include

D - Alice&Brown

如何打表

要善于通过打表展示视觉信息, 从而找到规律;

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int f[100][100];  // 0未定, 1win, 2lose

// 注意这里找先手必胜与必负的方式
// 当我的可以转移到任何一个必输态时, 我就处于必胜态了
int cal1(int a, int b)
{
    // cout << "cal " << a << ',' << b << endl;
    if (f[a][b]) return f[a][b];
    for (int i = 2; i <= a; i += 2) if (cal1(a - i, b + i/2) == 2) return f[a][b] = 1;
    for (int i = 2; i <= b; i += 2) if (cal1(a + i/2, b - i) == 2) return f[a][b] = 1;
    return f[a][b] = 2;
}

void solv()
{
    // // 打表
    f[1][0] = f[0][1] = f[1][1] = 2;
    for (int i = 0; i <= 50; i ++)
    {
        for (int j = 0; j <= 50; j ++)
            cout << (cal1(i, j)==1? "o": "x") << ' ';
        cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

结果如下图:

其中x为先手必输,o为先手必胜,则答案就显而易见了~

code

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

bool cal2(LL a, LL b)
{
    return abs(a-b) > 1;
}

void solv()
{
    LL a, b;
    cin >> a >> b;
    cout << (cal2(a, b) ? "Alice" : "Brown") << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签：abc059d,return,int,LL,long,solv,include
From： https://www.cnblogs.com/o2iginal/p/17500042.html