网泰网站建设网络推广,企业网站排名优化价格,品牌设计公司vi设计,微信平台如何开发题意:
给定n个嵌套的圆#xff0c;每次可以删除圆以及该圆包含的所有圆#xff0c;不能删除者输。
思路#xff1a;
把每个圆看成一个点#xff0c;把圆的包含关系看成一条单向边#xff0c;那么就化成了一棵树。 然后就是裸的树上删边游戏模型了。 对于树上删边游戏…题意:
给定n个嵌套的圆每次可以删除圆以及该圆包含的所有圆不能删除者输。
思路
把每个圆看成一个点把圆的包含关系看成一条单向边那么就化成了一棵树。 然后就是裸的树上删边游戏模型了。 对于树上删边游戏 1. 叶子节点的sg为0 2. 中间节点的sg为所有儿子节点的sg1的异或和
实际上该题目为树上删边游戏的变形。
#include bits/stdc.h
using namespace std;typedef long long ll;
const int N20005;
int head[N],to[N],nt[N],cnt;
struct circle
{int x,y,r;void read(){scanf(%d%d%d,x,y,r);}
}c[N];
ll pp(ll p){return p*p;
}
bool ok(circle A,circle B){return pp(A.x-B.x)pp(A.y-B.y)pp(A.r-B.r);
}
bool cmp(circle A,circle B){if (A.r!B.r) return A.rB.r;return A.xB.x;
}
void addedge(int u,int v){to[cnt]v;nt[cnt]head[u];head[u]cnt;
}
int dfs(int u){//printf(%d\n, u);int ans0;for (int ihead[u];i;int[i]){ans^(dfs(to[i])1);}return ans;
}
void init(){memset(head,0,sizeof(head));memset(nt,-1,sizeof(nt));cnt0;
}
int main(int argc, char const *argv[])
{int T,n;scanf(%d,T);while (T--){scanf(%d,n);init();for (int i0;in;i) c[i].read();sort(c,cn,cmp);int rtn;for (int in-1;i0;i--){bool ff0;for (int ji-1;j0;j--){if (ok(c[i],c[j])) {ff1;addedge(j,i);break;}}if (!ff) addedge(rt,i);}addedge(rt,0);if (dfs(rt)) puts(Alice);else puts(Bob);}return 0;
}
