那些你不要的

idea from 127, data, solution from csy2005

算法一

每次删掉位置为奇数和偶数的数，那么所有位置的奇偶性不会变。

剩下来的数为奇数位置上的数，那么偶数位置上的数就没用了，就相当于每次删掉一个奇数位置上的数。

所以答案就是奇数位置上的数的中位数。

求解中位数可以直接排序，也可以使用 std::nth_element。

时间复杂度为 $O(n)$ 或 $O(n\log n)$。

期望得分 $100$ 分。

比特迷宫

idea, data, solution from JohnVictor

算法一

我会直接依次输出 $P$ 的系数！期望得分 $10$。

算法二

我会暴力讨论相邻几位！讨论的多就能获得 $30$ 分。

算法三

考虑爆搜出所有相邻 $k$ 位可以怎么表示。注意这时候可以允许影响到更前面的位。具体的过程类似一个最短路。期望得分 $60$，因为开了 $6s$，有厉害选手选了 $k=24$ 获得了 $100$ 分。

算法四

直接贪心，先通过随机打乱使得 $1$ 的个数不超过一半，然后从后往前，每一步在不把 $0$ 变成 $1$ 的情况下将包括当前位的最多的 $1$ 变成 $0$。时间复杂度分析不清楚，但很多人这样过了。期望得分 ???。

算法五

我们在构造的时候规定 $a,b$ 中二进制的 $1$ 不重合，也就是 $a+b$ 不进位。此时相当于对于 $a\le x\le b$ 操作，这里重定义 $x\le y$ 为 $x\mathrm{\&}y=x$。现在把所有数按照二进制中的 $1$ 的个数分组，设含有 $k$ 个 $1$ 的那组为 $S_k$。我们将会对 $k$ 从大到小操作，在现在的限制下，后面的操作不会影响到已经操作完的部分。

一个关键的观察是，对于 $S_k$ 中的一个数，可以对它进行一次合适的操作，使得它在 $S_{k-1}$ 中的邻居（二进制只差一位）中的任意子集 $01$ 反转。这样，如果我们找到若干个 $S_k$ 中的元素，构成 $T_k$，它们的邻居覆盖了 $S_{k-1}$，那么我们就能合理操作这些集合使得可以将 $S_{k-1}$ 中的元素变为任意状态。

现在，我们可以得到如下算法：首先通过至多一次操作将 $n-1$ 位置的数变为 $1$，然后从大到小对于每一个 $k$，对 $T_k$ 操作，使得 $k-1$ 层中恰有 $T_{k-1}$ 中的数为 $1$。这种做法的总操作次数为 $\sum |T_k|$。

通过贪心算法寻找 $T_k$（每一次找一个能解决尽量多未解决的邻居的），得到的界为 $157885$。可以证明这个算法的操作次数的上界为 $\mathcal{O}(\frac{n\ln \ln n}{\ln n})$。

璀璨宝石

idea, data, solution from he_____he

算法一

首先我们一定是先拿足够多的宝石之后，再去拿所有发展卡。假设我们分别需要 $A,B,C,D,E$ 个宝石，记 $s=A+B+C+D+E$，那么我们需要 $max(A,B,C,D,E,[(s+1)/2])$ 轮去拿。这是因为如果这五个数中存在绝对众数，不妨设是 $A$，那么我们可以每次拿一个 $A$，再拿一个其他类型的宝石，可以把其他类型的宝石都拿到，轮次瓶颈在于 $A$ 的大小，就需要恰好 $A$ 轮。如果不存在绝对众数，我们每次拿两个需要数量最多的类型的宝石，就可以保证一直不出现绝对众数，也就是每次都能拿到两个宝石，需要 $[(s+1)/2]$ 轮。

暴力枚举每次拿哪张发展卡，对每种情况算出所需的每种宝石数量，复杂度 $O(2^n)$，可以通过子任务 1，期望得分 $20$ 分。

算法二

对于 $b_{i,1}=c_{i,1}=d_{i,1}=e_{i,1}=0$ 的部分，由于对于这四种宝石不会减免消耗数量，我们可以直接算出这四种宝石需要拿取多少。而第一种宝石显然需要拿的越少越好。设计 dp 数组 $d_{i,j}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$ 时（此时牌堆顶一定为第 $i+1$ 张发展卡），第一种宝石所需的最少数量。时间复杂度 $O(n^2)$，可以通过子任务 2，结合算法 1 可以获得 $25$ 分。

算法三

对于 $c_{i,0}=d_{i,0}=e_{i,0}=0$ 或 $c_{i,1}=d_{i,1}=e_{i,1}=0$ 的部分，我们同样可以直接算出 $C,D,E$ 三种宝石消耗的数量，设计 dp 数组 $d_{i,j,k}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$，第一种宝石目前需要拿取共 $k$ 个，第二种宝石最少需要拿取多少个。时间复杂度 $O(n^{2}M)$，可以通过子任务 2, 3, 4，结合算法 1 可以获得 $40$ 分。

算法四

如果我们需要的轮次不是 $max(A,B,C,D,E,[(s+1)/2])$，而是 $A,B,C,D,E$ 与 $[(s+1)/2]$ 中任意一个的话，我们都能很轻松的 dp 得到答案。我们考虑通过数方案数来分辨出最大值是其中哪个情况。记 $d_{t,i,j,k,l}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$，第 $t$ 种宝石目前需要拿取 $k$ 个，其余类型宝石目前需要拿取 $l$ 个，有多少种方案。记 $f_{i,j,k}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$，目前总共需要拿取 $k$ 个宝石的方案数。

通过 $d$ 数组，我们可以算出所有最大值为 $A,B,C,D,E$ 的方案对答案的贡献。如果最大值为 $[(s+1)/2]$，我们可以通过容斥的方式，用 $d$ 和 $f$ 算出没有绝对众数时，每个 $s$ 的方案数。这样找到没有绝对众数时最小的 $s$ 即可。

时间复杂度 $O(n^2{M}^2)$，结合算法 3 后期望得分 $60\sim 80$ 分。

算法五

我们抛弃算方案数的计算方法，想办法直接求出这个最大值。考虑这样一个过程：每一次取宝石相当于消了两个不同类型的宝石，我们首先随便消一些，直到出现一类宝石出现次数大于等于一半，我们把所有非这一类的宝石全部留着和这一类宝石相消。考虑用一个 dp 来还原这个过程。记 $d_{i,j,t,k}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$，目前随便消的过程中还剩 $k$ 个第 $t$ 类宝石没被消完，目前最少消（拿取）了多少轮。记 $f_{i,j,t,k}$ 表示：现在桌面上的两张发展卡为 $i,j(j<i)$，并且我们认为第 $t$ 类宝石出现次数会在最终大于等于一半，所以我们留了 $k$ 个非第 $t$ 类的宝石用来和第 $t$ 类的宝石相消，目前最少消（拿取）了多少轮。

我们希望在转移过程中，每次消都是消了两个不同的宝石，这样我们得到的答案一定不会好于最优解。同时我们希望能够达到最优解。也就是存在一种转移，能够在前一半模拟出随便消（$d$ 数组），并可以在任意时刻转移到存在出现大于等于一半的情况（$f$ 数组）。

更进一步的，每次转移都是拿取一张卡，我们可以依次考虑所有宝石种类，所以我们每次要做的就是考虑一些只有 $t,k$ 变化的状态，在需要多拿取若干个某一类宝石后，得到的新的状态是什么。

我们尝试把转移挨个写下来：假设目前是 $d$ 状态中的 $(t,k)$，目前要多拿取 $k^{\prime }$ 个 $t^{\prime }$ 类宝石。

• 如果 $t=t^{\prime }$，那么第 $t$ 类宝石会多 $k^{\prime }$ 个，会转移到 $(t,k+k^{\prime })$。

• 如果 $t\ne t^{\prime }$，那么这两类宝石之间可以相消，有以下两种情况：

  • 如果 $k<k^{\prime }$，那么要么在消的过程中转移到了 $f$ 状态，要么仍然处于 $d$ 状态。

    后者为消（拿取）$k$ 次转移到 $(t^{\prime },k^{\prime }-k)$，前者为消（拿取）$x$ 次转移到 $f$ 状态中的 $(t^{″},k+k^{\prime }-2x)$，其中 $t^{″}\ne t,t^{″}\ne t^{\prime }$，表示我们用 $t$ 和 $t^{\prime }$ 消了 $x$ 次，消之后 $t^{″}$ 出现次数大于等于一半了，剩下的 $t$ 和 $t^{\prime }$ 都留着以后消 $t^{″}$。

  • 如果 $k\ge k^{\prime }$，那么要么在消的过程中转移到了 $f$ 状态，要么仍然处于 $d$ 状态。

    后者为消（拿取） $k^{\prime }$ 次转移到 $(t,k-k^{\prime })$，前者为消（拿取）$x$ 次转移到 $f$ 状态中的 $(t^{″},k+k^{\prime }-2x)$，其中 $t^{″}\ne t,t^{″}\ne t^{\prime }$，表示我们用 $t$ 和 $t^{\prime }$ 消了 $x$ 次，消之后 $t^{″}$ 出现次数大于等于一半了，剩下的 $t$ 和 $t^{\prime }$ 都留着以后消 $t^{″}$。

第二种，假设目前是 $f$ 状态中的 $(t,k)$，目前要多拿取 $k^{\prime }$ 个 $t^{\prime }$ 类宝石。

• 如果 $t=t^{\prime }$，那么我们正好要用前面留下的宝石消这 $k^{\prime }$ 个宝石。
  • 如果 $k\ge k^{\prime }$，直接消（拿取）$k^{\prime }$ 次转移到 $f$ 状态的 $(t,k-k^{\prime })$ 即可。
  • 如果 $k<k^{\prime }$，同样直接消（拿取）$k$ 次转移到 $d$ 状态的 $(t,k^{\prime }-k)$ 即可（这里相当于剩下 $k^{\prime }-k$ 个 $t$ 没被消完，回到 $d$ 状态仍然能保证我们不会消两个非 $t$ 的宝石）。
• 如果 $t\ne t^{\prime }$，那么直接把这 $k^{\prime }$ 个也留着消 $t$，转移到 $f$ 状态的 $(t,k+k^{\prime })$。

转移复杂度 $O(M)$，总复杂度 $O(n^2{M}^2)$，结合算法 3 后期望得分 $60\sim 80$。

算法六

尝试优化转移。可以注意到，两种情况中，要么是在区间 $[k-k^{\prime },k+k^{\prime }]$ 中所有同奇偶部分和一个公差为 $-1$ 的等差数列取最小值，要么是在区间 $[k^{\prime }-k,k^{\prime }+k]$ 中所有同奇偶部分和一个公差为 $-1$ 的等差数列取最小值。

把区间取最小值用数据结构优化可以做到每次转移 $O(\log M)$。时间复杂度 $O(n^{2}M\log M)$，结合算法 3 后期望得分 $80\sim 100$。

算法七

想办法把转移做到 $O(1)$。可以注意到，在一次转移中，对于所有状态，要多拿取的 $k^{\prime }$ 个 $t^{\prime }$ 类宝石是固定的。所以 $k^{\prime }$ 是固定不变的。

对于 $[k-k^{\prime },k+k^{\prime }]$ 这类区间取最小值，区间长度固定，可以类似滑动窗口用单调队列优化，做到所有转移 $O(M)$ 一起处理。

对于 $[k^{\prime }-k,k^{\prime }+k]$ 这类区间取最小值，区间一定跨过了 $k^{\prime }$ 这个位置，可以在两个位置打个标记后求前缀最小值/后缀最小值解决，做到所有转移 $O(M)$ 一起处理。

这样单次转移所有状态就做到了 $O(M)$。总复杂度 $O(n^{2}M)$，可以通过所有数据，期望得分 $100$。

题外话

Splendor 真的很好玩！推荐大家都去尝试。

火星式选拔

idea, data, solution from ix35

算法一

用堆维护所有当前在队伍中的人，暴力模拟题目中的操作。

期望得分 $25$ 分。

算法二

考虑 $k=1$ 怎么做。

设 $f(i)$ 表示如果 $i$ 在队伍里，那么直到哪个人到来后 $i$ 会被踢出。

我们要求的就是 $f(f(\dots (l)))$，使得它不超过 $r$，对 $f$ 数组倍增即可。

期望得分 $25$ 分，结合算法一 $50$ 分。

算法三

考虑区间中 $b_i$ 前 $k-1$ 大的人，由于队伍有 $k$ 个人，所以它们都不可能成为 $b_i$ 最小的人，也就是说它们永远不会被踢出。

于是我们只要考虑剩下的最后一个名额即可，这转化为了一个类似 $k=1$ 的问题。

用主席树维护区间前 $k$ 大即可。

期望得分 $100$ 分。

反重：求熵

idea from djq_cpp, solution, data from he_____he

算法一

暴力枚举所有情况。时间复杂度 $O(T^n{n}^2)$，可以通过子任务 1，期望得分 $5$ 分。

算法二

对于 $n=2$ 的情况，只有限制 $0\le x_1,x_2\le T$ 与 $-c_1\le x_1-x_2\le c_2$ 的限制，容易算出方案数。结合算法 1 后可以通过子任务 1, 2，期望得分 $10$ 分。

算法三

可以再把 $n=3$ 手玩出来。可以通过子任务 1, 2, 3，期望得分 $25$ 分。

算法四

整一点算法。考虑数位 dp，维护两两之间的两个限制目前处于什么状况，并需要记录每个数是否达到上界。状态最多 $3^{n(n-1)/2}{2}^n$ 个，但实际上有用的并没有这么多。由于和正解无关，不在此过多描述，时间复杂度约为 $O(3^{n(n-1)/2}{2}^{n}n\log T)$。根据赛时情况观察，期望得分 $40\sim 50$

算法五

不从值域的角度考虑，转而尝试一个一个把变量消去。比如我们想要消去 $x_n$。想要消去一个变量，那么和这个变量有关的不等式越少越好。不妨设 $x_0=0$，那么会有一些 $x_n\le x_i+c_{n,i}$ 的限制，和一些 $x_n\ge x_i-c_{i,n}$ 的限制。我们分别枚举这两类限制中最紧的限制，这样与 $x_n$ 相关的限制就只剩一个了，但由限制是最紧的，会多出一些 $x_0,\dots ,x_{n-1}$ 之间的限制。枚举完之后，和 $x_n$ 相关的限制就只剩一条形如 $x_i-c_{i,n}\le x_n\le x_j+c_{n,j}$ 了。那么我们就可以再加一条 $x_i-x_j\le c_{n,j}+c_{i,n}$ 的限制之后，考虑所有 $x_1,\dots ,x_{n-1}$ 的方案，对所有方案求出 $x_n$ 的方案数，即 $x_j-x_i-(c_{n,j}+c_{i,n})+1$ 的和即可。这样，相当于我们需要维护一个关于 $x_1,\dots ,x_n$ 的多元多项式，每次相当于把所有 $x_n^k$ 替换为 $[x_i-c_{i,n},x_j+c_{n,j}]$ 中所有数的 $k$ 次方和，而这仍然是一个关于 $x_1,\dots ,x_{n-1}$ 的多元多项式。

时间复杂度 $O(n{!}^2\cdot c^n)$，其中 $c^n$ 为维护多元多项式的复杂度，$c$ 我们认为应该是一个常数，可以通过 $n\le 6$ 或 $n\le 7$，期望得分 $70\sim 90$ 分。

算法六

在上一个算法中，我们实际上做的是枚举 $i$，枚举 $j$，把 $x_n^k$ 替换为某个 $f_k(x_j+c_{n,j})-f_k(x_i-c_{i,n}-1)$（$f_k(x)$ 应为自然数幂和）。考虑拆开 $i,j$ 的贡献，变为只枚举 $i$，把 $x_n^k$ 替换为 $-f_k(x_i-c_{i,n}-1)$，和只枚举 $j$，把 $x_n^k$ 替换为 $f_k(x_j+c_{n,j})$ 分别统计一次答案。

一个你可能的疑问是，我们不是还需要保证 $x_i-c_{i,n}\le x_j+c_{n,j}$ 吗？但实际上，我们在枚举 $i$ 之后，我们并不需要再枚举 $j$ 那一侧最紧的限制是什么了，我们只需要保证所有限制都满足就可以。因此我们统计的所有合法的 $x_1,\dots ,x_{n-1}$ 的方案仍然是满足 $x_i-c_{i,n}\le x_j+c_{n,j}$ 的，只是我们并不知道具体哪个是最紧的限制 $j$，只知道对所有 $j$ 都满足这个限制。

这样复杂度就变为了 $O(n!2^n\cdot c^n)$，其中 $c$ 和算法 6 中同样。可以通过所有数据，期望得分 $100$ 分。

鸽子收费站

idea, solution from hehezhou, data from 127

考虑按时间顺序维护所有询问，对每个收费站依次处理。通过简单处理，题意即可转化为维护一个序列，支持：

1. 单点修改
2. 单点查询
3. 将 $[l_1,r_1]$ 中值在 $[l_2,r_2]$ 的元素全部置为 $r_2$

以下均在描述转化后题意的解法，且认为 $n,Q$ 同阶。

算法一

我会暴力！

直接 $O(n^2)$ 暴力做修改操作。

期望得分 $10$。

算法二

若保证了 $r_2\le 20$，则由于操作 $3$ 只会使元素变大，可以暴力修改需要修改的位置。在线段树上维护区间中是否有 $0,1,\cdots ,20$ 中的值，即可在 $O(\mathrm{实}\mathrm{际}\mathrm{修}\mathrm{改}\mathrm{个}\mathrm{数}\times \log n)$ 时间内完成修改。

总复杂度 $O(n\log nmax{r}_2)$，期望得分 $20$。

算法三

依然是考虑线段树。主要考虑第三种操作。如果我们能做到：仅当 当前节点区间与操作区间相交而不包含 或者 当前节点区间中有两种及以上的值需要修改 时，才继续递归，则所有修改访问的线段树节点数是 $O(n\log n)$ 的。定义一个节点的势能是区间中元素种类数，总势能定义为每个节点的势能之和，不难分析得到这个复杂度。

怎么判断 当前节点区间中有两种及以上的值需要修改 呢，这看起来没啥高论，考虑在每个线段树节点维护一棵平衡树，代表区间元素排序并去重后的结果。此时判断只需在平衡树上二分即可。但是不难发现这么做的问题：如果一个线段树节点代表的区间中只有一种值需要修改，但是这种值可能遍布整个区间，我们没法快速修改所有后代线段树节点的平衡树。

怎么做到“牵一发而动全身”呢，答案是把平衡树连起来。实际上对于上述问题，这个区间修改后，区间中值的相对顺序没有任何变化，也就是平衡树的结构并不需要改变。考虑只在线段树根节点的平衡树上维护具体的元素值，对于其他线段树节点的平衡树，每个平衡树点连向线段树上父亲所在平衡树中，值相同的平衡树点。这样一来，如果一个线段树节点代表的区间中只有一种值需要修改，只需要通过某种方式修改当前节点平衡树中对应点代表的值，线段树后代节点无需继续递归修改。

在这个结构上修改，所有操作需要修改的线段树总节点数就是 $O(n\log n)$ 的。接下来只需要考虑一些细节即可。为了方便修改，考虑一个基础操作：对于某个平衡树节点，查询它在线段树上左/右儿子的平衡树上的前驱。这可以通过每个平衡树节点再记录在线段树上左/右儿子的平衡树上对应的节点，并维护平衡树子树中是否有这种向左/向右的链接，将问题转化为查询当前平衡树上向前最近的有左/右链接的节点来完成，称为递归操作，单次操作复杂度 $O(\log n)$。

对于查询操作，直接找到线段树叶子，然后从对应平衡树节点不断在线段树上向上跳到根即可得到真实值，复杂度 $O(\log n)$。

对于单点修改操作，直接通过递归操作不断找到平衡树中应该插入的位置完成，复杂度 $O({\log }^{2}n)$。

对于区间修改操作，通过递归操作不断求出当前节点 $[l_2,r_2]$ 中最前和最后的节点，并依此判断是否需要递归，若需要插入 $r_2$ 也可以找到插入位置。在操作结束后，及时清理无用节点，通过均摊分析不难得到总复杂度为 $O(n{\log }^{2}n)$。

因此总复杂度 $O(n{\log }^{2}n)$，期望得分 $100$。