Educational Codeforces Round 68
E
题意：有 n 个线段，每个都是平行 x 或者 y 轴，只有互相垂直的两线段才会相交。问形成了多少个矩形。 (n le 5000, -5000 le x_i,y_i le 5000)
key：树状数组
考虑枚举矩形上边和下边，如果统计出与这两条边相交的竖线个数，那么就能知道贡献。先枚举下边，把所有与它相交的竖线插入树状数组。如果把竖线按照上端点的纵坐标排序，那么按照从下往上枚举上边时就可以删掉某些竖边。总复杂度 (O(n^2 log n))
F
题意：有 n 个题，第 i 个题花费时间是 (a_i) 或 (a_i+1)，概率都是 0.5，你只能顺着做。问 T 时间做题的期望个数。 (a_i le 10^9, T le 10^{14}, n le 2*10^5)
key：概率
key：姿势
总方案数是 (2^n)， 考虑第 i 个题被做的方案数。令 (sum_i=sum_{jle i}a_i) ，那么剩余可随意支配的时间是 (T-sum_i)，这些时间会被分配到前 i 个题上，每个至多分配 1，或者留给后面的题。后面的题不用管，就是 (2^{n-i}) 种方案。所以这个题的贡献是
[frac{2^{n-i}*sum_{j=0}^{T-sum_i} {i choose j}}{2^n}
]
分子是一个组合数第 i 行的前缀和，这个可以直接递推（(sum_{ile m} {n+1 choose i} = 2sum_{ile m} {n choose i} - {n choose m})）。由于随着 i 增大， (T-sum_i) 变小，所以可以直接做。