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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI 20 stage2  

2014-03-06 10:49:42|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
做不动POI还搞P OI啊。
果然应该退役保平安了。

题意:2^60的图,每个点按照二进制标号,二进制之间位数只相差1的点之间连边,删去给定的k个点(k<=1000000),询问某两点之间的连通性。
题解:介绍一个不能AC的算法。。将显然联通的一些集合拿出来,这样的集合至多n*k个,然后枚举修改哪位找到对应的新的集合,用并查集。时间复杂度O(n^2k * \alpha(nk)),可以在线回答询问。不知道比某些算法高明到哪儿去了(雾)。问题是虽然本地是1s以内,但在main上跑了1s+,于是就超时了。无力吐槽
可耻的cheat掉了
主要是POI时限给的太不良心了。而且main上的评测机又慢得要死

Inspector
题意:依次给出m个条件(x_i在第y_i时刻看到房间内有z_i个人)。已知每个人进出房间只有一次,求到第几个条件出现矛盾。总人数为n。
题解:
O( (m+n)logm )就可以很暴力的过了。。不过我不会O(m+n)的做法。这题其实就是noip2013 day2 T1的原题稍微改改
首先很二分答案。问题转化:你可以每次给一个区间中每个元素的值-1,最终使得序列变成0,求最少操作次数。还有若干次不算在代价里的操作:你可以给若干个左端点固定或右端点固定的区间-1。
这个和noip那题的做法是一样的。如果不会做noip那题的话就看看我的代码吧

题意:两个人在一棵n个点的树上玩游戏,一个人在根,每回合往树上一个相邻的点移动。。另一个人则每回合可以选择标记未标记的至多k个点。最开始根已经被标记。如果第一个人走到了某个未标记的点,则算获胜。求使得第一人不能获胜的最小的k。
题解:一道挺有意思的傻逼题。首先二分答案。给定k,如果第一个人如果能获胜,则必定存在一种情况使得他不走重复边。。那么就只需要考虑从根往下走的情况了。我们记录一个f[u],表示从u往下走,之前至少得在该子树中标记了多少点才能使得第一人不能走到未标记的点。f[u]的递推是显然的,这题就完了。

题意:一个n(n<=5000)个点,m(m<=5000)条边的无向图(边权都为1),以及k(k\le 10^6)组询问,是否存在从s到t的长度为d的路径(可以有重边)
题解:考虑到可以在一条边上走来走去,所以只需要关注从s出发到达t的最短的长度为奇数或偶数的路径即可。每次询问可以O(1)回答。


Watering can
题意:交互题,每次区间加个值,以及询问某个区间中大于K的数的个数
题解:傻逼题
  评论这张
 
阅读(976)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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