ABC206F Interval Game 2

洛谷 ABC206F Interval Game 2

题目大意

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

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

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

有$t$组数据。

数据范围

1≤t≤20,1≤n≤100,1≤li<ri≤1001\\leq t\\leq 20,1\\leq n\\leq 100,1\\leq l_i<r_i\\leq 1001≤t≤20,1≤n≤100,1≤li​<ri​≤100

题解

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

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

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

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

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

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;
}