【 HDU 1538 】A Puzzle for Pirates （海盗博弈论）

BUPT2017 wintertraining(15) #5D

HDU 1538

偷懒直接放个果壳的链接了,感觉比网上直接找这题的题解要更正确、易懂。

海盗博弈论

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

int t,n,m,p,a[10004],ans;

int main() {

	for(int i=2;i<=10000;i<<=1)a[i]=1;

	scanf("%d",&t);

	while(t--){

		scanf("%d%d%d",&n,&m,&p);

		int d=m-(n-1)/2;//贿赂后剩下的

		if(d>=0){

			if(p==n) ans=d;

			else ans=p%2==n%2;

		}else{//不剩

			if(!a[n-m*2]&&p==n)ans=-1;

			else{

				while(!a[n-m*2])n--;//第一个不会扔出去的

				if(p>n) ans=-1;

				else ans=0;//n号海盗有多种分金币的方案，没有人是确定能被分到贿赂的这1金币的

			}

		}

		if(ans==-1)puts("Thrown");

		else printf("%d\n",ans);

	}

	return 0;

}