Game Theory

HDU 5795 || 3032

把x个石子的堆分成非空两(i, j)或三堆(i, j, k)的操作->(sg[i] ^ sg[j])或(sg[i] ^ sg[j] ^ sg[k])是x的后继

 #define pron "hdu5795"

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int sg[maxn + ];

 bool vis[maxn + ];

 int mex(){

     for (int i = ; i <= maxn; i ++)

         if (not vis[i])

             return i;

 }

 int get_sg(int x){

     if (sg[x] != -)

         return sg[x];

     memset(vis, false, sizeof vis);

     for (int i = ; i < x; i ++){

         int temp = get_sg(i);

         vis[temp] = true;

         for (int j = ; j < x - i; j ++)

             vis[temp ^ get_sg(j) ^ get_sg(x - i - j)] = true;

     }

     return sg[x] = mex();

 }

 int get_sg(int x){

     if (x %  == )

         return x - ;

     if (x %  == )

         return x + ;

     return x;

 }

 int main(){

 #ifndef online_judge

     freopen(pron ".in", "r", stdin);

 #endif

     int tcase, n, flag, temp;

     scanf("%d", &tcase);

     while (tcase --){

         flag = ;

         scanf("%d", &n);

         for (int i = ; i < n; i ++){

             scanf("%d", &temp);

             flag ^= get_sg(temp);

         }

         if (flag)

             puts("first player wins.");

         else

             puts("second player wins.");

     }

 }

5795

 #define PRON "hdu3032"

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int MAXN = ;

 bool vis[MAXN + ];

 int sg[MAXN + ];

 int mex(){

     for (int i = ; i <= MAXN; i ++)

         if (not vis[i])

             return i;

 }

 int get_sg(int x){

     if (sg[x] != -)

         return sg[x];

     memset(vis, false, sizeof vis);

     int temp;

     for (int i = ; i < x; i ++){

         temp = get_sg(i);

         vis[temp] = vis[temp ^ get_sg(x - i)] = true;

     }

     return sg[x] = mex();

 }

 int get_SG(int x){

     if (x %  == )

         return x - ;

     if (x %  == )

         return x + ;

     return x;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen(PRON ".in", "r", stdin);

 #endif

     memset(sg, -, sizeof sg);

     int Tcase, n, temp, flag;

     scanf("%d", &Tcase);

     while (Tcase --){

         flag = ;

         scanf("%d", &n);

         while (n --){

             scanf("%d", &temp);

             flag ^= get_SG(temp);

         }

         if (flag)

             puts("Alice");

         else

             puts("Bob");

     }

 }

3032

HDU 1536 || 1944

直接get_sg，不需要打表找规律

 #define PRON "hdu1536"

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int MAXK =  + ;

 const int MAXN = ;

 bool vis[MAXN + ];

 int k, Tcase, n, h, flag, s[MAXK], sg[MAXN + ];

 int mex(){

     for (int i = ; i <= MAXN; i ++)

         if (not vis[i])

             return i;

 }

 void get_sg(){

     memset(sg, , sizeof sg);

     for (int i = , j; i <= MAXN; i ++){

         memset(vis, false, sizeof vis);

         j = ;

         while (i >= s[j] && j < k)

             vis[sg[i - s[j ++]]] = true;

         sg[i] = mex();

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen(PRON ".in", "r", stdin);

 #endif

     while (scanf("%d", &k) ==  && k){

         for (int i = ; i < k; i ++)

             scanf("%d", &s[i]);

         sort(s, s + k);

         get_sg();

         scanf("%d", &Tcase);

         while (Tcase --){

             flag = ;

             scanf("%d", &n);

             for (int i = ; i < n; i ++){

                 scanf("%d", &h);

                 flag ^= sg[h];

             }

             if (flag)

                 putchar('W');

             else

                 putchar('L');

         }

         putchar();

     }

 }

1536

Codeforces 768E

取石子，但是对于每一堆，不能取相同的个数。比如这一堆被拿走了x个，下一次就不能再拿x个了。

官方题解用的dp。但这道题可以...

处理一个数组a[i], 表示取完i个石子最多需要的步骤数，即 1 + 2 + .... + a[i] <= i。由于是后手，所以前者采取什么策略我就可以采取什么策略，因此求一个异或和就好。

#define PRON "768e"

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = ;

int n, a[maxn];

int main(){

#ifndef ONLINE_JUDGE

    freopen(PRON ".in", "r", stdin);

#endif

    memset(a, , sizeof a);

    for (int i = , j = ; i <= ; i ++){

        while (j * (j + ) /  <= i)

            ++ j;

        a[i] = -- j;

    }

    scanf("%d", &n);

    int flag = , p;

    while (n --){

        scanf("%d", &p);

        flag ^= a[p];

    }

    puts(flag ? "NO" : "YES");

}

768E

巴特西

Game Theory

最新文章

热门文章