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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 176 Div 1  

2013-03-30 17:24:33|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
呜呜呜,我得有多弱了啊。。。
被虐死了。。。估计是rp掉光了,今晚tco补回来。。。。真的好久没想题人都晕了。。不过我现在真的快晕了。
最近各种被虐啊,CH上的题也不会,腾讯马拉松也只是单纯地被虐(我参都不敢参加啊)
回家之后再补题解了。

A题,是一道关于置换的题目,具体细节就不说了,关键是要发现规律。
B题我另外开了一个帖子的。

C题
题意:括号是匹配的,但是括号是用数来表示,只有绝对值相同的数才能匹配,而且正的为左括号,负的为右括号。比如12-2-1就是一组合法的括号匹配方案。现在知道了每个数的绝对值,并且知道了有些数一定是负的,求出任意一组合法的括号匹配方案。
题解:首先yy了一个结论:如果每种颜色的前缀和都>0的话,那么一定有解。。。不知道对不对,但是由这个可以推导出可以AC的程序。有了这个结论后我们要尽可能地保证前缀和>0,由于本来前缀和一定>0的,所以如果我们倒着从每个位置由里到外贪心寻找匹配的括号的话前缀和不会受到影响,所以就这样搞就行了,具体证明不会。

D题
题意:平面坐标系上,在一定时刻就会有两人分别从(-1,0)(1,0)出发沿y轴正方向以1m/s的速度前进。在某一时刻t就会出现一些墙(l,r),表示是连接(0,l)和(0,r)的一条线段。这些线段会挡住两个人之间的视线,回答询问,在qi时刻出发的两人会有多少时间被挡住视线,挡住就是两人之间的连线与某个墙相交。
题解:
其实我从这道题上感受到了一个事实,一道再SB的题目,算法再简单都可以让人想上很久很久。思路其实超级简单的说,但是我开始将问题转化了一下解决某个问题结果忘了转化回来费了好多时间纠结,而且忘了离线这个好方法。唉!
其实有个很显然的思路,我们将坐标离散化,对于没一段,我们只需算出覆盖这个区间的第一条线段是哪条。。。于是我们得到了很多不想交的线段,以及其出现时间,就可以算出一个时间段(s,t),表示出发时间为x(x>s)的话,那么就可能被挡住。将这些时间段画到坐标轴上,对于时间x,答案就是在其左边的线段的长度和。然后将时间也离散化掉,统计一下答案就行了。。
尼玛我傻逼想了一下午才写出来啊。

E题
题意:给定一个数的集合a,求另一个数的集合b,要求:1.a中任意一个元素都可以表示为b的一个可重子集和。2.b的任意一个小于m的可重子集和都是a的元素。求b,使得元素个数最少。
题解:其实本题不算太难,至少DE的难度都比不上B。。。标签里提示了是FFT那么这道题就水掉了。不过考场上想出来真心对于我而言有点难度。。。而且我写FFT至少还得要几十分钟。。不过好歹写对了
考虑一个贪心地过程,j将a中元素排序,如果前i个a的元素都已经被b表示出来了,第i+1个集合一定也是b的元素!否则a_{i+1}无法被表示。
很容易想到问题就是如果a中哪些元素不能被a中比它小的元素表示,那么一定属于集合b,集合b中也只会存在这些元素!证明:归纳,先对于比它小的元素成立。如果它能被a中比它小的元素表示,将那些元素拆成b,那么这个元素不会属于集合b,因为只会徒然增加b的集合个数,如果不能,为了能够表示出来,只能新增加一个为a_{i}的元素了。
为了解决这个问题,自己乘以自己的多项式乘法,统计出自己被比自己小的元素加起来表示的方案数即可。
  评论这张
 
阅读(225)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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