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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

TC 600.5 T3  

2014-01-28 17:15:04|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
妈呀,我真的觉得我太屌了。。。。。。
我感觉我再努力奋斗一百年就能赶上杜教一半的智商了
===========================================
好久没写题解了,因为一直在做傻逼题。。。
不过终于碰到一道想了好久才想出来的题了——要知道我碰到能做出来的不傻逼的题目少之又少,真是难能可贵。。

好了,题意是这样滴:
给定一个大小为n(n<=10^18)的图,点从0开始标号,以及集合S(|S|<=50)。
点i和点j之间有一条无向边,当且仅当|i-j|属于集合S。
求问这个图的连通块个数。

my solution:
首先一眼可以看出应该用gcd。。但是我们只能对S_i*2<=n的数取gcd。。因为其它数不能取遍其剩余系。
但是我们还是可以取gcd,不然我就不会做了
好了,图被分成了gcd个连通块,设gcd为g,我们只需考虑大小为g的图和S_i*2>n的边了。。
首先,若n-S_i>g,我们还是可以拿S_i出来和g取gcd,因为又可以取遍mod g的剩余系了。。。
接下来就剩下的都是n-S_i<g &&S_i*2>n 的边。。
显然又有两种情况:
如果g是0,也就是之前没有删除任意一条边的话,那么我们画画图
TC 600.5 T3 - hzaskywalker - Yavin(某沙茶的代码库)
红色为最小的S值,那么中间会有一块绿色的单独的一个点一个连通块,接着有关的就是两个黄色的块,我们可以去掉红色的边,将S值减去min(S_i),得到只有一个黄色块的等价的新图,递归处理。
 

如果g不为0。。。这是很悲催的情况,但其实解决方法非常简单:
将n变为n%g+g,然后将所有S_i %= g或者S_i = S_i % g+g(若n-S_i+S_%g<g的话就加上g)。
这样的话,必定可以转化为上面的情况,而且图必定等价——嗯,绝对的。。我觉得我能想到这一步简直就神了。。
这样递归处理就完了。
  评论这张
 
阅读(560)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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