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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1228][SDOI2009]E&D  

2014-11-25 19:00:14|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1228: [SDOI2009]E&D

找了一节课的规律终于搞出来了
代码真是异常短
题解在代码下方

#include<cstdio>
#include<cstdlib>
int sg(int i,int j){
unsigned long long tmp=2;
for(int re=0;;re++,tmp*=2)
if((i-1)%tmp<tmp/2 && (j-1)%tmp<tmp/2)return re;
}
int n;
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,a,b,tmp;
int nn = scan();
while(nn--){
n = scan()/2;
tmp=0;
for(i=1;i<=n;i++){
a = scan();b = scan();
tmp ^= sg(a,b);
}
if(tmp)printf("YES\n");
else printf("NO\n");
}
return 0;
}

题解:
SG函数
首先给sg函数打个表……发现0的分布好有规律
然后又发现1好像也挺规则的,一堆小三角型
最后发现每个数都是类似的三角形
发现如下规律:

0出现条件
i,j均%2=1
1出现条件
i%4=1,2
j%4=1,2
2出现条件
i,j%8=1,2,3,4

……

得到sg(i,j)=k的必要条件:
(i-1)%2k+1 < 2k

(j-1)%2k+1 < 2k

但是需要注意这里是必要不充分条件,因为每个数字并不是网格状,而是三角形。

为什么呢,因为对于3,它某个合适的位置可能同时也对2合适,那么这个值就是2而不是3

也就是说最sg(i,j)会等于最小的合适的k

i,j109,所以直接暴力从小到大枚举,每次时间是logn

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

历史上的今天

评论

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

页脚

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