非常有趣的题目。 首先观察样例，不妨猜测蛇一定是对称的（这点我们稍后证明）。因此我们可以将这个正方形砍掉一半只保留左上角。 考虑对角线上的点，每个点必然不同的蛇。这是因为一条蛇只能往右侧和下方走，所以一条蛇不可能同时占有一个格子和一个格子右上角的格子。 因此，我们考虑为每个对角线上的格子分配一个长度，其对应的棋盘结果是唯一的。因为你只能贴着边界摆放。 比如考虑这张图，如果这样摆放，那么 两个点

非常好题目。 我们考虑计算出所有可行的答案最后除以 来计算出答案。 考虑一个简单的 dp 设计。令 表示前 个数进行了 次加法操作所得到的方案数。 转移是每次加入一个数或者直接乘转移到下一个位置。你发现这个复杂度直接爆炸了，因为 的范围是 。 我们希望把状态从 中踢出去。 考虑使用乘法分配律。但是暴力展开之后实际上并不好处理。我们继续观察一下，考虑每次操作对每个位置产生的影响，也就是下

▶INFO 题意简述 有 个格子，每个格子有一个参数 。有一枚棋子初始在第 个格子，力量值为 。有两名玩家轮流操作这个棋子，假设当前棋子在第 个格子，当前玩家可以选择增加最多 的力量值，然后将棋子移动不超过当前力量值的距离（不能原地不动）。先到 的玩家获胜。

写完这篇题解就去睡觉。 上来经典套路，方差等于平方的均值减去均值的平方，对应到这里就是 。 我们来考虑如何计算一下这两个东西。 首先是 。考察 是 之间均匀独立分布的随机变量， 那么 。我们注意到实际上 的分布是一样的，因此这两个期望也是一样的。 就是 。考虑全期望公式。 维护一下前缀和即可。 接下来是 。我们如法炮制。 前面的 我们继续用全期望公式展开之后是 。想之前那样维护一个前缀

▶INFO 题意 给定 个字符，第 个字符的代价是 ，现在你需要用这 个字符构造出 个互相不为前缀的字符串，使得总共的权值和最小。字符串的权值是所有字符的权值和。 我们发现这个等价于在一棵无限大的 Trie 树上找到 个叶子节点，使得叶子

非常好题目啊。 APIO 之前有人给我推了这个题目，APIO 之后有人和我说这个题目和 T1 很像。 不过我没去 APIO 不知道啊。 题目可以转化为下面这个问题：有两条相互平行的链，每条从 指向 。同时两条链之间也有若干条无向边，保证每个点只和一条连接两条链的边连边。你需要给无向边定向使得图没有环。 对于 的情况，只需要在上链的 和下链的 之间连边即可。 对于没有环的情况，我们总是可以进

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

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

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

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