五校联考day2——2018.8.27

比赛总结

预计 100 + 70 + 55
实际 100 + 70 + 55

比赛总结

开始，T1想了不少时间，然后T2，没想出，半个小时过去了，T3看完题目感觉是求每个数的概率*这个数的权值。然后开始写T1了。
T1：想复杂了，感觉像是那场比赛的题，而那场比赛好像是用dp+二分做的。于是就往这方面想。贪心：按右端点排序，然后每个线段在查询左端点之前的最靠右的线段，如果有，然后这条线段可以不增加加答案（就是两个人用一个杯子喝水），并把那个线段的右端点删掉，然后加入这个右端点；否则，答案加一。然后查找的时候二分，插入删除平衡树和主席树都行，最后用了可重集合。证明想了很长时间。
思维僵化。。。应该扩展思路，多想想。

T2：推了很长时间，写了n^2的容斥。
考虑对行容斥：
所有的情况就是$2^{nm}$，然后减去一行全空着的，加上两行全空着的，减去三行全空着的...
然后规定了k行空着之后，有$C_n^k$中选法，然后剩下的所有的方案数就是$2^{(n-k)m}$，这些里面包含列全空着的情况，然后向行一样，减去一列空着的，加上两列空着的...求出来就是n-k行保证每一列都有的方案数。相乘，求和。

T3：
只剩一个小时了，又感觉是T3，感觉可能会很难，就没去想正解，写了暴力，加一个部分分。
考完听说都写了正解。
然后看一下我的暴力，发现我的暴力就是将一段区间乘以一个数，将一段区间加一个数，求一段区间的和。发现这不就是洛谷线段树2吗！！！后悔没写。

题解

T1：其实将每段区间所对应的数在数轴上+1，求出最大的值就好了。发现自己zz了，其中需要离散化一下。

T2：其实对行容斥完后，剩下的就是求n-k行，保证每一列都有的方案数。这里不需要容斥的，直接算就行。
对于每一列：都有n-k个格子，每个格子可以选涂色或者不涂色，方案数就是$2 ^ {n - k}$
其中可能会有全都不选的方案数，有1种，减去就是$2 ^ {n - k} - 1$。然后一共m列，所以方案数就是$(2 ^ {n - k} - 1) ^ m$
当时时间不算很多了，想先打完t3，感觉T2往后可能也不简单，于是也没往下想。

T3：交换操作[l1,r1]与[l2,r2]，考虑每个数出现的概率。
对于i∈[l1,r1],
1、有$1 - \frac{1}{r1 - l1 + 1}$的概率保持不变，就是原数乘以这个概率。
2、它有$\frac{1}{r1-l1+1}$的概率被选中，第二个区间的数j出现在i这个位置的概率是$\frac{1}{r1-l1+1} \times \frac{1}{r2-l2+1} * a_j$，每个数的概率都一样所以区间2总的和就是$\frac{1}{r1-l1+1} \times\frac{1}{r2-l2+1} * \sum\limits_{i=l2}^{r2} a_i$
然后就成了线段树的经典操作将一段区间乘以一个数，将一段区间加一个数，求一段区间的和