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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Croc Champ 2013 - Finals && Codeforces 184 Div2  

2013-05-22 20:33:52|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近心情很不好,由于滚回去搞文化课了,加上各种各样的原因。唉,现在心里好烦的说。
这两套题其实不久前就做完了。。。不想多说什么。
184保持了CF div2的一贯风格。
Croc Champ 2013的题则是都是些比较注重思维的,trick好多好多,Wa了好多次。。呜呼

=========================Croc 2013 Final===================
CF上似乎没放题解
那就写写吧,其中E题挺神的。。
A.
题意:n个人,在一个环上,其实位置不同,其随机往左跑或往右跑,跑步速度相同,两个人相遇当期在同一时刻在同一位置。。问时间t之内相遇总数的期望。
题解:考虑两两相撞的期望然后累加。确定其中一个人,其它人的相撞次数只会相差1,而且与其位置有关,这个可以二分。非常简单的。

B.
题意:单词中加上空格连成一行,我们要选择其中连续的一些单词,使得其单词数最多,而且能够划分成不超过L段,每段的长度不超过c,忽略行末空格。
题解:显然可以处理出第i个电词结尾的行至多能够包含多少个单词,可以单调性扫扫即可。这样每行都有一个确定的前趋。这是树的形式。于是你要从树上一个点出发,求出其前L个祖先的权值。。这个显然倍增就行了。

C.
题意:给出n个容器,每个容器有个容量,然后给出m个数,这m个数都是2的整数幂。。一个容器能够装下任意多的物品,只要这些物品的和不超过容量。求最多能够装下多少个数。
题解:好厉害的题,tourist怒hack了16人,估计就是因为这题吧。。都赶上唐翔昊的18x了。
题解显然就是贪心了。。由于物品是2的整数幂,我们将容量也分为2的整数幂。我们从小到大放物品即可保证最优,因为放小的和放大的收益都是1,而放不了小的肯定也放不了大的。
但是这个贪心实现起来很蛋疼。。。犯了个种傻逼错误的法法塔就各种滚出了。

D.
题意:一个等边三角形,每条边上等距分布着n个点(n<=3000),其中两边的连续m个点是无效的,求由有效的点组成的三角形的个数,使得其三个顶点分属等边三角形的三条边,而且是钝角三角形。
题解:显然可以优化下常数的~钝角在哪条边,其实是无所谓的,最后答案乘个3,然后这个点是在该边的左边还是右边,也是无所谓的,答案乘个2。
那么枚举钝角所对应的顶点。然后枚举另一条边的一个点,显然其对应的钝角是个区间。。。而且这个区间具有单调性的。。钝角用点积来判,公式很简单。。不知为何通过人数那么少,明明不能更水了。

E.
题意:
n(n<=1000)个区间,两两区间之间连边只要他有公共点。求一个排列,使得相交区间对应的点在排列中的距离的最大值最小。
题解:
最大值最小问题很容易想到二分。
所以二分答案D判断是否能够安排区间的顺序,使得相交的区间的距离小于等于D。
依次安排第i个位置是哪个区间,我们记个limit表示当前每个区间的位置的最大值,这个东西是由已经安排的且与其相交的区间的位置和D共同约束的。
最开始显然是右端点最小的排在最前面,因为其它的右端点都比它大,安排其它的,只会增加其它的点的约束。。得不偿失,而且自己也是迟早要放的。放到后面也不会减少其它点的约束,因为它约束了的,放在它前面的也约束了。
那么我们就每次贪心将右端点最小的放在前面怎么样呢?
这个肯定是错的。。由于别的区间都有个limit的限制,可能右端点最小的区间放不放无所谓,但是有个区间必须放在该位置了。。
对于这样的窘境应该从另一方面看问题。。我们要求的其实是区间与位置的对应关系,由于每个区间有个limit,所以其能放的位置是有限的,那么判断是否能放这个区间其实是要判断是否存在一个匹配。这个可以用Hall定理。。也就是如果有i个数要放在剩下的前i个位置,那么就只能从这i个数中选择右端点最小的放了。
于是本题就可以AC了。

=======================Codeforces 184 Div2==================
其实这套题。。。无力吐槽了。。
不过ydc大神怒切四题,orz了。
当时还想水水这套题的。。。结果喜闻乐见记错了时间。
题目还是挺有意思的说。

A.
题意:两个数匹配当且仅当对于任意一位,至少有个数该数位为0。给出一些数,求个最大的集合,使得这些数两两匹配。这些数都是三位数以内
题解:显然。。。其实只和该数位是否为0或1有关。那么实际上不同的数大概只有5种,随便怎么暴力就行了。

B,C都是大水无误。
D稍稍好点:
题意:n个点good图,要求满足每个点只会往编号比它大的点连边。考虑任意一个点,对于其后的前k个点,这些点到这个点的距离为编号差,而对于k个点后的其它点,其最短距离要么为编号差,要么为编号差-k。
给定图的一部分,要求有多少个不同的图是good的。
题解:题意大概如此吧。稍稍动动脑子,就是在n个点的链上在一些编号差为k的点之间连边 ,而且这样的边必须交叉。
没了。

E题:
给定一个串,两个人轮流操作,每次可以选择一个回文串最中间的字符,从这儿将这个串断开,不能操作者获得胜利。
题解:
看错题了,搞了一晚上。
然后才发现是水题。。。显然只和哪些点是回文串的中点有关。。这些点连起来相当于一个石堆。
nim游戏,暴力sg函数。
没了。
  评论这张
 
阅读(466)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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