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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POI 20 stage3  

2014-03-07 22:41:20|  分类: POI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
希望不坑希望不坑
问题是看到0AC感到压力山大啊

Tower Defense game
题意:给定一个图,已知其最小支配集为k。求一个大小小于等于k的近似最小支配集——一个集合为近似最小支配集当且仅当图中每个点都存在集合中的一个点与其距离小于等于2。
题解:感觉构思非常巧妙的一道题,虽然非常简单。。其实做法就是从1到n,碰到一个没被支配的点就加入集合,并用它来支配其它点。为何这样是对的呢?因为最小支配集为k,没有被近似支配的点一定会被集合中的某个点支配,选择它之后就相当于选择了最小支配集中的点。。

哦艹。。。POI的题解已经放出来了。。
累觉不爱
心灰意冷
再也不相信爱情了
动力持续丧失中

嘛,有始有终。
题意给定一个{-1,0,1}组成的序列,你可以进行x_i+=x_{i-1}这样的操作,求最少操作次数使其变成不降序列。
题解满分率几乎99%的题。。随便写了个不知道是什么的dp就过了。主要是考虑到最终形成的序列还是只包含了-1,0,1就行了

题意:给定一个序列,求有多少个子序列使得c_i这个数在这个序列中出现了l_i次,且不存在其它的数。
题解:如果可以存在其它的数的话还有点搞头。这个嘛

题意:
交互题,已知一个排列,每次你可以询问1.某两个位置的数的差是否被某个数整除,2.第i个数是否大于第j个数。请用最少的2操作找出排列中1所在的的位置。操作1的次数是任意的,但是不能超时。n<=5*10^5
题解:
这题虽然通过人数很多但是很有意思。我开始没注意到操作2的次数至多1次逗了好久:当n>1时,操作1是不能区分1和n的,而只要找出两个数整除n-1就可以找到1和n了。
接下来就是经典算法上线的时候了,给定一个排列,请找出其中最大和最小的元素:这个问题显然可以分治了,按照mod2同余将排列拆成两部分,分别在内部找到最大最小,通过检验这四个数之间的差是否被(元素个数-1)整除即可

题意:给定一颗树,请给树边改成有向边,求连通的点对个数的最大最小值。点对连通,要么a能到达b,要么b能到达a。(n<=250000)
题解:
一道不是那么傻逼的题目。当然如果通过人数稍微多一两个的话这题就是傻逼题无误了。
首先最小值就是n-1,考虑奇数层的边向上偶数层的百年向下即可破。。
最大值是个很棘手的情况。。我想了一天的dp优化,尝试了各种dp方程无果。。扫了眼题解:
O(n\sqrt(n))。。。。卧槽啊。。这么大的数据范围也敢根号啊。。
然后发现似乎用了结论。。。去看了下去年波兰人的成绩,几乎都A了这题。。。那为何main上的通过人数这么少呢。。利用这两条性质可以证明:这题是道傻逼题。。
所以说无论如何此题都用了一个结论:答案一定是以一个点作为源点,其它点要么通向这个点,要么可以从这个点到达。。。当时利用通过人数这么少的性质直接否定了。。从这方面讲我真是卡哇伊啊!
具体证明的话:考虑如果这样的点存在两个。。其间一定存在一条路径。。设第一个点进入的是a,出去的是b,第二个进入的是c,出去的是d,设sum=a+b+c+d,即证:a*b+b*c+c*d<=max((sum-a)*a,(sum-b)*b,(sum-c)*c,(sum-d)*d),然后这是显然的。
所以说做法就是枚举中点。
接下来就是要划分出去的和进来的使得其乘积最大,也就是选出一些数最靠近(n-1)/2,子集和问题,除了dp就没办法了。
但是由于总个数有限,我们可以将数分为大于sqrt(n)和小于sqrt(n)的数处理,时间nsqrt(n)。
注意到只有在重心才会dp,否则的话直接就可以算了,所以总时间nsqrt(n)
跑得贼快的。。

题意:平面上有些线段,你最多从原点射出k条射线,穿过最多的线段,且使得每条线段最多被穿过1次。k<=100,n<=500000
题解:通过人数很少的原因完全是因为题目没有被翻译成英文吧。。

有生之年终于能够在main上屠一道0AC的题了!
题意:用L和P描述一个边与坐标轴平行的简单多边形,其中L表示往左拐,P表示往右拐。给定L,P的描述,请输出这个多边形。
题解:虽然这题不是很容易AC,虽然这题做的人不多,但还是改变不了这是傻逼题的本质。显然如果L的个数不是P的个数+4的话就无解了,因为我们可以将连续的LP或PL消去,直到最终留下矩形(当然可以用多边形的内角和证明了),也就是四个L。
我们用链表处理每个L和哪个P消去,然后取出四个L。接下来就是递归构造了:
考虑一个位置l,和其匹配的位置r,由于区间(l+1,r-1)所对应的多边形的片段不会改变边的方向,所以我们可以取出这个片段,然后在首尾添上相应的边。
这样,只要我们在首位添上的边与(l+1,r-1)的片段不会相交的话,则递归构造就成立了。那么关键是l所对应的边和r所对应的边得有多长?
显然只要l的边的长度大于(l+1,r-1)的最小外接矩形的宽度即可。
所以我们事先做一次类似于dp,处理出原串中任意一段的最小外接矩形,再用一次递归构造出解。

补完!
总的而言,除了一道题扫了眼题解外都是独立完成的,成就感满满啊。
嘛,作为集训队作业的一环,我应该会补一份比较详细的题解。。虽然工作量会比较大,不过也相当于继承了qzc的传统了。
  评论这张
 
阅读(1344)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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