暴力sg入門--(牛客暑假多校A-Alice and Bob)

博弈,要么敗要么勝.在我看來,博弈就是一個狀態轉移問題,由必勝態向必敗態兩者之間不斷轉換.常規博弈,比如bash博弈(兩個人取m個物品,最多取n個,先取完勝利)這類,就是找到了必勝必敗的規律來直接找到問題答案,一般要么記規律,要么暴力打表找規律......當然,像nim游戲這類求異或和再判斷的博弈,也可以將問題化為二進制數來尋找規律.你也許會想:博弈就這?但是,這些都是特殊情況,那么在沒有特殊情況的一般博弈里面,我們該如何求呢?為了解決這些,我們引入了sg函式.

必勝點,必敗點

在引入sg函式之前,先引入必勝點(N點)和必敗點(P點)的概念:

顧名思義,必敗點(P)就是前一個選手必定取勝的點,必勝點(N)就是下一個選手將取勝的點,這個點是一個狀態,而狀態轉移的規則:從任何必勝點(N)推,必可以轉移到至少一個必敗點(P),從必敗點(P)轉移,只能進入必勝點(N).游戲由必敗點終結.

mex

另外需要介紹的一個就是mex(s),mex是最小非負數的意思,比如mex(1,3,4)=0,mex=(0,1)=2.mex里面的s是一個集合,他的意思是找出不包含在集合內的最小非負數.而sg函式中,保存的就是mex(該點的前驅節點的所有sg值),這些值都是由已知的終結點--必敗點來進行推,暴力sg就是推出所有可能的結果,從而得到想要的答案.

下面,上題!

鏈接：https://ac.nowcoder.com/acm/contest/11166/A
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

Alice and Bob like playing games. There are two piles of stones with numbers n{n}n and m{m}m. Alice and Bob take turns to operate, each operation can take away k(k>0){k}(k>0)k(k>0) stones from one pile and take away s×k(s≥0)s \times k(s \geq 0)s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.

Please determine who will win the game if both Alice and Bob play the game optimally.

輸入描述:

The first line contains an integer T(1≤T≤104)T(1 \le T \le 10^4)T(1≤T≤104) denotes the total number of test cases.
Each test case contains two integers n,m(1≤n,m≤5×103)n,m(1 \le n,m \leq 5 \times 10^3)n,m(1≤n,m≤5×103) in a line, indicating the number of two piles of stones.

輸出描述:

For each test case, print "Alice" if Alice will win the game, otherwise print "Bob".

示例1

輸入

5 2 3 3 5 5 7 7 5 7 7

5
2 3
3 5
5 7
7 5
7 7

輸出

Bob Alice Bob Bob Alice

Bob
Alice
Bob
Bob
Alice

題目大意是alice和bob玩游戲,有兩堆石頭,他們輪流取,不能繼續操作的就輸了,alice先取.規則是每次一堆取k個(k>0),另一堆取k*s個(s>=0).要輸入一個n控制幾組樣例.輸出就輸出勝者名字.

這題是我打牛客多校遇到的,當時稍微學了一點點博弈,想挑戰來著,結果到最后還是沒過,sg沒學明白(現在也沒學明白).

我一開始就像,嘗試純暴力sg,把所有情況都列舉了在算出來,按照規則,只從必敗點推,可以剪枝優化一下,于是就有了以下代碼:

#include<iostream>
using namespace std;
bool sg[5007][5007];
void init(){
	int i,j,u,k,q,p;
	sg[0][0]=0;
	for(i=0;i<=5000;i++)
	{
		for(j=0;j<=5000;j++)
		{
			if(sg[i][j]!=0)continue;
			for(u=1;u+i<=5000;u++)
			{
				for(k=0;k*u+j<=5000;k++)
				{
					sg[u+i][k*u+j]=true;		
				}
			}
			for(u=1;u+j<=5000;u++)
			{
				for(k=0;k*u+i<=5000;k++)
				{
					sg[k*u+i][u+j]=true;		
				}
			}
		}
	}
	return;
}
int main()
{
	int t,x,y;
	init();
	cin>>t;
	while(t--)
	{
		cin>>x>>y;
		if(sg[x][y]==0)cout<<"Bob"<<endl;
		else cout<<"Alice"<<endl;
	}
	return 0;	
}

代碼很好理解,就是遍歷所有點,是必敗點的話,就從這里出發,按照題意,一邊取k張牌,另一邊取k*s張牌,這些點就都是必勝點,如果遍歷訪問到必勝點就直接continue,因為從必勝點可以推出必勝必敗兩種情況,但是只要遍歷所有必敗點,并且按規則找必勝點,一定就可以找完所有的點的sg值.在按題意多次訪問,就過了.(這里的必勝必敗是相對于Alice來說的,因為一開始(0,0)狀態是相對于Alice的必敗點,只有必敗點才能推出必勝點).

其實這個解法并不是最好的寫法,代碼中sg陣列我本來開的是int型別,超時了,后來改為bool型別,1000ms用了800ms將近900ms,有點卡時間過的意思了.

之前我還有另一段代碼,由于考慮了從必勝點轉化,以及時間復雜度過高的問題,總之就是寫了百行,沒有過,然后去找學長請教,最終把它優化了,代碼如下:

#include<iostream>
using namespace std;
int sg[5007][5007];
void init(){
    for(int i=0;i<=5000;i++){
        for(int j=i;j<=5000;j++){
            if(sg[i][j]==0){
                for(int h=1;i+h<=5000;h++){
                    for(int k=0;j+h*k<=5000;k++){
                        int a=h+i;
                        int b=j+h*k;
                        if(a>b)swap(a,b);
                        sg[a][b]=1;
                    }
                }
                for(int h=1;j+h<=5000;h++){
                    for(int k=0;i+h*k<=5000;k++){
                        int b=h+j;
                        int a=i+h*k;
                        if(a>b)swap(a,b);
                        sg[a][b]=1;
                    }
                }
            }
        }
    }
}

int main()
{
	int tt,t,x,y;
	init();
	cin>>t;
	while(t--){
		cin>>x>>y;
		if(x>y){
			tt=x;
			x=y;
			y=tt;
		}
		if(sg[x][y]==0)cout<<"Bob"<<endl;
		else cout<<"Alice"<<endl;
	}
	return 0;	
}

該段暴力sg時,遍歷就不像上一段代碼,回圈是j必定大于i,這樣就導致main函式進行sg值訪問時,就要按照左小右大的順序才能進行訪問.其實兩段代碼性質上都是暴力sg,只是下面的這段進行了剪枝.就可以不用bool型別,雖然使用了時間肯定會進一步縮短.

總結一下,這個題的思路就是從終結點(0,0)出發,尋找所有必敗點,找到一個必敗點就去逆推出所有必勝點,將所有的情況列舉完,這樣不論問你哪種狀態的勝負情況,都可以直接求出來.

本人是蒟蒻一枚,sg函式也是初學,有什么問題望大佬指正!大家好好刷題!加油!有什么問題一起探討.