A 小sun的假期

题目本意是用若干个区间覆盖数轴，最后问没有覆盖到的区间最大长度。

以左端点为第一关键字，右端点为第二关键字区间排序后，从左到右维护一下当前的最大ans就好了。

B 扫雷

直接遍历整个矩形，对于每个非雷的区域统计周围雷的个数。

C 异或和

考虑异或的性质，直接取所有数的异或和就行了。

D 解密

两种解法。

一种是直接把密文表打出来（因为只有52个字符），然后进行解密。

另外一种把式子稍微变换一下，得到

求k1在26下的逆元就行了。

E 图的遍历

考察这个遍历的性质，发现如果图存在奇环，那么跟当前奇环联通的所有点全部可以遍历到。

首先讨论图有多少个联通块，在这些联通块中，若存在一个包含奇环的联通块，那么将当前的联通块与所有的不包含奇环的联通块相连就行了，答案个数为不包含奇环的联通块个数。

若所有的联通块都不包含奇环，那么可以用若干条边在k个（k为奇数）联通块之间构造一条奇环，然后再把其他的联通块跟当前的奇环相连，答案为联通块的个数。

F 小黄鸭

纯数学题，可以建系积分。

图中h即为所求，可设圆的方程为（没在水中的长度）
由积分的知识可以知道：

V可以由浮力定律求出，在这里V=m。

最后会得到：
二分求解即可

G 区间求和

对于每个区间，要求

代表在这个区间中出现的次数。
对于每个区间中出现的,对答案的贡献是
对于这个值，可以用莫队很好的维护。

H 取球游戏

设dp(i,j)为取球i次，最终桌面上有j个球的概率。
根据桌上是否存在同颜色的球，可以很容易的写出转移：
复杂度O(nc)，发现做不了。

不过好在其实并不用算那么多，n达到大约1e5（甚至更小）这个马尔可夫过程就已经收敛了，所以，你只用算到n<=1e5的情况就好。

需要注意当n，m奇偶性不同时无解。

黑书（算法艺术与信息学竞赛）上还记录了一种用生成函数做的题解，有兴趣的各位可以自行查看黑书P259。

I 坐电梯

根据所在的楼层是否是最高的楼层计算答案即可。

J 计数

我的思路有点绕：
考虑这种序列：，需要求解。
可以发现两点

• 解的结果与的具体值无关，只与中间可选择的数的个数有关
• 因为递减序列倒过来就是递增序列， 所以满足条件的递增序列的个数与递减序列相同。

设为长度为i，最后一位是j的递增序列个数。

其实就是

边界

发现就是组合数:

于是对于每个连续的0区间，计算0的个数与两端a,b的差值，然后用组合数计算答案即可。