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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 185  

2013-05-28 22:24:05|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
额。。。似乎把tco的题解补完后就木有时间写这篇的题解了。。。
时间也不早了,明天再来写吧。。话说最近空间访问量真的是越来越来越少。。日记也是越来越少。
不过本来也不指望有多少人来看。所以也只是继续记录我的,b历程而已。

185的题目乃是出自于lydrainbowcat和众多的神犇,除了Div1 C,几乎都是一眼题。
不过都是属于在考场上无法做出来的东东。。。最近发现我的代码能力是硬伤,哭瞎了。

A.
cha掉一段代码。。
题目里有trick。。坑了我好久。

B.裸的斜率优化。。。话说我一直觉得用半平面交来理解斜率优化才是王道啊!不知其它人怎么想的。

C.
题意是这样的,数轴上有些点有宝藏(点数<=10^5)。。但是你只能前进一定的步数,比如为a1,a2,a3,...am(m<=20 ai<=10^18),这些走法是随着询问依次添加的,最开始有个走法k(k<=10000),每次询问是使得某些点的宝藏减少。。或者询问你从一号点能够走到的宝藏中权值最大的是哪个。
关键就是判断每个点什么时候能够走到。。其它的都是简单数据结构问题,可以直接STL搞搞。
注意到k<=10000,这有什么性质呢?
想了我好久的说。从gcd想到任意两个数a,b能够走到的数的个数——于是就发现了最多走k步一定会遍历k的剩余系中能够走到的点——于是就想到了取模了。
好了,关键就是记录下这么个东西,f[i]表示第一个能够走到的mod k==i的点是哪个。。如果能够求出这个,那么哪些点能够到达就非常容易了,用堆存下mod k==i的所有点,一旦发现堆顶元素能够走到就删除,这样时间复杂度是O(nlogn)的。
而求f数组其实也是挺简单的事情。。从modK的任意一个点出发,都可以加行a中的一个数,成为另外的点,然后要求每个点最小的距离——差不多就是个最短路的样子,用dijstra跑跑即可。

D.
每次将一段序列中的一段的每个数变成其立方,或者询问序列和模95542721
APIO时似乎cqx讲过这题啊。
大概就是取模的数比较特殊,根据费马小定理,那么立方几次之后会变成自己。。于是就可以找到周期,线段树暴力搞。

E.
比较裸的最小割模型。
大概就是n个点,每个点都有一个0或1的属性,改变这个属性需要一定的费用。
现在有许多集合,每个集合都有一定的利益和属性,如果该集合中的点都是该属性那么获得利益。
求最大获利。

联想到了srm558,不过相比之下还是逊色很多很多。。
直接对于将集合和点参与构图。
与S相连通则为0
与T相连通则为1
改变的代价就是费用

我们将所有的集合的获利加起来
然后考虑集合对应的点,如果集合中的的有个点与不是自己的属性的话,说明它与另一边联通,就得割掉自己的那条边。。
差不多就这样建图跑跑就行了。。啦啦啦

好可惜unrated。。虽然我木有参加。
  评论这张
 
阅读(378)| 评论(8)
推荐 转载

历史上的今天

评论

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

页脚

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