3
16
2015
0

Codeforces Round #204 (Div. 1)

出题人对逆序对爱的深沉。。。

A.给出2*n个实数,让n个数上取整,n个数下取整。求最小的原数组与新数组的元素之和的差的绝对值。n<=2000

题解:首先我们让每个数都下取整,这样有一个和有差值。

            注意到一个不是整数的数上取整的结果比下取整的结果大1。那么我们就可以枚举不是整数的数的使用次数,其他的用整数来填补。取ans的最小值即可。

            也可以分类讨论直接得出答案。

B.有一个n个数的排列。两个人轮流操作,A每次可以交换p[i],p[i+1],满足p[i]>p[i+1].  B会等概率的交换p[i],p[i+1],满足p[i]>p[i+1]或p[i]<p[i+1]。当整个排列成为单调递增的时候游戏结束。求期望操作次数。n<=3000

题解:不妨设f[i][0]表示有i个逆序对并且轮到A操作的期望,f[i][1]表示有i个逆序对并且轮到B操作的期望。则

           f[i][0]=(f[i+1][1]+1)*0.5+(f[i-1][1]+1)*0.5

           f[i][1]=f[i+1][0]

           这样整理后就有f[i][0]=f[i+2][0]+4

           刚开始的逆序对为m,则f[m][0]=0  (?)

           当m为偶数的时候ans=2*m,  m为奇数的时候ans=2*m-1  (???)

C.有一个n*m长度的括号序列,给出a[0..n-1],b[0..n-1]。在i位置放置左括号需要花费a[i%n],右括号花费b[i%n]。求一个合法的花费最小的括号序列的花费。n<=20 m<=1000W

题解:据说可以证明任何时刻左括号不会多于右括号2*n个。。。然后我们用f[i][j]表示从剩余i个左括号填了j个括号之后剩下j个左括号的最小花费。

           求f[][]矩阵的m次方f[0][0]就是答案。当然要用floyed式的乘法。怎么证还是个坑

E.有n个数的数列,可以随意更改一个数的正负。求最小逆序对总数。n<=2000

题解:Orz好题。

            对于一个数a[i],考虑他对答案的贡献,不妨设1到i-1中绝对值比a[i]小的有x个,i+1到n中绝对值比a[i]小的y个。

            那么他对答案的贡献就是min(x,y)。因为a[i]的正负正好对应了逆序对数增加了x还是y,并且对其他的没有影响。Orz!!!

UPD:卧槽怎么还有绝对值相等的情况。。。好像DP一下就可以了?

UPD:绝对值相等的话考虑这个值不断的右移,x增大,y减小,所以只会倾向于让我们选正的。所以绝对值相等的符号选的肯定是先一段负的,然后全是正的。

官方题解:http://codeforces.com/blog/entry/9070

Category: codeforces | Tags: | Read Count: 494

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com