BUPT 大二訓練-博弈

比賽網址

HDU 3595 GG and MM

EVERY SG：

在驗算的過程中，我們可以發現如果X,Y，X>Y而且X / Y==1，則每次從X中取走Y，這步的選擇是固定的，但是當X / Y>=2的情況就不一樣了，可以控制步數。

在這個遊戲中，由于是Every_SG,我們考慮的是步數，

首先，利用輾轉相除法計算最原始的步奏

其次，看誰如果擁有第一個X/Y>=2，便具有優先權，可以控制，将所有的X/Y>=2控制在自己手中，到了最後一個讓自己獲勝。以上的政策全部由奇偶來決定，如果在某一步操作的時候，第一個和第二個滿足X / Y >=2的點，之間原始步奏的奇偶性，如果是相同的奇偶性那麼就不需要改變步數，如果是不同的奇偶性，那麼就要将步數加一以實作最優政策，以此得到最大的步數，判斷奇偶。

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;


template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------------------------------

const int INF=0x3f3f3f3f;
const int MAXN=1010;

int Gcd(int a,int b)
{
    int j=-1;//even   0   odd  1
    int step=0,num=2;
    int f[110]={1,a,b};
    while(f[num])
    {
        f[num+1]=f[num-1]%f[num];
        num++;
    }
    step=num-2;
    for(int i=1;i<num-1;i++)
        if(f[i]>=2*f[i+1])
        {
            if(j>0&&(i&1)!=(j&1))
                step++;
            j=i;
        }
    return step;
}

int main()
{
	int n;
	while(read(n))
	{
		int p,q,ans=0;
		for(int i=0;i<n;i++)
		{
			read(p);read(q);
			if(q>p)
                swap(p,q);
			ans=max(Gcd(p,q),ans);
		}
		if(!(ans&1))
			puts("GG");
		else
			puts("MM");
	}
    return 0;
}

POJ 1704 Georgia and Bob

StairCase博弈：

将之轉化為Nim博弈，把兩個棋子的距離看成一堆石子，因為如果你把左邊的棋子移動任意步數，右邊的棋子跟着移動相同步數就會抵消（例 2 3 3 等同于 2），這樣就轉換成Nim遊戲了。注意，如果是奇數個的棋子，則将右邊擋闆當做棋子輔助運算。

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;


template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------------------------------

const int MAXN=1200;

int a[MAXN];

int main()
{
	int ans,T,i,n;
	read(T);
	while(T--)
	{
		read(n);
		ans=0;
		for(i=0;i<n;i++)
			read(a[i]);
		sort(a,a+n);
		for(i=n-1;i>=1;i-=2)
			ans^= a[i]-a[i-1]-1;
		if(n&1)
			ans^=a[0]-1;
		if(!ans)
		   puts("Bob will win");
  		else
		   puts("Georgia will win");
	 }
	 return 0;
}

HDU 1730 Northcott Game

将之轉化為NIM遊戲，将把每行黑白子的初始距離設為每堆石子的初始數量，當然不同的是，這個石子不僅可以取，還可以增加，但是因為這個增加的數量是有界限的（比如，白棋左移3格，黑棋左移3格，他們之間的差是不變的，是以可以認為和最初的狀态是一樣的，無論如何增加，一定會某一棋子到達邊界，導緻棋子之間的距離再無法增加）。

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------

int main()
{
	int n,m,sum=0;
	while(read(n)&&read(m))
	{
		sum=0;
		for(int i=0;i<n;i++)
		{
			int x,y;
			read(x);read(y);
			sum^=(int)fabs(x-y)-1;	
		}
		if(sum)
			puts("I WIN!");
		else
			puts("BAD LUCK!");
	}
	return 0;
}

POJ 2925 Nim

簡單NIM遊戲的變形：

記n1^n2^n3..^n[m]=x

顯然若x=0,則該局勢為奇異局勢，必輸。

如果把ni變成x^ni，則n1^n2^...^n[i-1]^n[i+1]^...^n[m]^x^ni=0，為奇異局勢。顯然如果ni>x^ni，如果能ni堆中拿走ni-x^ni張牌，則一定會獲勝。

是以隻用統計ni中比x^ni大于的個數，結果就是先拿者獲勝的種數。

<pre name="code" class="cpp">#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;


template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------------------------------

int main (){int n,t,a[1111];while(scanf("%d",&n) && n != 0){int temp=0;for(int i=0;i<n;i++){scanf("%d",&t);temp^=t;a[i]=t;}int ans=0;if(temp!=0){for(int i=0;i<n;i++){int k = 0; for(int j=0;j<n;j++) if(i!=j) k^=a[j];//隻要能夠取到K個，就能夠根據對稱原理獲勝 if(k<=a[i]) ans++;}}printf("%d\n",ans);}return 0;}

POJ 1067 取石子遊戲

裸Wythoff博弈：

你可以根據公式直接得出答案，也可以根據sg推出答案

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;


template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------------------------------

int main()
{
	int m,n;
	while(read(m)&&read(n))
	{
		if(m>n)
			swap(m,n);
		int k = n - m;
		int data = floor(k*(1.0+sqrt(5.0))/2);
		puts(data == m ? "0" : "1");
	}
	return 0;
}

HDU 1907 John

裸反NIM遊戲：

BUPT 大二訓練-博弈

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;


template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//-------------------------------------------------------------------


int main()
{
	int T,n;
    read(T);
    int ans,a,mi;
    while(T--)
    {
        ans=0;mi=-1;
        read(n);
        for(int i=0;i<n;i++)
        	read(a),ans^=a,mi=max(mi,a);
         if(mi>1)
         	if(ans>0)
                puts("John");
          	else
                puts("Brother");
         else
         	if(!ans)
                puts("John");
         	else
                puts("Brother");
    }
    return 0;
}

HDU 1922 a simple stone game

K倍動态減法遊戲：

詳見論文http://wenku.baidu.com/view/32782dea81c758f5f61f67a8.html?re=view

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>

using namespace std;

template<class T>
inline bool read(T &n)
{
    T x = 0, tmp = 1; char c = getchar();
    while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
    if(c == EOF) return false;
    if(c == '-') c = getchar(), tmp = -1;
    while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
    n = x*tmp;
    return true;
}
//------------------------------------------------------------------------

const int MAXN=2000010;

int a[MAXN],b[MAXN];
int n,k,cas=1;

int main()
{
	int T;
	read(T);
	while(T--)
	{
		read(n);read(k);
		int i=0,j=0;
		a[0]=b[0]=1;
		while(a[i]<n)
		{
			i++;
			a[i]=b[i-1]+1;
			while(a[j+1]*k<a[i])
				j++;
			if(a[j]*k<a[i])
				b[i]=b[j]+a[i];
			else
				b[i]=a[i];
		}
		printf("Case %d: ",cas++);
		if(a[i]==n)
			puts("lose");
		else
		{
			int ans;
			while(n)
			{
				if(n>=a[i])
				{
					n-=a[i];
					ans=a[i];
				}
				i--;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

BUPT 大二訓練-博弈

繼續閱讀

Yandex.Algorithm Online Round 3 Sunday, June 15, 2014

CF1394C 計算幾何

leetcode_17.Letter Combinations of a Phone Number

HDU 1286 找新朋友（歐拉函數模闆）

hdu 1286 找新朋友（歐拉函數）

哈理工oj Touring （最短路 dij算法鄰接表 + 隊列）

HDU 1286 找新朋友(歐拉函數)找新朋友

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

CF-346 D. Robot Control(反向建圖spfa)

ACMer成長之路

pat（B）1009. 說反話（逆疊代器）

關于多項式的一點研究及其在ACM競賽中的應用關于多項式的一點研究及其在ACM競賽中的應用

codeforces 838D D. Airplane Arrangements 構造法推公式

HDU Reorder the Books

POJ 1284 Primitive Roots (歐拉函數&原根定理)

hdu 4741 Save Labman No.004（計算幾何） Save Labman No.004