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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Codeforces 175 Div2  

2013-03-22 20:59:34|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
决定不管TC的题了,做起来蛋疼。。。
这次Div2的题目相比之下还是有一定难度的,虽然也不是很难,但是要我在考场上想出和写出E那道题,不知是否可行啊。难度差不多和上次Div1的题差不多。。。极水无比。不过我D和E都很沙茶地没有一遍写过,可耻啊。

其实我觉得C是一道挺有意思的题,只可惜没有发现水题的性质。。。就是将一个数列修改为排列,最少需要修改多少次,每次只能将一个数加减1。我竟然想到了一个栈匹配模型。。。其实排个序就行了不是吗?

D题,是求这样的两个排列的个数,其一一对应的和对n取模+1之后也构成排列,n<=16。。这种一看就是状压dp的题,其实还是有点意思的,首先自然确定一个排列为1,2,3,4,...,然后dp的状态即为之前用过的数有哪些,暴力转移就行了。
注意到两个排列可行,那么将其中一个排列都加上某个值然后取模也一定满足,所以可以确定第二个排列的第一个数为1。开map状压dp,CF上竟然跑过去了!好神奇。开始发现偶数时是无解的,吓我一跳,还以为我程序写错了囧。

E题,对于一个排列,记good=sigma(abs(p[i]-i)==1),给出n和good,求满足的排列数。n<=1000。
n^2的算法就行了吧。这题显然是道dp,但是由于要用到一点点的容斥原理所以就只有四个人考场上通过了。核心是dp,用dp我们可以对于每个i,选择i个位置,其实good,的方案数,用这个乘以剩下的数的排列数得到的就是至少有k个位置为good的方案数。然后容斥掉。。。惊讶地发现这样重复都被判掉了。
只可惜我组合数都求错了。

  评论这张
 
阅读(140)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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