注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

ural 1856 War and Peace  

2013-04-16 16:44:13|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
学校里考试考了这题。。。然后傻逼的我打war结果只拿了5分!!!明明打个peace可以拿95分的。。。结果就完挂了
网上没有题解,于是我就在这题上蛋疼了好久。。。
最后总算在某个东西的启发下把这题搞出来了。。讲讲思路吧,顺便给空间除个草
题意是这样的,n个城市,开始每个城市都驻扎有军队,每次可以进行两种操作,每种操作都是将每个城市的军队移动到指定的城市(每个城市指定的城市是不同的,实际就是每个城市连出去了两条边)。。。两人轮流玩游戏,先手想将所有的军队都集合到一个城市,后手试图阻止这件事情。。问先手是否有必胜策略。
其实题目挺好的。
考虑如果我们能够将所有的点合并到一个点,那么一定可以将任意两个点合并到一个点
如果我们可以将任意两个点合并到一个点,那么一定也可以依次将还没有合并的点一个一个合并。
换言之,充分必要条件就是任意两个点都存在必胜策略将其合并到某个点。
记状态f[a][b][c]表示第一个点在a,第二个点在b,c表示是先手还是后手
具体方式就是利用类似于拓扑排序的bfs将所有一定得走向合并的状态推出来。。
如果所有状态都走向合并,那么就是war了。
问题圆满解决,贴上我的糟糕代码(注意别用vector存边)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=1000+10;

int n,e[MAX][2];
int f[MAX][MAX][2];

typedef pair< pair<int,int>,int > Case;
Case q[MAX*MAX];
int first,last;

pair<int,int> t[MAX*MAX];
int begin[MAX][MAX],tot,next[MAX*MAX];

void add(int a,int b,int c,int d)
{
t[++tot]=mp(c,d);
next[tot]=begin[a][b];
begin[a][b]=tot;
}

void check(int a,int b,int c)
{
if(f[a][b][c]!=-1)
return;
if(c==0)//先手啦
{
int k=0;
REP2(k,0,2)
{
int x=e[a][k];
int y=e[b][k];
if(x>y)
swap(x,y);
if(f[x][y][1]==1)
{
f[a][b][c]=1;
q[last++]=mp(mp(a,b),c);
return;
}
}
return;
}
else//我是后手
{
int k=0,can=0;
REP2(k,0,2)
{
int x=e[a][k];
int y=e[b][k];
if(x>y)
swap(x,y);
if(f[x][y][0]==-1)
can=-1;
}
if(can==-1)
return;
f[a][b][c]=1;
q[last++]=mp(mp(a,b),c);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("wap.in","r",stdin);
freopen("wap.out","w",stdout);
#endif
memset(f,-1,sizeof f);
int i,j,k;
scanf("%d",&n);
REP(i,1,n)
scanf("%d%d",&e[i][0],&e[i][1]);
REP(i,1,n)
REP(j,i,n)
REP2(k,0,2)
{
int a=e[i][k];
int b=e[j][k];
if(a>b)
swap(a,b);
add(a,b,i,j);
}
REP2(j,0,2)
REP(i,1,n)
{
f[i][i][j]=1;
q[last++]=mp(mp(i,i),j);
}
while(first<last)
{
Case c=q[first++];
for(k=begin[c.x.x][c.x.y];k;k=next[k])
{
pair<int,int> next=t[k];
check(next.x,next.y,c.y^1);
}
}
REP(i,1,n)
REP(j,i,n)
if(f[i][j][0]!=1)
{
printf("Peace\n");
return 0;
}
printf("War\n");
return 0;
}


  评论这张
 
阅读(336)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017