题目：[[2024.11.14 题目]] ## 邻间的骰子之舞 最初有 $1$ 个字符的文本，可以进行若干次操作，每次操作都是以下两种之一：复制所有字符到剪切板（花费 $x$）与将剪切板内的内容粘贴到文本末尾（花费 $y$）。求让文本长度大于 $N$ 所需要进行的最小花费。 --- 采用暴力与分类讨论乱搞。 对于 $x=y=1$ 的情况，我们一直复制+粘贴倍增即可，时间复杂度 $\mathcal O(\log_2 N)$，理论获得 $10$ 分，实际由于好渴鹅写挂了这一部分一分都没有。 对于 $n\le 10^3$ 的数据，采用暴力 dp。令 $dp_{i,j}$ 表示为当前文本已经有 $i$ 个字符、剪切板里面有 $j$ 个字符，达到该目标所需要花费的最小值，那么很显然初始状态 $dp_{1,1}=x$，因为最开始肯定要复制一次。 考虑如何进行转移。不难发现有两种情况：重新复制当前文本并粘贴或直接粘贴之前复制的文本，因此转移方程有 $ \begin{cases} dp_{i+j,j}=\min(dp_{i+j,j},dp_{i,j}+y) \\ dp_{i+i,i}=\min(dp_{i+i,i},dp_{i,j}+x+y) \end{cases} $ 此做法可以拿到另外 $30$ 分。好渴鹅考虑到有很多 dp 状态实际上是没有用的（即无法达到），而这些没有用的状态也不会影响后面的转移，因此可以拿一个队列只将需要转移的状态放进去，这样子可能能骗到更多分（类似于 Bellman-Ford 的队列优化 SPFA）。 但是由于好渴鹅不知道为什么最后写挂了因此本题一分都没有，柠檬熟了。 ## 星海浮沉录 有一个长度为 $n$ 的非负整数序列 $a$，第 $i$ 个数是 $a_i$。现如今给出 $q$ 个操作需要执行，每一次操作都是以下两种操作之一： - $\fbox{1~p}$：将 $a_p$ 与 $a_{p+1}$ 互换值； - $\fbox{2~x}$：求出长度不小于 $x$ 的连续子序列的最小 $\text{mex}$ 值。其中，一个序列的 $\text{mex}$ 是这个序列中不存在的最小非负整数。 对于每一个操作 $2$，输出结果。 --- 还是采用暴力。首先操作 $1$ 非常好搞，直接 swap 翻转以下两个值就行了，大部分的暴力时间复杂度瓶颈都是在查询操作而非修改操作上。 对于操作 $2$，我们首先不难想到 $\mathcal O(n^2\log_2 n)$ 的单次查询时间复杂度，也就是枚举左边界，然后准备一个装满 $0\sim n+1$ 所有元素的 set，将左边界往右 $x$ 个元素的值从 set 里面删掉，最后剩下的最少元素就是这个左边界对应的 $\text{mex}$ 值。但是这样子做总最坏时间复杂度达到了 $\mathcal O(qn^2\log_2 n)$，需要考虑优化。 不难发现从 $[l,l+x-1]$ 到 $[l+1,l+x]$ 只是多个一个元素且少了一个元素的区别，因此我们不如考虑每次将上个区间的左边界对应的值从 set 中加回来，这样或许就能优化？不完全对，因为一个区间内的单个元素可能会出现多次，如果单纯地使用 set 的话加回来的话万一后面又删掉了怎么办。 因此我们还有拿一个 [[map]] 来辅助它。map 的键值 $k$ 对应着 $k$ 被删除了多少次，删掉就加一，反之就减一。当 $k$ 的对应值 $v$ 在一次操作过后大于 $0$ 了就把这个值从 set 当中删掉；当 $v<0$， 就将这个值补回去。 这样子我们的总时间复杂度就来到了 $\mathcal O(qn\log_2 n)$，成功获得 $20$ 分。 **后记**：偶然听到另一种 set 暴力方式过了，当场气得晕厥。 ## 勾指起誓 有 $m$ 个选手参加 $n$ 场考试，每次考试都只有一道题。给出 $0/1$ 矩阵 $a$，第 $i$ 行第 $j$ 个元素表示在第 $i$ 场考试中第 $j$ 个人是是否能答对题目。 每次考试都可能会淘汰某一些人。当这次考试的所有选手不是全部都能答对或全部都不能答对，那么没有答对的人就会淘汰，剩下答对的人就会继续比赛；否则没有人被淘汰，所有人都晋级。 现在对于每一个人 $1\le i\le m$，求有多少种排列能够使得第 $i$ 个人能够成为最终的胜者（即没有被淘汰的人）。答案对 $998244353$ 取模。 --- 还是采用暴力。使用库函数 next_permutation 生成每一种可能的排列。然后再来一遍 $\mathcal O(n+m)$ 一遍求出在该种排列下获胜的人并将其统计进答案。时间复杂度 $\mathcal O(m!\times m\times (n+m))$，成功获得 $12$ 分。 ## 第八交响曲「千日同升」 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 还希望这段程序的耗时不能太大，具体见评分标准。 --- 没有完全看懂题目，没有任何头绪，代码都没有提交，文件夹都没有创建，$0$ 分。