UOJ Logo hehezhou的博客

博客

UOJ Round #22 题解

2021-10-03 08:34:59 By hehezhou

首先作为管理员主要苦力向大家谢罪。这场比赛由于准备比较匆忙,以及管理员们的经验不足,导致部分分的分值和范围设置上有诸多不合理之处,样例与数据的强度也有较大差距,在此为造成大家不便表示歉意。

月球列车

idea from he_____he,mayaohua, solution from he_____he, data from hehezhou.

算法1

直接暴力模拟!时间复杂度 $O(nm)$ ,可以通过子任务 1,期望得分 $30$ 分。

算法2

考虑对于一次查询 $x$ ,依次决定每一个二进制位是 $0$ 还是 $1$ 。设 $a'_{j,i}=a_i \& (2^{j+1}-1)$ ,其中 $\&$ 表示二进制与。对于每个 $i$ , $a_i+x$ 的 $2^j$ 位是 $a_i\oplus x$ 的 $2^j$ 位再异或上 $a_i+x$ 的第 $j-1$ 位是否进位。前者容易处理,后者等价于 $a'_{j-1,i}+(x\& (2^j-1))\geq 2^j$ 。所以求 $\bigoplus\limits_{i=1}^n (a_i+x)$ 的 $2^j$ 位时只需求出有多少个 $a'_{j-1,i}\geq 2^j- (x\& (2^j-1))$ 。可以排序预处理然后每次查询对每一位二分。

时间复杂度 $O((n+m)\log n\log a_i)$ ,可以通过前两个子任务,期望得分 $60$ 分。

算法3

注意到排序预处理的部分可以利用上一次排序的结果,将新的一位为 $0$ 的部分和为 $1$ 的部分归并排序,使预处理复杂度降至 $O(n\log a_i)$ 。

将查询离线之后,同样可以按上述方法将 $x$ 的前 $j-1$ 位的顺序用 $O(m\log a_i)$ 的复杂度求出。然后对于每一位,线性 two pointers 求出每个查询在这一位上的答案。

时间复杂度 $O((n+m)\log a_i)$ ,可以通过子任务 3,与算法 2 结合可以通过前三个子任务,期望得分 $90$ 分。

算法4

由于强制在线,我们不能预处理出所有查询的信息,但我们可以预处理出所有 $a_i$ 的信息。设对于 $j$ 预处理出的 $a'_{j,i}$ 的顺序为 $b_{j,1}\leq b_{j,2}\leq \cdots \leq b_{j,n}$ 。默认 $b_{j,0}=-\infty,b_{j,n+1}=\infty$ 。我们原先做的事就是将其中的一些 $+2^j$ 再和剩下的归并得到 $b_{j+1,1}\leq b_{j+1,2}\leq \cdots \leq b_{j+1,n}$ ,然后对于每个查询找到 $2^{j+1}-(x\& (2^{j+1}-1))$ 大于多少个 $b_{j,i}$ 。

此时多预处理出两个数组 $c_{j,i,0}=\max\{x|b_{j+1,x}\leq b_{j,i}\}$ 和 $c_{j,i,1}=\max\{x|b_{j+1,x}\leq b_{j,i}+2^j\}$ 。这个容易归并在 $O(n\log a_i)$ 内做到。

对于 $x$ 查询的时候如果求出 $2^{j+1}-(x\& (2^{j+1}-1))$ 在 $[b_{j,k},b_{j,k+1})$ 之间,那么直接用 $c_{j,k,0/1}$ 就可以得到 $j+1$ 的答案。这是因为 $\{b_{j+1}\}$ 中不存在 $(b_{j,k},b_{j,k+1})$ 中的数和 $(b_{j,k}+2^j,b_{j,k+1}+2^j)$ 中的数,$c_{j,k,0/1}$ 得到的解和 $2^{j+2}-x\& (2^{j+2}-1)$ 得到的解一定相同。

每次查询复杂度 $O(\log a_i)$ ,总复杂度 $O((n+m)\log a_i)$ ,可以通过所有子任务,期望得分 $100$ 分。

月球铁轨

idea from wangziji,he_____he, data,solution from hehezhou.

算法一

我会暴力!枚举每个区间再枚举每个位置的选择,然后排序求出第 $k$ 小。

复杂度 $O(2^nn^2)$,期望得分 $0$ 分。

算法二

定义 $f(x,T)=\max_{y\in T}(x\oplus y),g(x,T)=\min_{y\in T}(x\oplus y)$,其中 $x$ 是一个数,$T$ 是一个 $\mathbb{F}_2$ 上的线性空间。

考虑如何计算一个区间的最优稳定度。令 $c_i=a_i\oplus b_i(1\leq i\leq n)$。对于区间 $[l,r]$,求出 $x_{l,r}=\oplus_{i=l}^{r} a_i$,再对 $c_l\cdots c_r$ 求出张出的线性空间 $T_{l,r}$,则答案为 $f(x_{l,r},T_{l,r})$。

维护线性空间(可以维护一组基)以及求出 $f(x_{l,r},T_{l,r})$ 的复杂度均为 $O(m)$。

时间复杂度 $O(n^2m)$,可以通过子任务一,期望得分 $10$ 分。

算法三

我们发现如果一个区间的线性空间维数达到 $m$,则这个区间的答案就是 $2^m-1$。

随机数据下,维数小于 $m$ 的区间只有 $O(nm)$ 个,求出这些区间的答案后,使用经典算法求出第 $k$ 小即可。

时间复杂度 $O(nm^2)$,可以通过子任务三。

算法四

定义 $S_n=\oplus_{i=1}^n a_i$,则 $x_{l,r}=S_r\oplus S_{l-1}$。

对于性质 B,我们发现一个区间的答案就是 $S_r\oplus S_{l-1}$,于是我们把所有前缀异或和插入一颗 trie,然后 trie 上二分即可求出第 $k$ 小的答案。

时间复杂度 $O(nm)$,可以通过子任务四。

算法五

对于性质 C,此时区间 $[l,r]$ 答案就是 $f(0,T_{l,r})$。注意到一个性质,对于某个固定的 $l$,$T_{l,r}$ 最多只有 $m+1$ 种,维数分别为 $0\cdots m$,并且如果区间 $A$ 包含区间 $B$,$T_A$ 包含 $T_B$。

使用扫描线算法,每次在序列末尾加入一个数 $S_r$,并且维护出每个左端点当前对应的线性空间。加入一个数会使当前一个后缀的线性空间维数变大 $1$。维数变大总次数是 $O(nm)$ 的,于是暴力维护即可。

加粗部分更详细解释是,考虑使用 $S_{1}\cdots S_{r-1}$ 异或出 $S_r$,并且最小下标尽可能大,设这个最小下标是 $p$(如果不存在则为 $0$)。则 $p+1\cdots r$ 对应的 $T_{i,r}$ 维数均加一, $1\cdots p$ 对应的维数均不加一。

时间复杂度 $O(nm^2)$,可以通过子任务五。

算法六

我们发现一个性质,$f(x\oplus y, T)=f(x,T)\oplus g(y,T)$。于是区间 $[l,r]$ 的答案也是 $f(S_{l-1},T_{l,r})\oplus g(S_r,T_{l,r})$。

使用算法五维护出所有 $T_{i,r}$ 以及 $f(S_{i-1},T_{i,r})$。并且维护 $m+1$ 棵 trie,第 $t$ 棵 trie 包含 $f(S_{i-1},T_{i,r})(\texttt{dim}(T_{i,r})=t)$,其中 $\texttt{dim}$ 表示维数。

对于某个 $r$,$T_{i,r},g(S_r,T_{i,r})$ 同样最多 $m+1$ 种,且每一种对应一个维数。

于是计算出这几个值,并在对应 trie 上查询,但是这里有两个方向,一种是二分答案(逐位确定),每次跑一遍上述过程,时空复杂度分别为 $O(nm^3),O(nm)$,另一种是使用可持久化 trie 并多树二分,时空复杂度均为 $O(nm^2)$。

均可以通过子任务二,期望得分 $25\sim 70$ 分。

算法七

对于算法六的逐位确定方向,但是确定每一位的时候,通过 trie 的上一层,只维护出 trie 对应的一层。

时间复杂度 $O(nm^2)$,空间复杂度 $O(nm)$,可以通过本题,期望得分 $100$ 分。

月球车站

idea,solution from jiqimao, data from hehezhou.

以下把硬币的正反面属性称为颜色,0 表示背面,1 表示正面。

算法一

对于 $p=0$ 的情况,伏特永远不会翻转,因此当且仅当初始硬币全为正面,答案为 0,否则 skip 蚤也选择不操作答案为 -1。

可以通过子任务一,期望得分 $5$ 分。

算法二

对于 $p=1$ 的情况,伏特每次遇到背面的硬币都会将它翻转。

我们把同色的连续一些硬币称为一段。对于段数大于 $2$ 的局面,skip 蚤也只需要每次遇到正面的硬币都将它反转即可。容易发现这样即可让游戏无法结束。

当局面为全 0 或全 1,伏特显然获胜。

当局面为 00...011...1 时,显然伏特会获胜。

当局面为 11...100...0 时,伏特能否获胜与 1 的个数有关。当仅有一个 1 时,不管 skip 蚤如何操作,都会变为上述伏特必胜局面。否则,skip 蚤不翻转第一个 1 ,即可使段数大于 2 ,于是游戏无法结束。

判断一下即可,可以通过子任务二,期望得分 $10$ 分,结合算法一期望得分 $15$ 分。

算法三

规定一些记号:$c_x$ 表示局面 $x$ 的第一个硬币的颜色。$trans_{x,c}$ 表示局面 $x$ 去掉第一个硬币后接一个颜色为 $c$ 的硬币,即 $trans_{abcd,e}=bcde$。$f_x$ 表示局面 $x$ 的答案。

我们可以暴力地列一个 dp 出来。

若 $c_x=1$ ,$f_x=\max(f_{trans_{x,0}},f_{trans_{x,1}})+1$,

若 $c_x=0$,$f_x=pf_{trans_{x,1}}+(1-p)f_{trans_{x,0}}+1$。

这是个带环还带 $\max$ 的 dp,我们枚举 $\max$ 取值来源,每次用高斯消元求解。

特判掉 $p=1$ 或 $p=0$ 的情况之后若出现矩阵不满秩的情况则一定不合法。另外若求出的dp值不满足上述约束则也不合法。可以证明最多只有一种情况合法(因为最优策略唯一)。若没有合法情况输出 -1 ,否则输出唯一合法的解即可。

注意求解需先用 double 算出最优策略再算出取模后的答案。

复杂度为 $O(2^{2^{n-1}}\cdot2^{3n})$,可通过子任务三,期望得分 $10$ 分,结合算法一、二期望得分 $25$ 分。

算法四

为了进一步挖掘性质优化算法,先来研究一下两人都绝顶聪明时的这个博弈问题(伏特希望最小化步数,skip 蚤希望最大化步数)。

首先有一个很自然的问题:为什么 skip 蚤不是能翻就翻呢?其实是因为当 skip 蚤翻掉一个硬币时,他也就丧失了接下来对这个硬币的操作权。对于一个正面硬币,主动权掌握在 skip 蚤手中,而对于背面硬币,skip 蚤就陷入被动。

考虑到全正的局面是已知的最终局面,我们从这个局面开始推出其他局面的最优步数。

具体地,类似最短路的过程,我们维护一个队列,其中存储一些局面,它们已知最优步数且等待扩展其他局面。这些局面要按照最优步数从小到大排列。

从队头取出一个已经确定最优步数的局面 $z$ ,考察有哪些局面能一步转移到它,设为 $x,y$,其中 $c_x=0,c_y=1$。则如果 $x$ 是第一次被访问到,则 $x$ 的最优决策即可转移到 $z$。(伏特希望最小化步数)。类似的,如果 $y$ 是第二次被访问到,则 $y$ 的最优决策转移到 $z$。(skip 蚤希望最大化步数)

被扩展到的新局面存到队尾即可。

注意这里的 $x$ 和 $y$ 只有第一个硬币不同。则可以发现 $x$ 和 $y$ 总是同时被访问到,它们要第一次都是第一次,要第二次都是第二次。这样我们发现,每次都有且仅有一个局面可以扩展。

那么在一种理想的情况下,局面之间的转移关系就构成了一条链,所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。

但是还有一个例外:当全正局面作为第二次访问到的 $y$ 出现时,它已经无法再被扩展了。此时还没有被扩展到的局面就是无解局面:以它们为初始局面的游戏无法结束。

选手们当然可以验证出在给定的数据范围内不存在这种例外情况。就算没有得到这个结论,也可以在代码中特判。当存在无解局面时,不管初始局面是否无解直接输出 -1 即可,这是因为在伏特随机的游走的时候,总会有可能走到无解局面。

下面还是证明一下在 $n$ 取任何值时都不会存在上述例外发生。即对于任何初始局面,伏特有必胜策略。

证明:我们把初始局面的硬币按 $1$ 到 $n$ 标号。从硬币按 $1$ 到 $n$ 排列到下一次硬币按 $1$ 到 $n$ 排列的一次过程称为一回合。对于每一回合,起初伏特看到背面的硬币就翻面,直到 skip 蚤第一次操作,伏特在这一回合之后就都不操作。

这样会发现每一轮过后局面表示的二进制数都会变小。总会变成全 0,此时伏特一路翻过去就获胜了。

证毕。

注意,上面的这个策略只是保证获胜的策略,并不是步数最少的策略。

于是,得到了这样的结论:局面之间的转移关系构成了一条链,所有局面的最优步数恰好取遍了 $0$ 到 $2^n-1$ 。我们可以按局面在这条链上的位置来给局面编号,局面 $i$ 的最优步数为 $i$,以下均使用这个标号描述局面

回到最初的问题。当伏特操作与否随机时,利用这个结论来优化一下算法。

对于 skip 蚤,他从 $i$ 要么到 $i-1$,要么到某个 $x(x < i-1)$。对于伏特,他从 $i$ 要么到 $i-1$,要么到某个 $y(y > i-1)$。下面证明 skip 蚤每次都从 $i$ 到 $i-1$,即期望 $f_i$ 单调递增。

反证,若 $x < y,f_x > f_y$,则从 $y$ 到第一次到达 $x$ 的这些回合里,skip 蚤都从 $i$ 走到 $i-1$,那么必定经过 $x$。第一次到达 $x$ 之后按之前的最优策略走。则 $f'_y > f_x > f_y$,与最优性矛盾。则 $f_i$ 单调得证。

于是我们去掉了转移方程中的 $\max$,可以高斯消元解决,而观察方程组形态可以优化到 $O(2^{2n})$。

可以通过子任务三、四,期望得分 $40$ 分,结合算法一、二期望得分 $55$ 分。

算法五

观察到从局面 $i$ 一定会经过局面 $i-1$。我们改变状态定义:从 $i$ 到 $i-1$ 的期望步数。写出方程发现可以按链的顺序递推,优化为 $O(2^n)$。

期望得分 $100$ 分。

bonus: 是否可以在多项式复杂度内解决本题或得到局面序列的某一项。

评论

x_Yi_x
data from hehezhou
Jacder
data from hehezhou
Lillia
data from hehezhou
Clovers
data from hehezhou
_map_
hhz,我的超人!
oisdoaiu
orz hehezhou
Rainbow_sjy
orz hehezhou
run
老师为什么我昨天考试写上去给零分
run
老师为什么我昨天考试写上去给零分
run
必须用c加加才能给分是吗老师
huangzirui
题目好神啊orz
tl_xujiayi
@hehezhou NB
Usueles
@hehezhou 神级选手
CCPSDCGK
Orz

发表评论

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