ABC206F Interval Game 2

洛谷 ABC206F Interval Game 2

题目大意

有$n$个作左闭右开的区间$[l_i,r_i)$，Alice和Bob用这些区间玩一个游戏。Alice和bob轮流做如下操作，Alice先手：

• 从这$n$个区间中选择一个区间，这个区间和之前选中的区间不能有重叠部分

如果轮到一个玩家时这个玩家不能再操作了，则这个玩家输。如果Alice和Bob都采用最优策略，问最终谁会赢？

有$t$组数据。

数据范围

$1\le t\le 20,1\le n\le 100,1\le l_i<r_i\le 100$

题解

根据数据范围可得，$l_i$和$r_i$的范围很小，所以我们可以令$sg(l,r)$表示在$[l,r)$之间的区间中进行游戏的$sg$值。

在求$sg(l,r)$时，枚举当前选的区间，设选择区间$[l_i,r_i)$，则选择后的状态为$sg(l,l_i)xorsg(r_i,r)$。对每个区间$[l_i,r_i)$，求选择后的状态，最后求$mex$，即可求出$sg(l,r)$。

因为每次向下一层至少会使区间的长度减少一，所以状态数最多只会在100左右，所以求$mex$时的桶只需要开100多一点。

为了避免重复求同一个$sg(l,r)$，可以用记忆化搜索存储sg值。最后的答案为$sg(1,100)$。

时间复杂度为$O(t\times n^3)$。

code

#include<bits/stdc++.h>
using namespace std;
int t,n,p[105][105];
struct node{
	int x,y;
}w[105];
int gt(int l,int r){
	if(p[l][r]!=-1) return p[l][r];
	int z[205];
	memset(z,0,sizeof(z));
	for(int i=1;i<=n;i++){
		if(w[i].x>=l&&w[i].y<=r){
			z[gt(l,w[i].x)^gt(w[i].y,r)]=1;
		}
	}
	int x=0;
	for(;z[x];x++);
	p[l][r]=x;
	return p[l][r];
}
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		memset(p,-1,sizeof(p));
		for(int i=1;i<=n;i++){
			scanf("%d%d",&w[i].x,&w[i].y);
		}
		if(gt(1,100)) printf("Alice\n");
		else printf("Bob\n");
	}
	return 0;
}