一场在星期天下午的 div1，时间十分的阳间，但是侵占了星期天的颓废时间……
赛况
切了A1、A2、B、C、D，口胡了E，没写出来。D wa了两发，最后排名82。大概能上70+分。
过程
10分钟切 A1、A2 不知道他们有什么区别，然后15分钟切B。感觉这完全就是div2A,B 难度。
然后在C这个期望问题上陷入了困境，最开始一直在往逆序对方面想，然后发现一次操作以后逆序对减少的数量与 i,j 位置有关，然后就无法设出状态……但是考虑到序列中只有0,1，然后往这方面的性质想，终于在37分钟过C。
再看D，一眼最短路，然后思考一下怎么建图。主要是害怕移动非常复杂形成连锁反应，但是仔细分析一下，并不会出现这样的情况。然后就开始写，写了十几分钟，过了样例直接交，结果数组开小+变量名写错，挂了两发，很寄，最后在1:13过了这道题。
然后思考E，最开始以为乘法很多的是时候加法很少，加法很多的时候乘法很少，然后就是一个爆搜。结果又想了一下，乘法多的时候加法还是有O(n)个，所以要在爆搜的复杂度上乘1e6，寄了。然后过了很久，才想起每一个段内肯定先选a大的，然后二分+二分就行了，一看还剩15分钟，写不完了，开摆！
题解
C
看到每次如果 i,j 是逆序对就交换，然后往逆序对方向想，那么你就错了！
要设出好的dp状态，要满足一下条件：
- 可以轻易地反应起始和目标状态。
- 可以轻易转移。
于是想要设出优秀的状态，先从分析目标的性质开始：
它有序，首先可以想到其逆序对数量为0，结果发现从逆序对角度思考无法轻易转移：每次减少的逆序对个数与 i,j 的取值有关。
就只能从其他方向思考：假设一共有 m 个 0，那么最后就要前 m 个全是 0，后 n-m 个全是 1。然后操作的过程就是前 m 个中的 1 逐渐减少到 0。
令 \(f_i\) 为前 m 个中还有 i 个 1 的期望，每次操作选出的 i,j 只有当选出 前面的一个 1 和后面的一个 0，才会使前面的1的个数减少，这样进行一次有效的操作的期望步数为 $ \frac {C_n^2} {i^2} $ ，所以 \(f_i =f_{i+1}+\frac {C_n^2} {i^2}\)。于是最后的答案就为：
$ \sum _{i=1}^k \frac {C_n^2} {i^2}$，其中 k 为起始前m个中1的个数。
D
首先，可以发现每个床至多只会移动一步：证明如果移动两步及以上，那么一定就有一个大小至少为2的空位，可以直接把床放在那里。于是就知道了要空出每一个位置所需要的转移。
令 dis_i,j 为空出 (i,j) 的最小代价，要空出 i,j 就需要将覆盖它的床移动一步，覆盖另一个点 (i',j')，然后 (i,j) 只会有三个 (i',j') 然后就可以直接跑最短路了。
E
看一下题目中初始结果不超过2e9的限制，很明显ai>1的乘法操作就很少了，然后最后答案一定不超过4e18。
考虑修改的策略，肯定是将一些乘法操作移到最后，一些加法操作移到最前。
乘法操作很少，就可以直接爆搜，然后再算出每个加法移到前面的价值，选出最大的若干个。但是这样复杂度极高，跑不过！
于是考虑剪枝，对于 a_i 相同的乘法操作，肯定选前面的进行操作。然后对于所有加法操作，按其在第几个乘法之后分段，每一段肯定会选 a_i 大的。第一个剪枝直接让爆搜的状态数变得很少，貌似不会超过2^15。第二个剪枝可以用二分最小结果+每段二分有多少个来快速算出加法的答案。然后复杂度就很对！
然后刚刚写完dfs就结束了……
标签：二分,CF1753,然后,加法,操作,逆序,乘法 From： https://www.cnblogs.com/william555/p/16820060.html