ACM-ICPC 2018 徐州赛区网络预赛 B. BE, GE or NE（博弈，记忆化搜索）

题目链接：https://nanti.jisuanke.com/t/31454

 

样例输入1 
3 -8 5 -5
3 1 1
2 0 1
0 2 1
样例输出1 
Good Ending
样例输入2 
3 0 10 3
0 0 1
0 10 1
0 2 1
样例输出2 
Bad Ending

题意：A,B玩游戏，n轮，A先手，给一个数字m，每一轮操作有a，b，c三个选择，a为0则表示没有a这个选择，b，c同理，不可能三个选择都不能选，可以选择+a，-b或*（-1），A希望最后结果大于等于k，B希望最后结果小于等于l，两人都选择最有情况，l<k，若不能使得数字落在自己想要的区间，宁可使得数字落在区间l,k之间

思路：不会做，看了这篇博客：ACM-ICPC 2018 徐州赛区网络预赛 B. BE, GE or NE (博弈,模拟)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int n,m,k,l;
int a[1100],b[1100],c[1100];
int sum(int x){
	if(x>100)return 100;
	if(x<-100)return -100;
	return x;
}

int main(){
	scanf("%d%d%d%d",&n,&m,&k,&l);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	set<int>pre,now;
	for(int i=n;i>=1;i--){
		if(i%2==1){//A选择 
			for(int num=-100;num<=100;num++){
				if(a[i]!=0){
					if(pre.size()==0&&sum(num+a[i])>=k){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(num+a[i]))!=0){
						now.insert(num);
						continue;
					}
				}
				if(b[i]!=0){
					if(pre.size()==0&&sum(num-b[i])>=k){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(num-b[i]))!=0){
						now.insert(num);
						continue;
					}
				}
				if(c[i]!=0){
					if(pre.size()==0&&sum(-num)>=k){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(-num))!=0){
						now.insert(num);
						continue;
					}
				}
			}
		}
		else{//B选择 
			for(int num=-100;num<=100;num++){
				if(a[i]!=0){
					if(pre.size()==0){
						if(sum(num+a[i])<k)continue;
					}
					else{
						if(pre.count(sum(num+a[i]))==0)continue;
					}
				}
				if(b[i]!=0){
					if(pre.size()==0){
						if(sum(num-b[i])<k)continue;
					}
					else{
						if(pre.count(sum(num-b[i]))==0)continue;
					}
				}
				if(c[i]!=0){
					if(pre.size()==0){
						if(sum(-num)<k)continue;
					}
					else{
						if(pre.count(sum(-num))==0)continue;
					}
				}
				now.insert(num);
			}
		}
		pre.clear();
		pre=now;
		if(now.size()==0)break;
		now.clear();	
	}
	if(pre.count(m)!=0){
		printf("Good Ending\n");
		return 0;
	}
	pre.clear();
	now.clear();
	for(int i=n;i>=1;i--){
		if(i%2==0){//B选择 
			for(int num=-100;num<=100;num++){
				if(a[i]!=0){
					if(pre.size()==0&&sum(num+a[i])<=l){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(num+a[i]))!=0){
						now.insert(num);
						continue;
					}
				}
				if(b[i]!=0){
					if(pre.size()==0&&sum(num-b[i])<=l){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(num-b[i]))!=0){
						now.insert(num);
						continue;
					}
				}
				if(c[i]!=0){
					if(pre.size()==0&&sum(-num)<=l){
						now.insert(num);
						continue;
					}
					if(pre.count(sum(-num))!=0){
						now.insert(num);
						continue;
					}
				}
			}
		}
		else{//A选择 
			for(int num=-100;num<=100;num++){
				if(a[i]!=0){
					if(pre.size()==0){
						if(sum(num+a[i])>l)continue;
					}
					else{
						if(pre.count(sum(num+a[i]))==0)continue;
					}
				}
				if(b[i]!=0){
					if(pre.size()==0){
						if(sum(num-b[i])>l)continue;
					}
					else{
						if(pre.count(sum(num-b[i]))==0)continue;
					}
				}
				if(c[i]!=0){
					if(pre.size()==0){
						if(sum(-num)>l)continue;
					}
					else{
						if(pre.count(sum(-num))==0)continue;
					}
				}
				now.insert(num);
			}
		}
		pre.clear();
		pre=now;
		if(now.size()==0)break;
		now.clear();
	}
	if(pre.count(m)!=0){
		printf("Bad Ending\n");
		return 0;
	}
	printf("Normal Ending\n");
	return 0;
}