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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU328 SG函数  

2012-08-18 13:42:12|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
瞪着SG函数的定义看了好久
然后写了个暴力,印证了网上的SG函数定义
于是便过了
第222题,让我的rank进入前100了

#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

const int MAX=100000+10;

int f[MAX][4],hash[MAX][4];
/*
0 两边不确定
1 确定一边
2 两边同色
3 两边异色
*/
char a[MAX];
int n;

int work(int len,int k)
{
if(hash[len][k])return f[len][k];
hash[len][k]=1;
if(!len)return 0;
if(len==1)
{
if(k==0)return f[len][k]=1;
else if(k==1)return f[len][k]=1;
else if(k==2)return f[len][k]=1;
else return f[len][k]=0;
}else
{
f[len][k]=0;
vector<int> c;
set<int> hash;
int i;
for(i=0;i<=len+1;++i)
c.push_back(0);

if(k==0)c[0]=c[len+1]=0;
else if(k==1)c[0]=1;
else if(k==2)c[0]=c[len+1]=1;
else c[0]=1,c[len+1]=2;

int a1,a2,d;
f[len][k]=0;
for(i=1;i<=len;++i)
{
for(d=1;d<=2;++d)
{
c[i]=d;
if(c[i]!=c[i-1] && c[i]!=c[i+1])
{
if(!c[0])a1=1;
else a1=(c[i]==c[0]?2:3);
if(!c[len+1])a2=1;
else a2=(c[i]==c[len+1]?2:3);
int t1=work(i-1,a1),t2=work(len-i,a2);
hash.insert(t1^t2);
}
c[i]=0;
}
}
for(i=0;i<=len;++i)
if(hash.find(i)==hash.end())
{
f[len][k]=i;
break;
}
return f[len][k];
}
}

int calc(int a,int k)
{
if(k==0)return a&1;
else if(k==1)return a;
else if(k==2)return 1;
else return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i;
scanf("%d",&n);
scanf("%s",a+1);
a[0]=a[n+1]=0;
int last=1,ans=0,k,c,d;
for(i=1;i<=n+1;++i)
if(a[i]!='0' || i==n+1)
{
if(i-1>=last)
{
c=a[last-1];d=a[i];
if(!c || !d)
{
if(c || d)k=1;
else k=0;
}else
{
if(c==d)k=2;
else k=3;
}
ans^=calc(i-1-last+1,k);
}
last=i+1;
}
if(!ans)printf("SECOND\n");
else printf("FIRST\n");
}



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

历史上的今天

评论

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

页脚

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