A、期望逆序对

medium
假设最终序列是 ，它作为最优解的一个必要条件是交换两个相邻的位置 不能让答案变得更优。交换两个相邻的数的时候，只有它们之间的相对顺序发生了改变，所有这个条件也可以被写成所有 是逆序对的概率不超过 。
对于两个随机变量，考虑（x，y）是逆序对的概率不超过。的条件：
1.，这时 的区间整体在 的左侧，因此形成逆序对的概率不超过号。
2.，即 的区间包含 的区间时，如果 的区间在 的区间的正中央时，根据对称性，形成逆序对的概率是恰好。因此当 在 中间偏右的时候，逆序对的概率就小于了；中间偏左的时候，逆序对的概率大于。
综上，条件可以被总结为。因此最开始把所有区间按照中点从小到大排序，我们就可以得到最优的序列。问题变成了给定序列怎么求逆序对个数的期望。根据期望的可加性，我们可以枚举每一对位置，答案就是它们形成逆序对的概率加起来。对于两个随机变量，左边比右边大的概率为：
右侧是一个分段的线性函数，讨论一下即可。总的时间复杂度为。

B、密码学

easy
题面中给出了已知原文和秘钥，加密得到密文的方法。其实已知密文和秘钥，就可以轻松的解密出原文：只要用密文对应的数字减去秘钥对应的数字就可以了。
因此，我们可以从后往前“撤销”所有加密操作带来的影响。假设最后一次加密操作是用 去加密 ，
，那么在结果中，。是没有发生变化的，即秘钥已知；，存储的是结果，即密文已知。从而用上面的方法可以直接从两者之中推出 ，原来的值。
所以从后往前考虑每一次加密操作，依次进行撤销，最后得到的就是最开始的 个字符串。

C、染色图

medium-easy
对于一张图，如果染色方案已知：染第 种颜色的点的个数是 ，为了最大化图的边数，我们会在每一对不同颜色点之间连上一条边，因此此时的最大边数为：
为了让上面这个十字尽可能大，最优方案是把 均匀地分配给所有的 ，即有 个颜色有 个点，有 个颜色有个点，此时边数为：
使用两个恒等式化简：。这样可以得到是一个只和。后两者的取值只有 种，枚举它们然后每一段直接求和即可。
时间复杂度为。

D、生成树

medium-hard
这题要用到带权版本的基尔霍夫矩阵：对于一张带边权图G，定义生成树的权值为所有使用的边权的乘积，求所有生成树的权值和。方法和不带权的版本类似，定义矩阵A：
1.，等于 所有相邻边的权值和。
2.等于 边 的权值。令 为 删去第 行第 列后得到的矩阵，那么答案就是 。
在这题中，我们定义所有只在 的边的边权为 ，同时在 中的边的边权为 ，那么B的每一个元素都是一个多项式，记作 ， 是一个 次多项式，其中 表示使用了 条公共边的生成树个数，所以答案就是
根据矩阵求导法则，可以得到：
用高斯消元 的行列式和逆矩阵即可，时间复杂度为。

E、树与路径

令 为第 个点为根时的答案，那么 可以在 时间内求出来。现在对于每一个点 ，设它的父亲为 ，考虑 ：
1.对于任何一条不同时经过 和 ，的路径，它对 与 ；的贡献相同，即 。
2.对于一条同时经过 和 的路径，设其长度为， 往下的长度是 ，那么对 的贡献为，对 ；的贡献为 ，即对 ；的贡献是 。所以，我们需要对每一个，求出所有同时经过 和 ：的所有路径的 的和(记作)。对于路径(u,v)，设它们的最近公共祖先为 ，我们只考虑这一半边路径(另半边对称)，这条路径对 产生了的贡献，对危产生了产生了 的贡献，以此类推可得，对 上的每一个点 产生了的贡献，其中 表示 的深度。
我们可以用树上前缀和来推出所有 ：如果要对加上一个等差数列，就在 上加上，在 中减去，然后DFS一遍，对每一个点 算出子树内的所有标记和 ，那么 。
求出 后，DFS一遍就可以根据A1的值推出所有的值。时间复杂度 。

F、乘法

medium-easy
二分答案 ，算小于等于 的乘积有多少个。这只要对 排序后，lower_bound 或者用指针单调地扫一遍就行了。难点在于数可以是负数或者 ，因此要对这些情况分类讨论。
时间复杂度。

G、圆凸包

medium
在合并两个凸包的时候，我们会选择先求出两个凸包的外切线：外切线会取代原来凸包的一部分边界，出现在合并后的凸包边界上。因为圆也是凸包，所以这个过程对圆同样适用。
因此，答案的边界一定是若干段圆弧+外切线。考虑什么样的点会成为答案的顶点：
1.首先这个点必须要是某两个圆之间的外切点。
2.这个点不被任何圆覆盖。
因此我们可以先 求出所有满足这个条件的顶点，然后对这些顶点求凸包。计算答案的时候，如果相邻两个凸包点在同一个圆上，说明这一段应该是圆弧，就把对应长度的圆弧计入答案，否则说明这一段是外切线，直接把这一段的长度计入答案。
时间复杂度 。

H、最大公约数

easy
考虑 的取值：
1. 必须是 的倍数，否则无法区分 和。
2.对于的每一个质数 ，必须是 的倍数，否则无法区分 和 。
因此设为中的所有质数，那么答案就是。用高精度计算后就能得到答案。

I、K小数查询

medium-hard
考虑区间线段树套权值线段树求区间 小值的算法：对建线段树，每一个线段树节点，用一棵动态开点的权值线段树记录 中每种权值出现了多少次。
如果能够维护这样的数据结构，询问就可以转化为在 棵权值线段树上二分，能在的时间里得到答案。
修改时，首先和普通的区间线段树一样，定位到某些节点：这次修改相当于把内层线段树中所有大于等于 的数并到 的位置，这可以被转化成 次线段树单点修改操作，其中 为被并入的节点个数。把这 次修改应用到内层线段树以及所有祖先节点的内层线段树上。这一步的时间复杂度为。
接着，在 上打上对 取 的标记。在标记下传的时候，同样当前节点的内层线段树中，更大的节点的值并到 处，但是因为次数祖先节点的内层线段树的信息都是正确的，所以不需要把修改应用到祖先节点的内层线段树上。
时间复杂度和所有操作的 的和有关，不难发现，每一次操作结束后，内层线段树的叶子节点个数都减少了 ，而最开始一共有个叶子节点，所以 的总和不会超过。因此总的时间复杂度为。

J、德州扑克

medium-hard
直接枚举公共的 张牌的方案数是，再加上判断的复杂度乘上长度，是容易超时的。在此基础上各凭本事的剪枝就行了。
标算的做法是不枚举所有花色组合：出现同花的时候，必然有一种花色出现了超过 次，此时只有这一种花色的花色信息是有用的（其他花色不可能出现同花了）。因此只需要枚举大小组合、出现超过 次的花色以及对应的牌即可，枚举量就大大降低了。