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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 182 Div1 && 183 Div1  

2013-05-16 17:03:19|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
由于APIO考挂的原因加上回教室准备水考,都没什么时间写日记了。。以后时间恐怕会更少。。郁闷中。

================Codeforces 183 Div1====================
刚刚把183解决完,当时的考试似乎非常的坑爹啊,出现了各种bug导致似乎出题人心灰意冷???然后一直没有题解。。。巨蛋疼。
好吧,不得不承认这些题目真的很坑爹很坑爹。。。至少把我坑得非常非常惨。
下面开始久违的题解时间:
A.
题意:给定n,要求两个0~n-1的排列,使得这两个排列对应项相加模n后的依旧是个排列。
题解:首先n是偶数的时候肯定是无解的。。这个记得以前有过一道状压dp里面有这个结论。证明嘛。。我不会T_T,
然后n是奇数的情况就好办了。两个排列都是0~n-1依次排列即可。只要(2*i%n)一定是个排列那么就行。很容易证明n是奇数的时候这些数是不会重复的,可以反证假设2*i-n==2*j,那么左边是奇数右边为偶数,矛盾。。

B.
题意:n*m的矩形中有一点,要求一个最大的矩形,使得其中心离那个点最近,包含了那个点,且长宽比为a:b。
题解:注意到我们可以求出一个最大的,能够放在n*m内的矩形使得其长宽比最大。假设中心在那个点,根据超出部分抖一抖即可。

C.
题意:给定n(n<=5000)个数,这些数<=10^6,你最多能够删除k个数(k<=4),求最大的m使得不存在两个数ai%m==aj%m。
题解:这题的做法很囧。ai==aj mod m,那么m|(ai-aj),假设确定m,相等的只可能是那些差是m的整数倍的数对。于是我们可以预处理出每两个数的差,那么依次枚举m,就可以O(10^6log(10^6)+?)的时间复杂度处理出对于每个m,所有的相等数对,显然要删除的只能是这些数对的数。。。?代表的是对于每个m相等数对个数的和。。由于k<=4,那么当相等数对>10的时候肯定不可能了(5个点的团),所以可以直接判掉。那么时间复杂度就是10^6*(log10^6+10)+n*n。如果用vector的话常数过不了,改成链表才过的。。

D.

E.
题意:n个人(n<=80),每个人的分数都是[l,r]中随机的一个权值,分别对每个人求出其排在每一名的概率。
题解:首先强烈膜拜唐翔昊大神orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
他在考前一个月就精确命中此题,打算出在校内的模拟赛上,真的是太神了。
关于这题当时有个简单的想法,昨天仔细看了一下,其实也不是太难的说。(当时txh在各处求时间复杂度<=n^2的算法,简直丧心病狂)
主要是本题的n比较小,所以用很暴力的算法就能AC了。
考虑一个人,那么用其它人的分数区间来划分这个人的区间,假设该人的分数落在某小区间内,设为(L,R),又设该人的分数是X(L<=X<=R),为未知数。然后再考虑其它人,比如说区间为(l,r),是否排在该人前面,发现此时只有三种情况,1.r<L ,2.R<l 3. l<=L <=R <=r。前两种情况可以算出了,而对于第三种,其排在我前面的概率为(X-l)/(r-l),这是一个一次多项式!而最终概率是这些多项式的乘积,其结果一定也是多项式。
于是我们可以dp了(当然从母函数的角度解释也是可以的)
考虑前i个人有j个人的分数比我小的概率的多项式为f,那么通过枚举第i+1个人是否在我前面,并乘上对应的表达式即可完成转移。
那么得到最终的结果,f[i],表示有i个人排在我的前面的概率的多项式。这有什么用呢?
考虑任意一个多项式G=f[i]。
答案为sigma(G(x)*dx/(R-L)),看到这个形式就应该都会了吧,简单的定积分就可以算出来了。
那么这题就基本解决了。时间复杂度是O(n^5),常数写得好即可。
不过有个方法可以将其优化到O(n^4logn),那就是类似于求拉格朗日插值的方法,利用分治。(这儿多嘴一下,考虑极小的区间只有O(n)个,而对于包含了这个区间的人的多项式的差别只有自己的这个多项式,分治可以很好的解决这个问题)
注意常数,注意精度!

================Codeforces 182 Div1====================
A 略
B 题目太纠结了。。懒得写
C 开始一直没看懂题,所以也略了。
D 无脑线段树。
E 神题一道:
一个数列合法,当且仅当这个数列相邻两项差的绝对值为1。
给定一个不降数列,我们可以任意安排这个数列中的元素。
求这样的数列的个数,使得每个数<=m,数列的长度<=n,其可以安排成的不同的合法的数列的个数为k。
n,m,k<=100。
题解:
主要是有个难点,这样的数列是怎么形成的?
一般的思路都是一个一个往后面添加数。但是这题不行,决定不降数列的,是每个大小的数出现的次数,我们只能通过枚举这个来搞。
那么究竟是如何生成的呢?
其实有个很简单而且很神奇的方法,加上现在想在之前的数列上加上值为m的数,那么只能将值为m-1的数拆成两个然后插入其中!
利用这个就可以很简单的dp了。
  评论这张
 
阅读(556)| 评论(11)
推荐 转载

历史上的今天

评论

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

页脚

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