ゲームレコード

title:ゲームdate:2019-07-19 16:40:06 tags:

ゲーム

ブラシ問題categories:

ACM-ゲーム理論

ゲーム理論は、かつて見た感じが分からなかったもので、今はもう一度見なければなりませんが、この部分を大体理解しただけで、主にsg関数の使用でしょう.

クラシックゲーム

クラシックゲームはいくつかありますが、それぞれの局面と取り方と処理方法を覚えておけばいいのです.
ここのブログはよく話しています.
そしてこれ
ここ

フェアコンビネーションゲーム(Impartial Combinatori Games)

ここではsg関数の使用ですが、主にPN点は必敗と必勝状態がsg関数の中でどのように体現されているか、mex()の求め方を表しています.
複数のゲームの問題は古典的なゲームの異或を利用して各ゲームのsg値の異或和を求めて判断することができ、
sg関数を用いたゲームの可能な2つのボード:

時計を打つ

最もよく使われますが、複数のグループが入力され、各グループの取り方が異なると爆発する可能性があります.

//f[]  ， ， ，sg[] ，0 
int f[maxn], fn, sg[maxn];
bool vis[maxn];
void getsg(int n)
{
    memset(sg, 0, sizeof sg);
    for(int i = 1; i <= n; ++i)
    {
        memset(vis, false, sizeof vis);
        for(int j = 1; f[j] <= i && j <= fn; ++j)vis[sg[i - f[j]]] = true;
        for(int j = 0;; ++j)if(!vis[j]){sg[i] = j; break;}
    }
}

dfs記憶化検索

メーターが爆発する可能性がある場合は検索でsgを求めます

int f[105], sg[maxn], n, m, fn;
int dfsg(int num)
{
    if(~sg[num])return sg[num];
    bool vis[105];
    memset(vis, false, sizeof vis);
    for(int i = 1; i <= fn && f[i] <= num; ++i)
    {
        dfsg(num - f[i]);
        vis[sg[num - f[i]]] = true;
    }
    for(int i = 0;; ++i){if(!vis[i])return sg[num] = i;}
}

練習問題

[kuangbin]特集36ゲーム論(II)
[kuangbin]特集35ゲーム論(I)
もう少し問題を補う時間があるでしょう、、、
(end)