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

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

TC SRM 556 DIV1  

2012-09-14 20:07:38|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很长时间没做TC了,做了一次,结果250pt的题目没注意到数据量.....想了一个方法貌似有问题,TEST没问题,结果被CHA了,第一次被CHA.....

250pt
Solution:
1.注意到只有1024的数据量,所以可以暴力下,用BFS,状态空间是50个城市和1024个值.......
2.后来又仔细想了下,貌似我的想法是没问题的:
因为是异或操作,所以对这个图来说,结果就是选择出与0联通的所有点构成的集合,从这个集合中选择若干个点,使得这几个点的异或值最大就OK,之所以被CHA是代码写ci了。。。。
求n个数的最大异或值:
1.暴力,又多少种组合就需要试多少次,复杂度看起来貌似又2^n,但是如果用set优化下,复杂度会降低,因为异或操作的结果增长速度比较慢,
注意set初始化要放一个0进取,因为0异或任何数都是这个数本身,就相当于只选择这个数的情况。
k个数集合的异或后结果存储在set中,
则在此基础上添加一个数x,结果为set中的每个数与x异或后 的值放到集合中,这样就是在k个数的基础上,k+1个数的异或结果的求法,递推之....

2.高斯消元求n个数异或的最大值.

看到himdd 神http://blog.himdd.com/?p=2728 的想法,使用图的闭包考虑的.
  评论这张
 
阅读(396)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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