两个人的策略是显然的：因为先选的是高位，所以先手选最大数，后手选最小数
所以可以用一个set来维护当前可以拿的cube
这题刚开始想了一个拓扑排序，但这显然不对
例如 * 下一行左边的和右边的是可以拿走的
***
一个重要的结论是，一个方块可以拿，当且仅当所有以他为根基的方块都有不止一个根基
所以以这个方法先选出所有的可拿方块
然后每删除一个方块，就在以他为中心的5*5范围内（这是可波及影响的最大范围）判断可拿性是否有变动（注意已经拿过的记为false，不参与计算）
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define Pair pair<int,int> #define LOWBIT(x) x & (-x) using namespace std; const LL MOD=1e9+9; int n; bool visited[100048]; Pair a[100048]; map<Pair,int> m; set<int> s; inline int cnt(int x,int y) { int res=0; for (int i=-1;i<=1;i++) if (m[mp(x+i,y-1)] && !visited[m[mp(x+i,y-1)]]) res++; return res; } inline bool isleaf(int num) { int xx=a[num].x,yy=a[num].y,i; for (i=-1;i<=1;i++) if (m[mp(xx+i,yy+1)] && !visited[m[mp(xx+i,yy+1)]] && cnt(xx+i,yy+1)==1) return false; return true; } void update(int num) { int i,j,xx=a[num].x,yy=a[num].y,id; for (i=xx-2;i<=xx+2;i++) for (j=yy-2;j<=yy+2;j++) { //if (visited[i][j]) continue; id=m[mp(i,j)]; if (m[mp(i,j)]==0) continue; if (visited[id]) continue; if (s.find(id)!=s.end()) s.erase(id); if (isleaf(id)) s.insert(id); } } int main () { int i; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); m[a[i]]=i; } for (i=1;i<=n;i++) if (isleaf(i)) s.insert(i); int t=0; LL num; LL ans=0; for (i=1;i<=n;t^=1,++i) { //cout<<i<<endl; if (t==0) { //cout<<s.size()<<endl; num=(LL)*(--s.end());//cout<<"*"; ans=((ans*n)%MOD+num-1)%MOD; s.erase(--s.end()); visited[num]=true; update(num); } else { num=(LL)*s.begin(); ans=((ans*n)%MOD+num-1)%MOD; s.erase(s.begin()); visited[num]=true; update(num); } } cout<<ans<<endl; return 0; }