2024.11.14 题目

总结：2024.11.14 模拟赛

邻间的骰子之舞

Yoimiya 有一个文本编辑器，一开始这个文本编辑器里面有一个字符 $\text{Y}$。

文本编辑器支持剪贴板，也就是复制粘贴操作。Yoimiya 可以进行两种操作：

• 复制：该操作耗费 $x$ 秒，进行该操作后，剪贴板中的字符串将被替换为当前文本编辑器中的字符串。
• 粘贴：该操作耗费 $y$ 秒，该操作会将剪贴板中的字符串拼接到文本编辑器中的字符串的末尾。

一开始，剪贴板中是空字符串。给定正整数 $N$，问最少需要多少秒，才能使文本编辑器中 $\text{Y}$ 的个数 $>N$。

星海浮沉录

平衡树 线段树

Yoimiya 有一个长为 $n$ 的序列 $a$。她会执行 $q$ 次操作：

• $\boxed{1p}$：执行 $\text{swap}(a_p,a_{p+1})$。
• $\boxed{2x}$：你需要找一个长度 $\ge x$ 的区间，最小化这个区间中所有数的 $\text{mex}$。

其中，$\text{mex}(x_1,x_2,\cdots ,x_k)$ 表示最小的没有在 $x_1,x_2,\cdots ,x_k$ 中出现过的非负整数。例如，$\text{mex}(0,1,3)=2$，$\text{mex}(1,2)=0$。

勾指起誓

有 $m$ 个选手参加了 Naganohara Yoimiya 举办的一场答题比赛。

这场比赛共有 $n$ 道题目，Naganohara Yoimiya 会将这些题目以任意顺序排列，然后按照排列好的顺序依次问出每道题。在问出一道题目后，如果当前还未被淘汰的选手都会这道题目，或者都不会这道题目，那么没有人会被淘汰；否则，不会这道题的人会被淘汰。最后没有被淘汰的选手将获得胜利。

现在 Naganohara Yoimiya 已经知道了每个人是否会做每道题，也就是说，Naganohara Yoimiya 已经确定了一个 $n\times m$ 的 01 矩阵 ，如果 ，那么在问第 $i$ 道题时，第 $j$ 个人一定能答对这道题目；否则一定不会。

你需要对每个 $1\le i\le m$ 求出有多少种题目的排列能够使第 $i$ 位选手获得胜利。答案对 $998244353$ 取模。

第八交响曲「千日同升」

Yoimiya 有一台机器，这台机器可以对一个序列 $a$ 进行操作，且只支持一种操作：

• $\text{CompareAndSwap}(i,j)$：如果 $a_i>a_j$，交换 $a_i,a_j$ 的值；否则不做任何操作。其中 $i\ne j$。

进行一次这个操作耗时 $1$ 单位时间。

此外，这台机器还可以同时并行地执行多个操作。

具体来说，Yoimiya 可以同时给出 $k$ 对 $(i_1,j_2),(i_2,j_2),\cdots ,(i_k,j_k)$，且满足 $\forall x\ne y$，$i_x,i_y,j_x,j_y$， 互不相同（即每个 $a_p$ 只会在至多一个操作 $(i_x,j_x)$ 中被涉及到）。然后这台机器会同时对每个 $x=1,2,\cdots ,k$ 执行 $\text{CompareAndSwap}(i_x,j_x)$。

这台机器可以同时并行执行任意多个操作；不管并行执行了多少次操作，耗时均为 $1$ 单位时间。

给定正整数 $n$。现在 Yoimiya 希望你帮她写一段程序，使得当任意长为 $n$ 的排列作为输入时，用这台机器执行完这段程序后得到的排列均为 $1,2,\cdots ,n$。

此外，Yoimiya 还希望这段程序的耗时不能太大，具体见评分标准。