推广网站怎样做,做网站必备语言,天都城网站建设,广州aso优化题意是这样。给出非常多圆#xff0c;要么两两相离#xff0c;要么包括#xff0c;若删掉一个圆#xff0c;那被他包括的都要删除#xff0c;若某人没有圆给他删#xff0c;那么他就赢了。 。。。知道树上博弈的话。就非常easy。。。不知道的话。这确实是个神题…… 按半… 题意是这样。给出非常多圆要么两两相离要么包括若删掉一个圆那被他包括的都要删除若某人没有圆给他删那么他就赢了。 。。。知道树上博弈的话。就非常easy。。。不知道的话。这确实是个神题…… 按半径上升排序从左往右扫。i扫到第一个j能够包括它的圆建立j到i的连边然后break 这样就建立好了一棵树之后知道这个就非常easy了。。。 树的删边游戏 规则例如以下: 给出一个有 N 个点的树,有一个点作为树的根节点。 游戏者轮流从树中删去边,删去一条边后,不与根节点相连的 部分将被移走。 谁无路可走谁输。 我们有例如以下定理: [定理]叶子节点的 SG 值为 0; 中间节点的 SG 值为它的全部子节点的 SG 值加 1 后的异或和。 当然啦像我这样暴力的写法。交c会超时 #includemap
#includestring
#includecstring
#includecstdio
#includecstdlib
#includecmath
#includequeue
#includevector
#includeiostream
#includealgorithm
#includebitset
#includeclimits
#includelist
#includeiomanip
#includestack
#includeset
using namespace std;
typedef long long ll;
struct Point
{int x,y,r;
}point[20010];
bool cmp(Point a,Point b)
{return a.rb.r;
}
struct Edge
{int to,next;
}edge[20010];
int head[20010],tail;
void add(int from,int to)
{edge[tail].toto;edge[tail].nexthead[from];head[from]tail;
}
int dfs(int from)
{int ans0;for(int ihead[from];i!-1;iedge[i].next)ans^dfs(edge[i].to)1;return ans;
}
int main()
{int T;scanf(%d,T);while(T--){int n;scanf(%d,n);for(int i0;in;i)scanf(%d%d%d,point[i].x,point[i].y,point[i].r);sort(point,pointn,cmp);tail0;memset(head,-1,sizeof(head));for(int i0;in;i){bool flag0;for(int ji1;jn;j)if(ll(point[j].r*point[j].r)ll(point[i].x-point[j].x)*(point[i].x-point[j].x)(point[i].y-point[j].y)*(point[i].y-point[j].y)){flag1;add(j,i);break;}if(!flag)add(n,i);}if(dfs(n)!0)puts(Alice);elseputs(Bob);}
}Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 593 Accepted Submission(s): 164Problem Description There are n circles on a infinitely large table.With every two circle, either one contains another or isolates from the other.They are never crossed nor tangent. Alice and Bob are playing a game concerning these circles.They take turn to play,Alice goes first: 1、Pick out a certain circle A,then delete A and every circle that is inside of A. 2、Failling to find a deletable circle within one round will lost the game. Now,Alice and Bob are both smart guys,who will win the game,output the winners name. Input The first line include a positive integer T20,indicating the total group number of the statistic. As for the following T groups of statistic,the first line of every group must include a positive integer n to define the number of the circles. And the following lines,each line consists of 3 integers x,y and r,stating the coordinate of the circle center and radius of the circle respectively. n≤20000|x|≤20000。|y|≤20000r≤20000。 Output If Alice won,output “Alice”,else output “Bob” Sample Input 2 1 0 0 1 6 -100 0 90 -50 0 1 -20 0 1 100 0 90 47 0 1 23 0 1 Sample Output Alice Bob Author FZUACM Source 2015 Multi-University Training Contest 1 转载于:https://www.cnblogs.com/yangykaifa/p/6897097.html
