2 qq 37242775 qq_37242775 于 2017.01.04 12:06 提问

POJ 1626 有程序求解析。!!!!!! 30C

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long lld;
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define eps 1e-8
#define pi acos(-1.0)
int Sig(double a)
{
if(a < -eps)
return -1;
return a > eps;
}
struct Point
{
double x,y;
Point(){}
Point(double x0,double y0):x(x0),y(y0){}
void in()
{
scanf("%lf %lf",&x,&y);
}
double len()
{
return sqrt(x*x+y*y);
}
Point operator -(Point pt)
{
return Point(x-pt.x,y-pt.y);
}
};
struct Edge
{
int v,next;
}edge[1000010];
int head[110];
int pos;
void insert(int x,int y)
{
edge[pos].v=y;
edge[pos].next=head[x];
head[x]=pos++;
}
bool in[20];
struct Event
{
double s;
int flag,id;
Event(){}
Event(double s0,int flag0,int id0):s(s0),flag(flag0),id(id0){}
}pp[110];
int qq;
bool cmp(Event a,Event b)
{
return a.s < b.s;
}
Point p[110];
int T1,T2;
int dp[1< int dfs(int mask,int flag)
{
if(dp[mask][flag] != -1)
return dp[mask][flag];
if(flag == 0)
{
if(!(mask&T1))
return 0;
for(int k=0;k if(mask&(1 {
for(int i=head[k];i;i=edge[i].next)
{
int to=edge[i].v;
int next=mask;
next|=1 next^=1 next|=to;
next^=to;
if(!dfs(next,flag^1))
{
dp[mask][flag]=1;
return 1;
}
}
}
dp[mask][flag]=0;
return 0;
}
else
{
if(!(mask&T2))
return 0;
for(int k=8;k if(mask&(1 {
for(int i=head[k];i;i=edge[i].next)
{
int to=edge[i].v;
int next=mask;
next|=1 next^=1 next|=to;
next^=to;
if(!dfs(next,flag^1))
{
dp[mask][flag]=1;
return 1;
}
}
}
dp[mask][flag]=0;
return 0;
}
return (int)"you are so pretty";
}
int main()
{
T1=T2=0;
for(int i=0;i T1+=1 for(i=8;i T2+=1 while(scanf("%lf %lf",&p[0].x,&p[0].y)!=EOF)
{
for(int i=1;i p[i].in();
memset(head,0,sizeof(head));
pos=1;
for(i=0;i {
qq=0;
int T=0;
memset(in,false,sizeof(in));
for(int j=0;j {
if(i == j)
continue;
double d=(p[i]-p[j]).len();
double add=asin(0.8/d);
double angle=atan2(p[j].y-p[i].y,p[j].x-p[i].x);
pp[qq++]=Event(angle-add-eps,-1,j);
pp[qq++]=Event(angle+add+eps,1,j);
}
for(j=0;j {
while(pp[j].s pp[j].s+=pi*2;
while(pp[j].s > pi*2)
pp[j].s-=pi*2;
}
sort(pp,pp+qq,cmp);
for(j=0;j<qq;j++)
{
int id=pp[j].id;
if(pp[j].flag == -1)
in[id]=true;
else
in[id]=false;
}
int mask;
for(j=0;j<qq;j++)
{
int id=pp[j].id;
mask=0;
for(int k=0;k<16;k++)
if(in[k])
mask|=1<<k;
insert(i,mask+T);
if(pp[j].flag == -1)
in[id]=true;
else
in[id]=false;

        }
    }
    memset(dp,-1,sizeof(dp));
    if(dfs((1<<16)-1,0))
        printf("RED\n");
    else
        printf("WHITE\n");
}
return 0;

}

不知道这个游戏是怎么执行的。有没有大神来提点一下。!谢谢

1个回答

dabocaiqq
dabocaiqq   2017.01.14 23:21
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj3177-tarjan求桥/割边
题目大意:有F个牧场,1 给定现有的R条直接连接两个牧场的路,F-1 若low[v]>dfn[u],则(u,v)为割边。但是实际处理时我们并不这样判断,因为有的图上可能有重边,这样不好处理。我们记录每条边的标号(一条无向边拆成的两条有向边标号相同),记录每个点的父亲到它的边的标号,如果边(u,v)是v的父亲边,就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后,发现l
POJ2980大整数乘法
描述 求两个不超过200位的非负整数的积。 输入 有两行,每行是一个不超过200位的非负整数,没有多余的前导0。 输出 一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。 样例输入 12345678900 98765432100 样例输出 1219326311126352690000 代码: #include #include #i
[POJ1521]Huffman编码
[POJ1521]Huffman编码 时间限制: 1 Sec  内存限制: 128 MB 题目描述 输入一个字符串,长度不超过100,仅由大写字母和下划分组成。求用最好的字符编码方式,令总长度最小。 输入 多组数据,每组数据在一行上输入一个字符串,格式如前所述 当遇到END时,表示输入结束 输出 对应每
poj 1626
传送门:http://poj.org/problem?id=1636 题意:有两个监狱,每个监狱有n个人,有m种关系,表示A监狱第i个人不能跟B监狱第j个人在一个监狱,问你最多能换几组人(从A,B监狱互换一个人,ans<=n/2) 方法:首先这是一个很明显的二分图,我们可以很轻松的建边,但交换一次要把所有与这两个人有关的情况都遍历一遍.dp[i][j]表示从A监狱换i个人再从B监狱换j个人是否可
POJ 1985 树的直径(最长链)
题目大意就是求一棵树上距离最远的两个顶点的距离 说是一棵树是因为之前1984题面上说过 然后据说2631跟此题一样 可以随便选择一个点开始进行bfs或者dfs,从而找到离该点最远的那个点(可以证明,离树上任意一点最远的点一定是树的某条直径的两端点之一;树的直径:树上的最长简单路径)。再从找到的点出发,找到据该点的最远点,那么这两点就确定了树的一条直径,两点间距即为所求距离。 这个用反证
uva 1626 Brackets Sequence ❀(动态规划)
状态表示方法:d[ i ][ j ]表示的是一条序列的开始和结束; 状态定义:d[ i ][ j ]表示字串s[ i~j ] 需要添加的数量。 #include #include #include using namespace std; int n; char s[105]; int d[105][105]; bool match(char ch1,char ch2) { if(
uva 1626——Brackets sequence
题意:定义满足 1.空序列 2.()(X)及括号和其括起来的合法序列 3.【】要求和()相同 都是合法的串。 然后给定一段序列,求添加最小的()或【】使得序列合法。 思路: 区间dp。以前做过用堆栈来判断合法性的题目,这道题目同样是经典。 思想是不断分割小区间,当出现(X)时,应该转移到x,即从dp(i,j)转移到dp(i+1,j-1) 如果多于两个字符应该枚举中间
POJ 1849 Two (树形dp 树的直径 两种方法)
POJ 1849 Two (树形dp 树的直径 两种方法)
POJ 1001 求高精度幂(高精度)
Description 对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如,对国债进行计算就是属于这类问题。现在要你解决的问题是:对一个实数R,要求写程序精确计算R的n次方R^n,其中n 是整数并且0.0 < R < 99.999,0< n<=25 Input T输入包括多组R和n。R的值占第 1 到第 6 列,n的值占第8和第9列 Output 对于每组输入,要求输出一行,
poj 2396(有源汇的上下界可行流。。。。。dinic)
上下流相关的网络流的各种问题在Amber大牛的《图论原理》里讲的特备清楚。。。。。资料需要网上下载。。我就把原文摘抄下来吧。。。。。。 问题模型: 给定一个加权的有向图,满足: (1)容量限制条件:                (2)流量平衡条件: