依旧拖题解。 非常好题目！ 不妨考虑全部集齐的时候怎么做，即 的情况。 考虑 min-max 反演，即 证明可以考虑排名为 的数。大于这个数的数一共有 个，这个数会在 个子集中做贡献。对于 的情况，其中一半为正，另一半为负，因此贡献是 。对于 的情况，贡献就是 。 需要注意这个式子在期望意义下也是成立的，利用线性性质展开即可。 另 表示第一次每个元素的时间，放在这个题目，考虑其组

原来大家都不知道吗。 首先你必须要是 Coach。 接着找个能够挂载 ftp 的东西。挂载 ftp://taskbook.codeforces.com。用户名是你的 cf 用户名，密码是你的 cf 密码。 根目录下是用 GYM 编号命名的文件夹。找到要的那场的 GYM 点进去，依次点开 release，problems。这里会有若干个文件夹，找到你题目对应的那个点进去，你就可以找到题目的 chec

卡常题。而且似乎数据比较水。 简而言之，我们需要最大化 拆成这个式子： 先固定 ，不妨假设 是按照 从大到小排序。确定最优化的 的顺序。我们要最小化 ，最大化 ，根据排序不等式， 的大小应该和 顺序， 应该和 逆序。 显然 应该大于 ，因而 应当大于等于 。否则交换二者代价由负变正，显然不劣。如果 也小于 ，那么此时交换两者也不劣，原因是交换后 不变， 变大。 此时 和

非常好题目。 注意到，你目前的最优策略只和当前的红点集合有关。而操作失败并不会改变红点集合。因此你的最优操作肯定是对着一个点一直操作直到成功为止。相当于我们要给所有点排出来一个顺序。 记作 为初始红点邻居个数和排在 前面的邻居个数之和。换句话说， 是已经将 前面所有的节点染色完毕时， 周围红色节点的个数。 这个点对期望做出的贡献就是 （一次操作成功概率是 ，操作失败不改变红点集合，到成功为止

有临项交换和排序可以考虑逆序对。每次交换相邻逆序可以恰好减少一个逆序对，因而恰好逆序对个数次就可以排序完毕。 操作二的实质是将逆序对个数从 变成 ，因为每个逆序对反转后变成正序了，反之亦然。 因而每个操作仅使用前两个操作的最小代价是好求的。下文称作暴力还原的代价。 接下来引入操作 。首先注意到目前最优操作之和当前排列有关，和历史状态无关。更具体的说，是和当前逆序对有关。 考虑最后的策略是什么：

套路题。感觉没见过类似的套路最好都方法就是打张表。 一般这种博弈论通常不先考虑 SG 函数（而且这题似乎不是公平组合游戏）。通常考虑分析性质或者手完小样例。 不妨考虑 的必胜策略。注意到 Alice 无论下什么位置 Bob 都可以对称的下。 需要注意奇数的情况。Alice 可以下在中间。此时 Bob 只要不开始下中间旁边的两个点即可，每次 Alice 对着下的时候中间旁边的两个点至少有一个点可以

被黑题吓死了。 如何计算答案 首先需要注意酒桶和熊都是区分的，不要读错题目意思了。 不妨先来考虑一些简单的情况。 考虑 的情况。对于这种情况，实际上我们只能接受醉倒 头熊，因为要保证至少一头熊清醒。由于醉倒的熊的个数和用掉的床位是相等的，直接将 对 取 即可。 对于只有一个床位的情况：挨个试过去即可。 天最多可以区分 桶。 对于只有一天，但是允许醉倒很多熊：直接二进制分组。 然而其

怎么拖到现在才开始写题解啊。 我不会啊。这咋做啊。 首先就是整除并不好做。我们因此考虑使用 转化一下： 考虑左侧的 这个东西很像二项式定理，因此我们朝着这个方向去凑。考虑把 写成 的形式。 组合意义合并一下两个组合数： 提出一个 。 做变量代换 ，此时要把 替换成 。 显然 是 。将求和下标从 开始，然后就是标准的二项式定理！ 太棒了。但是考虑右侧的 怎么处理。 并不好

原题链接 INFO 题意简述 有 棵树在一条直线上，每颗树高都为 。每棵树倒下后会带倒同方向距离小于 的树。每次随机从左右两颗树中选择一个，被砍倒的树有 的概率向左倒下， 的概率向右倒下。求最后树覆盖的期望。 不难发现任意时刻剩下来的树都是一个区间。这时候就可以从区间 dp 的角度去考虑。 我们不妨设 表示当前剩下区间 的树，在 区间内

我们给每一杯可乐先乘上 让其变成整数。 我们希望构造 ，并且要最小化 。 特判 的情况。考虑把 乘到右边去，得到 移项得到 我们另 表示这个 。我们希望用最小的 让 到达 。我们每选择一个物品，就会让 增加 。 我们对于每个 建出点来，对于每个 ，从 向 连边。我们实际上要找出原图的一个最小环。对于每个 可达的点作为源点跑多源 BFS 即可。 对于任意一组可行解，我们可以