p_b_p_b的博客

博客

Public Round #3 题解

2022-04-14 13:10:01 By p_b_p_b
  • 搬题人:
    • A:hehezhou
    • B, C:p_b_p_b
  • 组题人:FSYo, p_b_p_b
  • 验题人:chenkuowen01, srf
  • 题解:chenkuowen01, hehezhou, p_b_p_b

最小生成树

题目来源:

  • 京都大学プログラミングProgramming コンテストContest 2020
  • Petrozavodsk Summer 2021 Day 1: Kyoto U Contest (KUPC 2020), Problem F

QOJ 链接:https://qoj.ac/contest/691/problem/1809

官方题解:https://qoj.ac/download.php?type=attachments&id=691&r=1

解法一

将图建出来然后使用任意最小生成树算法求解。

时间复杂度 $\Theta((H\times W)^{1+\epsilon})$,可以通过前6个测试点。

解法二

lemma 1: 一定存在一组最小生成树使得对于每个点 $P_{i,j}(i\gt 1\land j\gt 1)$ 存在和 $(i-1,j)$ 或 $(i,j-1)$ 的连边。

proof:

假设该结论不成立,那么对于所有最小生成树使得每个点 $P_{i,j}(i\gt 1\land j\gt 1)$ 都不存在这样的连边。

取其中一个点 $P_{i,j}$。

若其度数为 $1$,不妨令该边为 $(P_{i,j},P_{i+1,j})$,则删去该边后 $P_{i+1,j}$ 与 $P_{i-1,j}$ 在同一个连通块内,将该边替换为 $(P_{i-1,j},P_{i,j})$ 不劣。

若其度数为 $2$,考虑删去这两条边的连通块情况。

  • 若 $P_{i+1,j},P_{i-1,j}$ 或 $P_{i,j-1},P_{i,j+1}$ 在同一连通块内,不妨令这组为 $P_{i+1,j},P_{i-1,j}$,那么替换对应边为 $(P_{i-1,j},P_{i,j})$ 不劣。
  • 否则,$P_{i+1,j}$与$P_{i,j-1}$在同一连通块内且$P_{i,j+1}$与$P_{i-1,j}$在同一连通块内,将这两条边一并替换为$(P_{i-1,j},P_{i,j}),(P_{i,j-1},P_{i,j})$。

按上述方法调整即可找出矛盾。故假设不成立。

证毕。

lemma 2: 一定存在一组最小生成树 $T$ 使得对于任意 $1\le x\le H,1\le y\le W$,$T$ 关于点集 $\lbrace P_{i,j} | 1\le i\le x,1\le j\le y\rbrace$ 的导出子图为连通图。

proof:

假设该结论不成立,那么对于所有最小生成树都存在对应的 $x,y$ 不符合该性质。

我们取一组符合 lemma 1 的最小生成树和 $(x,y)$ 字典序最小的不符合条件的矩阵。

  • 该导出子图不连通,所以一定存在 $i$ 使得 $P_{1,i},P_{1,i+1}$ 不连通,或 $P_{i,1},P_{i+1,1}$ 不连通,不妨只考虑后者。
  • 考虑 $P_{i,1}$ 到 $P_{i+1,1}$ 在原图 $T$ 中的路径一定存在某个 $j$ 使得存在边 $(P_{i,j},P_{i+1,j})$,那么将该边替换为 $(P_{i,1},P_{i+1,1})$ 不会破坏性质且不劣。
  • 重复该方法可得到一个对于任意 $1\le x'\le x,1\le y'\le y$ 符合点集 $\lbrace P_{i,j} | 1\le i\le x',1\le j\le y'\rbrace$ 的导出子图为连通图的最小生成树。

重复该过程可发现矛盾,故假设不成立。

证毕。

根据 lemma 2,我们可以按 $i,j$ 从小到大枚举加入维护的生成树,因此答案的权值和为: $$\displaystyle\sum_{i=1}^{H-1} (A_i+B_1)+ \displaystyle\sum_{j=1}^{W-1} (C_1+D_i)+\displaystyle\sum_{i=2}^{H-1} \displaystyle\sum_{j=2}^{W-1} \min(A_{i-1}+B_j,C_i+D_{j-1})$$

其中:

$$\min(A_{i-1}+B_j,C_i+D_{j-1})=A_{i-1}+B_j+\lbrack C_i-A_{i-1}+D_j-B_{j-1}< 0 \rbrack (C_i-A_{i-1}+D_j-B_{j-1})$$

将 $i,j$ 分离后可用二分+前缀和优化,时间复杂度 $\Theta((H+W)\log (H+W))$,空间复杂度 $\Theta(H+W)$

该算法可以通过所有测试点。

猜数

题目来源:Petrozavodsk Winter 2022 Day 6: ICPC Camp Day 1, PKU Contest, Problem E

QOJ 链接:https://qoj.ac/contest/824/problem/2609

官方题解:https://qoj.ac/download.php?type=attachments&id=824&r=1

在获得足够的关于 seed 的信息之前,返回值与真实答案不怎么相关。因此我们应当考虑先求出 seed

生成一次随机数可以被拆成三步:

  1. seed*=n;
  2. seed%=P;
  3. return seed%n;

注意到,如果没有第二步,那么 seed%n 永远是 $0$ 。因此 seed%n 可以告诉我们在第二步中 seed 减掉了几个 P

由此可以获得一个暴力做法:先询问 $40$ 次 $0$ ,获得每一次的 seed%n 。然后在 $[0,P)$ 里枚举 seed ,判断结果是否符合。符合的那个 seed 就是真实的 seed 。接下来再用 $60$ 次询问来二分答案即可。

由于错误的 seed 只会期望符合前 $O(1)$ 个位置,因此这个做法的时间复杂度是 $O(P)$ 的。

(事实上,直接判断返回值是否正确即可,因此并不需要推导到这里就可以获得 $O(P)$ 的暴力做法。)

考虑如何优化。

倒着做,维护 $[l,r]$ 表示已知 seed 现在在区间 $[l,r]$ 内,每次回退一步。那么由于知道 seed%P 减掉了几个 P ,就可以知道在第二步之前的 seed 所在的区间。然后 seed*=n 反过来就可以把区间长度除掉 $n$ 。

由于 $n^{40}>P$ ,所以回退 $40$ 步足以确定起始的 seed 。然后仍然二分答案即可。

抽卡

题目来源:Petrozavodsk Winter 2022 Day 6: ICPC Camp Day 1, PKU Contest, Problem B

QOJ 链接:https://qoj.ac/contest/824/problem/2606

官方题解:https://qoj.ac/download.php?type=attachments&id=824&r=1

题解一

首先考虑计算一次合法抽卡的概率。

令 $f_{i,j}$ 表示一次 $i$ 级抽卡,合法且抽出的卡最大值不超过 $j$ 的概率,那么有:

$$f_{i,j}=f_{i-1,j}^{b_i}-f_{i-1,i-1}^{b_i}$$

后一项即为减去不合法的概率。

我们把抽卡过程看成一棵树,因为各叶子是等价的,只考虑最左侧叶子的贡献,考虑对根到最左侧的路径进行 $\text{dp}$(另一种理解是将各级抽卡的第一次抽卡设为关键抽卡)。

接下来考虑倒过来 $\text{dp}$,设 $g_{i,j}$ 表示一次合法抽卡过程中,若最左侧的 $i$ 级抽卡最大值为 $j$ ,最终 $n$ 级抽卡合法的概率,那么有:

$$g_{i,j}=g_{i+1,j}\sum_{k=0}^j s_{i,k}+\sum_{k=j+1}s_{i,k}g_{i+1,k}$$

其中 $s_{i,j}=f_{i,j}^{b_{i+1}-1}-f_{i,j-1}^{b_{i+1}-1}$,即第 $i$ 层其他抽卡最大值为 $j$ 的概率。上述式子可以分两部分前缀和优化。

总复杂度为 $O(n^2\log B)$,瓶颈在计算快速幂。

题解二

显然 $m>n$ 可以特判成 $m=n$ ,所以后面认为抽卡等级和卡等级的上限是相同的。另外,后面的 $a_i$ 也全都表示概率,即已经除掉了 $\sum_{i=0}^n a_i$ 。

使用自底向上的思考方式,把低等级抽卡逐步合并为高等级抽卡。

相应地,我们也在合并的过程中逐步确定每次抽出来的卡的等级。当我们在考虑所有 $k$ 级抽卡时,所有等级 $<k$ 的卡已经确定了,而等级 $\ge k$ 的卡的等级则未定。

那么可以设 $$ f_k(x)=\sum_{s\in S_k} p(s)x^{cnt_{\ge k}(s)} $$ 其中 $S_k$ 表示当所有等级 $\ge k$ 的卡被视为同一类时,合法的 $k$ 级抽卡的集合;$p(s)$ 表示等级 $<k$ 的卡的出现概率的乘积;$cnt_{\ge k}(s)$ 表示等级 $\ge k$ 的卡的个数。

转移式非常简单: $$ f_0(x)=x\\ f_k(x)=f_{k-1}^{b_k}(x+a_{k-1})-f_{k-1}^{b_k}(a_{k-1}) $$ 并且容易发现 $f_n(a_n)$ 就是一个 $n$ 级抽卡合法的概率,$a_nf'_n(a_n)$ 就是 $p_n\cdot q$ 。

如何求出这两个点值呢?从转移式可以注意到,为了求出这两个点值,对于所有的 $f_k(x)$ ,$x$ 只可能是从 $k$ 开始的若干个 $a_i$ 之和!

因此,可以设 $dp1_{k,r}=f_k(\sum_{i=k}^r a_i),dp2_{k,r}=f_k'(\sum_{i=k}^r a_i)$ ,然后使用转移式转移即可。

接下来考虑求出所有的 $p_k\cdot q$ 。

受到 $a_nf'_n(a_n)$ 的启发,可以想到用第二个变量来记录等级为 $k$ 的卡的数量,然后同样用求导的方式求出 $p_k\cdot q$ 。于是可以引入二元生成函数 $g(x,y)$ : $$ g_0(x,y)=x\\ g_k(x,y)=\begin{cases} g^{b_k}_{k-1}(x+y,y)-g^{b_k}_{k-1}(y,y)&k=T\\ g^{b_k}_{k-1}(x+a_{k-1},y)-g^{b_k}_{k-1}(a_{k-1},y)&k\ne T \end{cases} $$ 其中 $T$ 表示现在要求 $p_T\cdot q$ 。

那么设 $h_k(x,y)=\frac{\partial}{\partial y}g_k(x,y)$ ,就有 $p_T\cdot q=a_T h_n(a_n,a_T)$ 。

容易发现 $g,h$ 也有与 $f$ 类似的性质,即 $x$ 只可能代入 $\sum_{i=k}^r a_i$ ,因此也可以用类似的 DP 求出所有点值。这样就获得了一个 $O(n^3\log b)$ 的做法。

为了优化,注意到我们总是有 $g_k(\sum_{i=k}^r a_i,a_T)=f_k(\sum_{i=k}^r a_i)$ ,只有 $h$ 不确定,而且在 $g$ 已知时 $h$ 的转移是线性关系。因此可以设 $dp3_{k,r}$ 表示 $h_k(\sum_{i=k}^r a_i,a_T)$ 的贡献系数,而这个贡献系数与 $T$ 无关。这样倒着把 $dp3$ 递推出来之后就可以直接得到答案了。

所以最终复杂度 $O(n^2\log b)$ 。

评论

暂无评论

发表评论

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