string

本题的关键点在于挖掘好串的性质。容易发现好串实际上是一个离散化的完全 Trie。而我们的修改是区间的，不容易维护。考虑差分。

一个长度为的串差分后就变成了长度为的串。如果这个串是好串，那么我们可以将其差分后的串理解为一棵完全二叉树的中序遍历。这棵二叉树的同一层的结点上的数是一样的。

因此我们的问题转化成：每次询问一个长度为形如的区间，要求单点修改把这个区间的串改成好串的差分串，求最小操作次数。那么我们显然可以将二叉树的每一层结点分开考虑，取和中出现次数少的算入贡献即可。实际实现过程中可以利用二进制数的性质（lowbit）完成。

对于多组询问，我们可以预处理表示。这样就支持回答单个询问了。

总时间复杂度。

Lost Island1

思维 推理

红蓝眼的扩展题。我们先考虑这个经典的红蓝眼睛问题：

一个岛上有个红眼和个蓝眼的人（），但每个人都不知道自己眼睛的颜色。每个人都能看见其他人眼睛的颜色，但他们不会去向别人询问自己的眼睛的颜色。这个岛上有个规矩：如果某个人知道了自己眼睛的颜色，那么他在第二天就需要自杀。

这天来了个旅行家，他说：这个岛上既有红色眼睛的人也有蓝色眼睛的人，也只有这两种颜色。

问岛上的人是否会自杀。会以怎样的方式自杀。

首先我们考虑的情况。可以发现第二天那个唯一的蓝眼睛的人会自杀。

原因

因为他看不到别的蓝眼睛的人，而旅行家又说有蓝眼睛的人，那么只可能是他自己。

然后考虑的情况。到了第二天没有人会自杀。但是到了第三天，两个蓝眼睛的人会同时自杀。

原因

如果你只看到一个蓝眼睛的人，且第二天这个人自杀了，那么你就可以断定蓝眼睛的人只有这一个人。

但是第二天没有人自杀。说明这个蓝眼睛的人也看到了蓝眼睛的人，也就是说不只一个蓝眼睛的人，而你只看到了一个蓝眼睛的人。所以你也是蓝眼睛的人。

因此归纳得到，若，那么第天所有蓝眼睛的人会同时自杀。

而对于剩下的个红眼睛的人，他们发现蓝眼睛的人都自杀了，他们就知道自己不是蓝眼睛的人了。因此他们会在第天全部自杀。

的情况类似。

回到原问题。可以推广得到：

  • 若有两个及以上的，那么答案就是。
  • 若有唯一的，那么答案是。
  • 若没有，那么答案是，其中表示可重集的次大值。

代码

Two Pirates - 22

DP 期望

这题有一个很妙的模型转化。我们把这过程倒过来，同时把拿东西改成放东西。

不妨用黑球表示神仙（没喝醉的）放的，白球表示傻逼放的。

我们将宝物按从小到大排序。从空的序列开始：

  • 首先神仙放一个黑球。
  • 然后傻逼放一个白球。傻逼原本的操作是随机选一个宝物，倒过来后就是：随机一个空隙插入一个白球。
  • 接下来是神仙放球。由于神仙拿最大的，因此他会把球放序列末尾。
  • 回到步骤。

转化后的模型有一个特点：每次放一个白球，只会让其后面的球平移一个位置。

这样就可以方便地 DP 了。设表示当前序列长度为，左数第个球是黑球的概率。

如果轮到神仙放球，那么，。

如果轮到傻逼放球，那么。

代码

Chess Tournament3

个队伍的循环赛，只有个战场（一轮比赛最多有场对决），求一种安排的方案使得最小化比赛的轮数。

。

构造

本题的构造是：首先取，构造一个妙妙的比赛日程序列。然后我们取这个序列的区间作为第轮比赛的内容。

构造方法是：对于是奇数的情况，我们取一共个二元组加入到对决日程末尾。然后我们将每个二元组循环一位变成，再把这个新的二元组序列加入到对决日程的末尾。重复次我们就得到了一个长度为的序列，且每个无序二元组在其中恰好出现一次。

至于为啥这个序列妙得能够过本题，就不证明了（咕咕）。

对于是偶数的情况，我们对构造与上述类似的个二元组后，将加入其中即可。剩余的步骤类似。

代码

X Number

数位 DP

先转化为前缀计数，枚举与限制相同的前缀，那么后面可以随便填。直接枚举的出现次数，并求出其他数字的最大出现次数，然后做个背包即可（带一个组合数的系数）。

我实现的复杂度是。不过常数是很小的。数位 DP 的常数一般不大。

这题写代码的时候遇到了一个问题，静态查错才查出来的。说明对拍不是万能的。详情见我两发提交的不同之处。

代码

Complete the MST

给出一个个点条边的边带权无向图，要求将其补成一个完全图，使得所有边权值的异或和为，且这个完全图的最小生成树的权值和最小。

。

并查集 二合一

如果这个图的补图存在环，那么这个完全图的 MST 就无法用完补图上所有的边。因此我们可以把补图的边赋权为，留一条边赋权为原图的异或和。然后做一个类似 01-MST 的贪心即可。

否则，我们仍然先做一个 01-MST，然后做一个类似次小生成树的东西，即我要么将答案加上原图的异或和，要么去掉当前的MST上的一条权值为的边（补图上的边），加入一条原图上的边。

时间复杂度。

代码

Swap Pass

如果整个排列是一个环，那么我们可以固定一个点，每次把上的点权换到对应的编号上。这样肯定是合法的。

如果不是一个环，就想办法合并成一个环。

对着某个点极角排序一下，然后相邻的来合并，这样就避免了相交。

时间复杂度。

代码

Tree Calendar

给出一棵个点的以为根的树，初始时每个结点权值是它的 DFS 序（某一个）。接下来进行若干次点权交换：

  • 每次找到一个点权的字典序最小的二元组且是的父亲，然后交换两者的点权。

现在给出若干次交换后的树，问它原本的 DFS 序是什么样子，以及经过了多少次交换到达这一状态。

无解输出 NO。

。

性质

本题有三个重要的性质。

手玩一下，可以发现你的操作步骤大概是，不停把权值往下推直到推不动，然后推。

性质：当你推到推不动的时候，恰好代表它所在结点的后序遍历的次序（post-order）。由于后序遍历不唯一，因此更严谨地说，是初始状态的 DFS 序对应的后序遍历。也就是说当你把都推到推不动的位置上去后，所在结点的后序遍历次序恰好是他们目前的点权。

性质：对于任意结点，将它的儿子按点权排序。那么在交换过程中，这个顺序不会发生变化。

性质：当把都推到推不动的位置上去后，根结点的点权恰好为。换言之每个点权都是从根结点开始被往下推的。

手玩一下可以证明。

于是，根据性质，我们可以直接利用当前的树构建出它的初始状态的 DFS 序。然后我们就可以求出其对应的后序遍历。

结合性质和性质，我们可以找到当前被推的是哪个权值，假设是。由于操作可逆，我们就倒着把它推回根结点。

思考一下可以发现：

  • 得恰好在后序遍历的位置上。
  • 对于，则的位置应该在其初始状态的 DFS 序所在结点的级祖先上。

另外，在倒推前要先检查原本所在结点是不是后序遍历所在结点的祖先。

时间复杂度。

代码

Bags and Coins

位运算 背包

容易转化为 01 背包问题，需要位运算优化。记录表示最少选择前多少个物品能凑出。这样可以构造出方案。

为了维护，需要在 DP 转移的过程中找到这一轮变成的位。用 bitset 可以用 _Find_first 方法（虽然看上去很不官方）。手写位运算的话要注意预防 UB。具体来说：

  • 32 位整型的位移值必须在范围内
  • 左移操作不能溢出

具体来说就是这样的：

unsigned ls(unsigned x, int y) {
    return ((y) ? (((x) & ((1u << (32 - (y))) - 1)) << (y)) : (x));
}

代码

游戏

筛法

（JXOI 2018）

的情况要特判。

问题可以转化为一个筛法问题，类似求中的“伪质数”的个数。

考虑魔改埃氏筛的过程。为了辅助筛法我们需要预处理里的质数。

详情见 代码实现

1. Samara Farewell Contest 2020 (XXI Open Cup, GP of Samara) Prob. J ↩

2. Samara Farewell Contest 2020 (XXI Open Cup, GP of Samara) Prob. D ↩

3. Samara Farewell Contest 2020 (XXI Open Cup, GP of Samara) Prob. I ↩