出题人对逆序对爱的深沉。。。
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减小，所以只会倾向于让我们选正的。所以绝对值相等的符号选的肯定是先一段负的，然后全是正的。
评论 (0)
