UOJ Logo qingyu的博客

博客

UOJ NOI Round #7 题解

2023-07-16 19:38:11 By qingyu

那些你不要的

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\&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^2M)$,可以通过子任务 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^2M^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'$ 个 $t'$ 类宝石。

  • 如果 $t=t'$,那么第 $t$ 类宝石会多 $k'$ 个,会转移到 $(t,k+k')$。

  • 如果 $t\neq t'$,那么这两类宝石之间可以相消,有以下两种情况:

    • 如果 $k < k'$,那么要么在消的过程中转移到了 $f$ 状态,要么仍然处于 $d$ 状态。

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

    • 如果 $k\geq k'$,那么要么在消的过程中转移到了 $f$ 状态,要么仍然处于 $d$ 状态。

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

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

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

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

算法六

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

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

算法七

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

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

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

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

题外话

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

火星式选拔

idea, data, solution from ix35

算法一

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

期望得分 $25$ 分。

算法二

考虑 $k=1$ 怎么做。

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

我们要求的就是 $f(f(\ldots(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^nn^2)$,可以通过子任务 1,期望得分 $5$ 分。

算法二

对于 $n=2$ 的情况,只有限制 $0\leq x_1,x_2\leq T$ 与 $-c_1\leq x_1-x_2\leq 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^nn\log T)$。根据赛时情况观察,期望得分 $40\sim 50$

算法五

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

时间复杂度 $O(n!^2\cdot c^n)$,其中 $c^n$ 为维护多元多项式的复杂度,$c$ 我们认为应该是一个常数,可以通过 $n\leq 6$ 或 $n\leq 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}\leq x_j+c_{n,j}$ 吗?但实际上,我们在枚举 $i$ 之后,我们并不需要再枚举 $j$ 那一侧最紧的限制是什么了,我们只需要保证所有限制都满足就可以。因此我们统计的所有合法的 $x_1,\ldots,x_{n-1}$ 的方案仍然是满足 $x_i-c_{i,n}\leq 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\leq 20$,则由于操作 $3$ 只会使元素变大,可以暴力修改需要修改的位置。在线段树上维护区间中是否有 $0,1,\cdots,20$ 中的值,即可在 $O(实际修改个数\times \log n)$ 时间内完成修改。

总复杂度 $O(n\log n\max 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$。

评论

TOMWT
出题人速速出现!
lovelove
前排
tl_xujiayi
哇!我全是算法1!我会暴力!
CharlieV
💯
feecle6418
splendor 很好玩
olim_looc
有木有有打捞康康[这个](https://uoj.ac/submission/644713)提交的正确性/kel
tl_xujiayi
小青鱼!
tl_xujiayi
其实火星式选拔还有一档暴力,应该比堆分数还要低,堆是我后来想出来的

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。