11 2024.5.19
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(0\) | \(30\) | \(100\) | \(10\) | \(140\) |
排名：rank \(5\)。
2 题解
T1
其实 T1 是本场考试最难的题，因此放到后面讲。
T2
70 pts：
瞄准部分分，我们发现 \(n\le 15\)，于是自然想到状压。考虑记录下当前选了的数字，于是定义状态为 \(dp(i,j,S)\) 为枚举到第 \(i\) 位，当前位上放 \(a_j\)，同时总共放了的学生集合为 \(S\) 的状态数。
于是可以自然得到转移方程：
\[dp(i,j,S)=\sum dp(i-1,k,S') \]在合法的条件下直接转移即可，这一部分并不难想到。
100pts：
考虑到题目中有模 \(m\) 的限制，因此我们可以套路的想到将每个数模 \(m\) 处理。
在模完 \(m\) 之后，我们发现，只有余数相同的数才不能放在一起，其他可以随意放置。同时，如果合法，那么将余数相同的数调换仍然合法。于是我们此时只需要考虑余数即可，余数相同的数我们计算阶乘即可。
考虑爆搜，我们现在只需要考虑 \(m\) 个余数。但是此时我们的复杂度仍然高达 \(O(n^m)\)，并无太大优化。我们此时希望剪枝，而剪枝中较为有效的方法就是记忆化，这时候我们用一种比较骚的处理方式：对于当前剩下的余数，我们将每一种余数的剩余数量看成一个序列，对这个序列进行哈希，以此进行记忆化。
现在我们提交，发现可以得到 \(80\) pts 的好成绩。那么剩下的问题出在哪里呢？
考虑我们的记忆化。实质上，我们关注的不是原序列的数，甚至也不应该是余数，而是每一种余数出现的次数。例如在 \(m=10\) 时，余数序列 \(3\ 4\ 4\) 和 \(3\ 5\ 5\) 并没有任何本质上的差别。因此，我们实际上处理的序列是，对于 \(i=1,2,\cdots,n\)，有多少种余数出现次数为 \(i\)。对这个序列进行哈希就是真正的记忆化。
T3
全场最简单的题。
这道题本质上只要你能做出关键的 \(10\) 分的数据，应该就能做出整道题。那我们先看这关键的 \(10\) 分，就是 \(l=1\) 这个性质。
经过手玩以及推理，我们发现再这样一条性质：对于 \(l=1\) 的任意一个序列，\(1\) 在哪个位置，它的下标就是 \(t(x)\)。原因很简单：如果不选 \(1\)，那么整个序列无法结束；一旦选了 \(1\)，后面的所有数都会被选。
于是我们可以来看整道题，仿照上面的思路，我们可以求出整个序列中某些关键的数。如果不选这些关键的数，整个序列无法结束；而一旦全部选完，后面的所有数都会被选。显然这些数只需要满足在序列中没有因数即可（我们可以叫它们是这个序列的 “质数”，因此求法就是用简单的埃筛即可），设这些数总共有 \(cnt\) 个。
那么我们只需要关注这些关键数中的最后一个在什么位置。显然可以枚举这个位置 \(i\)，那么在 \(i\) 之前必须要放下剩余全部 \(cnt-1\) 个关键数，那么方案书就有 \(A_{i-1}^{cnt-1}\) 种；剩余的 \(n-cnt\) 个数可以随意排列，方案数有 \((n-cnt)!\) 种；最后当前这个位置放哪一个关键数也不确定，因此还有 \(cnt\) 种。最后再乘上 \(i\) 的贡献，于是答案就是：
\[\sum\limits_{i=cnt}^n A_{i-1}^{cnt-1}\times (n-cnt)!\times cnt\times i \]直接计算即可。
T4
本场最难的题。
首先我们在题目中可以发现这样一个神奇的性质：\(\sum\limits_{i=1}^n\sum\limits_{j=1}^np_{i,j}=n^2\)，这就意味着 \(p_{i,j}\) 一定等于 \(1\)，也就是每次魔法必定生效。那此时让我们再审视一下这道题，不难发现，这道题与 T1 一模一样，毫无差别。
现在我们开始正式做这个题。首先这道题我们最后变成哪种颜色不确定，因此需要枚举是哪种颜色。又由于求的是期望步数，因此对于每一种颜色我们都要求出是他的概率以及他转移的期望步数。那我们一个一个看。
我们发现这道题与颜色本身并没有太大关系，我们只需要考虑颜色数量即可。设 \(p_i\) 表示一种颜色有 \(i\) 个时，最后序列全部变成该种颜色的概率。那么我们得到，总共选的数量有 \(n(n-1)\) 种，而造成 \(i\) 变化的有 \(2i(n-i)\) 种，其中 \(i(n-i)\) 种是该种颜色变成其他颜色，\(i(n-i)\) 种是其他颜色变成该种该种颜色；当然剩下的情况就是无法转移。于是我们可以得到方程：
\[p_i=\frac{i(n-i)}{n(n-1)}p_{i-1}+\frac{i(n-i)}{n(n-1)}p_{i+1}+(1-\frac{2i(n-i)}{n(n-1)}p_i) \]现在我们对这个式子进行化简可得：
\[2p_i=p_{i-1}+p_{i+1}\\ p_i-p_{i-1}=p_{i+1}-p_i \]于是显然 \(p_i\) 构成了一个等差数列。根据定义我们有 \(p_0=0,p_n=1\)，于是可以得到 \(p_i\) 的通项公式为 \(\dfrac in\)。
接下来我们来看期望步数。设 \(dp_i\) 表示该种颜色有 \(i\) 个时，最后序列全部变成这种颜色的期望步数。注意这个期望步数实在序列变成这种颜色的前提下发生的，也就是我们要关注的实质上是 \(p_idp_i\)。考虑到 \(dp_i\) 的处理并不方便，我们可以直接列出 \(p_idp_i\) 的式子：
\[p_idp_i=\frac 12p_{i-1}dp_{i-1}+\frac 12p_{i+1}dp_{i+1}+p_i\times\frac{n(n-1)}{2i(n-i)} \]我们解释一下这个式子。首先我们知道从当前颜色改变的概率是 \(\dfrac{2i(n-i)}{n(n-1)}\)，那么转移的期望步数自然是它的倒数，同时还需要满足序列是由这种颜色变成的，于是还要乘上概率 \(p_i\)。接下来是前面的期望步数，以 \(i-1\) 为例，首先 \(i\) 从 \(i-1\) 或 \(i+1\) 转移的概率相同，因此要乘 \(\dfrac 12\)。接下来我们要求期望，但是依然都得先满足序列是由这种颜色变成的，于是还要乘上对应概率 \(p_{i-1}\)。
那么现在我们换元，令 \(f_i=p_idp_i\)，由上式可以得到：
\[f_i=\frac 12 (f_{i-1}+f_{i+1})+\frac{n(n-1)}{2i(n-i)}p_i\\ 2f_i=f_{i-1}+f_{i+1}+\frac{2n(n-1)}{2i(n-i)}\times \frac in\\ f_{i+1}-f_i=f_i-f_{i-1}-\frac{n-1}{n-i} \]我们得到了一个与 \(p_i\) 很像的递推公式，那么考虑求出通项。由于 \(p_0=0,dp_n=0\)，于是 \(f_0=f_n=0\)。现在如果要求出通项或者递推，还差一项，要么求出 \(f_1\)，要么求出 \(f_{n-1}\)。
现在继续换元，设 \(g_i=\dfrac{n-1}{n-i},d_i=f_{i+1}-f_i\)。那么由上式可得 \(d_{i}=d_{i-1}-g_i\)。同时我们又可以显然发现 \(f_{i+1}=d_i+f_i\)。那么这两个式子就都是显然的数列递推公式，我们可以得到：
\[\begin{aligned} f_{i+1}&=d_i+f_i\\ &=d_i+d_{i-1}+f_{i-1}\\ &=\cdots\\ &=d_i+d_{i-1}+\cdots+d_0+f_0\\ \\ d_i&=d_{i-1}-g_i\\ &=d_{i-1}-g_{i-1}-g_i\\ &=\cdots\\ &=d_0-g_0-g_1-\cdots-g_i \end{aligned} \]现在我们把下面的 \(d_i\) 再带回上面的式子中，可以得到：
\[\begin{aligned} f_{i+1}&=d_i+d_{i-1}+\cdots+d_0+f_0\\ &=(d_0-g_0-g_1-\cdots-g_i)+(d_0-g_0-g_1-\cdots-g_{i-1})+\cdots+d_0-g_0+d_0+f_0\\ &=(i+1)d_0-ig_0-(i-1)g_1\cdots+g_i+f_0 \end{aligned} \]那么由于 \(f_0=0\)，于是 \(d_0=f_1\)。将两者和 \(g_i\) 都带回上式得：
\[\begin{aligned} f_{i+1}&=(i+1)d_0-ig_0-(i-1)g_1\cdots+g_i+f_0\\ &=(i+1)f_1-ig_0-(i-1)g_1\cdots+g_i\\ &=(i+1)f_1-i\frac{n-1}{n-1}-(i-1)\frac{n-1}{n-2}+\cdots+\frac{n-1}{n-i} \end{aligned} \]现在将 \(i+1\) 换成 \(i\) 可得：
\[\begin{aligned} f_{i}&=if_1-(i-1)\frac{n-1}{n-1}-(i-2)\frac{n-1}{n-2}+\cdots+\frac{n-1}{n-i+1}\\ &=if_1+(n-1)(\frac{i-1}{n-1}+\frac{i-2}{n-2}+\cdots+\frac{i-i+1}{n-i+1}) \end{aligned} \]发现此时后面括号内式子形式很好，\(i\) 与 \(n\) 同步，那我们就可以直接令 \(i=n\)，得：
\[\begin{aligned} f_{n}&=nf_1+(n-1)(\frac{n-1}{n-1}+\frac{n-2}{n-2}+\cdots+\frac{n-n+1}{n-n+1})\\ &=nf_1+(n-1)(n-1) \end{aligned} \]由于 \(f_n=0\)，便可以求出：
\[nf_1+(n-1)^2=0\\ f_1=\frac{(n-1)^2}{n} \]现在我们终于可以直接递推整个 \(f\) 数列了！最后直接累加答案即可。
12 2024.6.2
1 得分
| 题目 | T1 | T2 | T3 | T4 | 总分 |
|---|---|---|---|---|---|
| 得分 | \(0\) | \(70\) | \(10\) | \(49\) | \(129\) |
排名：rank \(6\)。
2 题解
T1
最简单的题目。观察到 \(n\) 并不是很大，并且题目只要求出现长度为 \(3\) 的等差数列，所以我们可以考虑枚举第一个数字以及公差。维护一个桶，储存每个数字出现的位置，通过首项和公差计算然后通过桶来判断即可。
这样做复杂度为 \(O(Tn^2)\)，常数较小可以卡过去。
T2
首先这道题分为两部分，也就是每个男生被一个女生选到的概率，还有就是出现逆序对的期望个数。
先看第一部分。
考虑对于第 \(i\) 个女性，假设它的列表中有 \(s_i\) 个男性。现在看第 \(j\) 个男性被选到的概率，如果在第一轮就被选上，那么概率是 \((1-p)^{j-1}p\)；如果第二轮才被选到概率为 \((1-p)^{s_i+j-1}p\)；第三轮被选到概率为 \((1-p)^{2s_i+j-1}p\)……
不难发现，每一轮选中第 \(j\) 个男生的概率构成了一个公比为 \((1-p)^{s_i}\) 的等比数列。于是我们利用等比数列求和可以得到对于第 \(i\) 个女性，选到第 \(j\) 个男性的概率是：
\[P(i,j)=\frac{(1-p)^{j-1}p}{1-(1-p)^{s_i}} \]接下来看第二部分。
首先明确一点，由于逆序对的贡献始终为 \(1\)，因此期望就等于概率。所以我们只需要求出出现逆序对的概率即可。
我们考虑第 \(i\) 个女性的第 \(j\) 个男生，编号为 \(p_{i,j}\)，只要在 \(i\) 之前的女性有比 \(p_{i,j}\) 编号大的男生，就有可能出现逆序对。将出现这些男生的概率求和，再乘上 \(P(i,j)\) 就是当前出现一个逆序对的概率。所以我们可以得到如下式子：
\[E(i,j)=P'(i,j)=\sum_{k=1}^{i-1}(\sum_{p_{k,l}>p_{i,j}} P(k,l))\times P(i,j) \]此时暴力求这个式子的时间复杂度是 \(O(nm^2)\) 的，显然无法通过。
容易发现，如果我们将女生编号看作 \(x_i\)，男生编号看作 \(y_i\)。现在对于一个点，只需要求出所有 \(x_j<x_i\) 且 \(y_j>y_i\) 的点的概率之和，然后乘上这个点的概率即可。不难发现这就是一个二维偏序，用树状数组直接简单维护即可。时间复杂度降为 \(O(m\log n)\)，可以通过。
T3
首先容易想到，对于这样的题目，通常考虑区间 dp。那么这道题同样如此。
考虑分析题目条件，不难发现，所有合法的超级括号序列的两边应该都是括号。同时我们可以将所有超级括号序列分成两部分：
- 定义的 \(1,3\) 条可以归为一类，这一类序列两边的括号是互相匹配的。
- 定义的第 \(2\) 条可以归为一类，这一类序列两边的括号是和中间的括号匹配的。
显然两类的计算方法不同，所以要分开求解。设 \(f(i,j)\) 表示区间 \([i,j]\) 为第一类合法序列的方案数，\(g(i,j)\) 表示区间 \([i,j]\) 为第二类合法序列的方案数。
首先来看第一类的求解。还是需要进一步分类讨论。
注意下面讨论的基础都是 \(s_i\) 和 \(s_j\) 能够成为匹配的括号。
()型
显然，如果满足 \(i\) 和 \(i+1\) 能够成为匹配的括号（注意类似 (? 也算），则 \(f(i,i+1)=1\)。
(S)型
为了满足这里以及后面判断 S 型字符串的需要，定义 \(p(i,j)\) 表示区间 \([i,j]\) 是否可以全部都是 * 且长度是否不超过 \(k\) 的字符串。显然 \(p(i,j)=1\) 时就代表 \([i,j]\) 是一个 S 型串。
现在这一型字符串对应的转移方程就很简单了：
\[f(i,j)+=p(i+1,j-1) \]至于如何求 \(p(i,j)\)，暴力 \(O(n^2)\) 枚举即可。
(A)型
这一部分也很简单，直接给出方程：
\[f(i,j)+=f(i+1,j-1)+g(i+1,j-1) \](SA)和(AS)型
我们直接枚举断点，然后判断即可。两者的方程分别为：
\[f(i,j)+=\sum_{k=i+1}^{j-2}(f(k+1,j-1)+g(k+1,j-1))\times p(i+1,k)\\ f(i,j)+=\sum_{k=i+1}^{j-2}(f(i+1,k)+g(i+1,k))\times p(k+1,j-1) \]显然这些方程的转移复杂度都是 \(O(n^2)\) 或 \(O(n^3)\)，可以接受。
下面看第二类的求解。
其实第二类的转移方程只有一个，因为我们可以将 AB 型看成是 S 串长度为 \(0\) 的 ASB 型。枚举两个断点，转移方程如下：
但是这一类的求解难度并不在转移方程上。我们发现，这个方程的转移复杂度是 \(O(n^4)\)，需要优化。我们会发现后面一部分 \(f(l,j)\times p(k+1,l-1)\) 只有三个参数，于是自然想到预处理。定义一个 \(sg(i,j)\)，式子如下：
\[sg(i,j)=\sum_{k=i+1}^jf(l,j)\times p(i+1,k-1) \]我们在 dp 过程中一边求 \(f,g\)，一边求出 \(sg\) 数组，然后利用它优化上面的转移方程，最后方程为：
\[g(i,j)+=\sum_{k=i}^{j-1}(f(i,k)+g(i,k))\times sg(k,j) \]发现此时两个数组的求解都是 \(O(n^3)\) 的了。
所以整道题的转移复杂度现在都在 \(O(n^3)\) 以下，复杂度 \(O(n^3)\)，可以通过。
T4
首先我们会想到这样一个显然的 dp：设 \(dp(i,0/1)\) 表示在第 \(i\) 层上，从左 / 右端点落下后，走到原点的最短路径。
那么我们以 \(dp(i,0)\) 举例。假如从第 \(i\) 层的左端点落下，掉到第 \(j\) 层上，那么转移方程就是：
\[dp(i,0)=\min\{dp(j,0)+|l_i-l_j|,dp(j,1)+|l_i,r_j|\} \]容易发现，如果我们构造一个线段构成倒金字塔的数据，那么这个方程就会被卡到 \(O(n^2)\)，无法通过。
考虑瓶颈其实是在求出从第 \(i\) 层掉下落在那一层上。考虑到我们每一个线段都会覆盖掉之前出现的线段，因此如果我们将 \(x\) 轴单独拿出来，就可以认为这是一个线段覆盖的问题，而我们要求的其实就是一个下标对应的线段编号。
整理上面的操作可以看出，我们实际上只需要维护区间覆盖、单点查询。显然使用线段树优化即可。
时间复杂度为 \(O(n\log (B_i-A_i))\)。
3 挂分
- T1 全部爆炸，\(100\to 0\)。
- T2 树状数组做法写炸，\(100\to 70\)。