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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI 20 stage1  

2014-03-04 09:39:50|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
闲得没事做来做POI20了
估计做不了一两道就得被拉去当苦力了...
第一题就坑了我一下午去想O(m)的算法
实在想不出写个O(m\sqrt(M))的就直接A了
呵呵

题意:求图的最短路,每条边的边权为a。n\le 100000,m\le 100000。如果两个点之间的最短路是2*a的话,则加上一条2*b的边,求新的图的单源最短路
题解:就一傻逼题。注意到为何求出原图的最短路然后贪心地将连续三个点缩成两个点不行呢?那是因为a可能非常大以至于我们只走a的边。那么原问题等价为单源最短路,但是要求长度为偶数的简单路径。这个还是可以BFS啊。枚举u到达的点v,再枚举点v到达的点p,只要p与u不相连,就可以走到p。注意这样的话v到p的边可以删除了,时间复杂度可以保证。问题是如果点p与点u相连呢?这样时间复杂度等于原图中的三元环个数。考虑整个图都是团的时候才是msqrt(m)级别,所以答案应该不会很大吧。然后就A了

题意:傻逼题
题解:傻逼题

Take-out:
题意:一段01序列,你每次能够取出k个1和1个0,但是要求这些元素之间没有元素被取过,保证能取完,求方案。
题解:我太傻逼想了一个小时。。。显然,只要1的个数是0的个数的k倍就一定能取完。方法就是倒过来考虑,每次任意取一段能取的,删除之间的元素得到一个新的序列,由于1的个数仍然是0的倍数,所以可以递归下去。关键是为何保证个数就一定能够找到一段。。这个讨论啊意识流一下就可以了,因为若所有0前面的1的个数加后面的1的个数<k,设有num个0,则1的总个数就小于num*k了,显然不可能。

题意:给定一个棵树,将树中距离小于等于2的点之间连边。问是否存在一条连接a和b的哈密顿路径。。
题解:现在是早上2:32分。。。刚刚过了这题。。。想了好久都没想到什么很好的做法,最终无奈写了分类讨论。。。总之我实在是太傻逼了。。。

题意:给定一个简单多边形,问是否可以选择一个点作为光源,使得墙的明暗情况和给定的一样。。。一堵墙一定要么全部被照亮,要么完全不被照亮,如果点在墙所在直线,则墙不被照亮。
题解:显然我们考虑连续的一段不被照亮的墙,可以等效为一堵连接其两端点的新的不被照亮的墙。于是就可以去掉所有遮挡的情况。。这样一直搞之后做个半平面交再判一下所有暗的墙的交点即可。。或者暗的墙只有一个的话暴力枚举半平面交上的点判判即可。
嘛,很高兴抢到了BZOJ上的第一个AC
代码写得巨丑无比。。。人傻逼没办法
  评论这张
 
阅读(1164)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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