Difference between revisions of "2018 Multi-University, Nowcoder Day 9"

From EOJ Wiki
Jump to navigation Jump to search
 
(10 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
Solved by zerol. 02:10 (+)
 
Solved by zerol. 02:10 (+)
  
题意:<del>已知 a 和 x 的 FWT 结果是 b,输入 a 和 b,求 x。</del> 求解 $Ax=b$,其中 $A_{ij}=a[i \xor j]$
+
题意:<del>已知 a 和 x 的 FWT 结果是 b,输入 a 和 b,求 x。</del> 求解 $Ax=b \pmod p$,其中 $A_{ij}=a[i \oplus j]$。(n 恰好是 2 的幂)
  
题解:
+
题解:将 A x b 都分块,A 分成 4 块,其中左上右下以及左下右上完全一样,而且四个子矩阵也有这个性质。
 +
 
 +
$\begin{pmatrix} A & B \\ B & A \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}$
 +
 
 +
$\begin{eqnarray}A x_1 + B x_2 = b_1 \\  B x_1 + A x_2 = b_2 \end{eqnarray}  $
 +
 
 +
两式相加减,得到
 +
 
 +
$\begin{eqnarray} (A+B)(x_1+x_2)=(b_1+b_2) \\ (A-B)(x_1-x_2)=(b_1-b_2) \end{eqnarray}  $
 +
 
 +
然后递归求解。
 +
 
 +
 
 +
正解 $x = fwt^{-1}(fwt(b)/fwt(a))$
  
 
== Problem C ==
 
== Problem C ==
  
Upsolved by zerol.
+
Upsolved by zerol & ultmaster.
 +
 
 +
题意:用 $2^{2n-1}$ 的钱压 2n-1 场比赛中有至少 n 场赢,赢了得到这么多钱,输了就亏这么多钱。现在只能一场一场压,要求最后能够达到相同的效果。每次先输出压的金额,然后告诉你这场的输赢,然后再决定下一场的金额(如果赢或输达到 n 场,那么立即结束,要求此时输赢的钱数恰好是 $2^{2n-1}$)。
 +
 
 +
题解:假设我有一张表 a[i][j](n=i 时,如果一直赢,第 j 场的金额),是 n<k 时如果一直赢/输时的策略。对于 n=k,考虑 赢赢赢输,我要它和 n=k-1 时的 赢赢 等效,然后按照 n=k-1 的策略执行,只是金额扩大 4 倍。这会对这张表提出一些要求,具体就是:设 s 是 a 的每行前缀和,那么要满足 s[i][j] - a[i][j + 1] = s[i][j - 1] * 4。由于知道每行的和是 $2^{2i-1}$,所以这张表能推出来,但是会超时。然后打表找规律,发现和组合数有关。
 +
 
 +
zerol: 遗憾的是根本就没有考虑 dp 或者输赢的概率。
  
 
== Problem D ==
 
== Problem D ==
Line 48: Line 67:
  
 
开始怀疑人生,刚才的 40% 呢。。。。咦?难道?AC 之后报了个警。题意遂修改。
 
开始怀疑人生,刚才的 40% 呢。。。。咦?难道?AC 之后报了个警。题意遂修改。
 +
 +
== Problem G ==
 +
 +
Upsolved by zerol.
 +
 +
题意:求四个数列的最长公共子序列。前三个数列各自满足相同的数字至多出现两次。
 +
 +
题解:把每个数字在四个数列中的位置的四元组列出来,至多 8n 个,然后就是求四维偏序的 LIS 了。
 +
 +
zerol:用 CDQ×3,CDQ×2+BIT,K-D tree (带重构/带有效标记)都能过。K-D tree 需要剪枝才能过,因为是求 max,所以能剪枝,否则如果是计数题的话就 T 了。
  
 
== Problem H ==
 
== Problem H ==

Latest revision as of 15:35, 24 August 2018

Problem A

Solved by zerol. 02:10 (+)

题意:已知 a 和 x 的 FWT 结果是 b,输入 a 和 b,求 x。 求解 $Ax=b \pmod p$,其中 $A_{ij}=a[i \oplus j]$。(n 恰好是 2 的幂)

题解:将 A x b 都分块,A 分成 4 块,其中左上右下以及左下右上完全一样,而且四个子矩阵也有这个性质。

$\begin{pmatrix} A & B \\ B & A \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}$

$\begin{eqnarray}A x_1 + B x_2 = b_1 \\ B x_1 + A x_2 = b_2 \end{eqnarray} $

两式相加减,得到

$\begin{eqnarray} (A+B)(x_1+x_2)=(b_1+b_2) \\ (A-B)(x_1-x_2)=(b_1-b_2) \end{eqnarray} $

然后递归求解。


正解 $x = fwt^{-1}(fwt(b)/fwt(a))$

Problem C

Upsolved by zerol & ultmaster.

题意:用 $2^{2n-1}$ 的钱压 2n-1 场比赛中有至少 n 场赢,赢了得到这么多钱,输了就亏这么多钱。现在只能一场一场压,要求最后能够达到相同的效果。每次先输出压的金额,然后告诉你这场的输赢,然后再决定下一场的金额(如果赢或输达到 n 场,那么立即结束,要求此时输赢的钱数恰好是 $2^{2n-1}$)。

题解:假设我有一张表 a[i][j](n=i 时,如果一直赢,第 j 场的金额),是 n<k 时如果一直赢/输时的策略。对于 n=k,考虑 赢赢赢输,我要它和 n=k-1 时的 赢赢 等效,然后按照 n=k-1 的策略执行,只是金额扩大 4 倍。这会对这张表提出一些要求,具体就是:设 s 是 a 的每行前缀和,那么要满足 s[i][j] - a[i][j + 1] = s[i][j - 1] * 4。由于知道每行的和是 $2^{2i-1}$,所以这张表能推出来,但是会超时。然后打表找规律,发现和组合数有关。

zerol: 遗憾的是根本就没有考虑 dp 或者输赢的概率。

Problem D

Upsolved by ultmaster.

题意:给一个按照某种规则生成的有关 $n,k$ 的图,求欧拉回路的总数。

题解:运用矩阵树定理和 BEST 定理求欧拉回路数量;然后解出线性递推的关系式即可。

ultmaster: 其实两步都有了,就是没搭上,遂挂机。

Problem E

Solved by kblack. 00:28 (+)

题意:连击奖励 $(Combo)^m$,每个时刻 $p_i$ 概率按对,求期望得分。

题解:$n^2$ 枚举最终连续区间,算一下对得分的期望贡献。

Problem F

Solved by ultmaster. 01:08 (+5)

题意:你在键盘上打字,偶尔还会按按退格键。每次操作之后,问你最少需要敲几次键盘,才能使得给定串中的至少一个作为你当前串的后缀出现。

题解:大概就是建个 AC 自动机,然后反向 BFS 求距离。用个栈维护一下当前状态。

一开始 BFS 写错了。WA1。

改好了 BFS。WA2。

发现其实 0 的边也要加入。遂修复。WA3。通过数据 40%。

突然发现是出现串。我的算法只能判后缀。然后改改改。WA4。40% 变成了 0%。

发现有个地方还是写错了。WA5。20%?

开始怀疑人生,刚才的 40% 呢。。。。咦?难道?AC 之后报了个警。题意遂修改。

Problem G

Upsolved by zerol.

题意:求四个数列的最长公共子序列。前三个数列各自满足相同的数字至多出现两次。

题解:把每个数字在四个数列中的位置的四元组列出来,至多 8n 个,然后就是求四维偏序的 LIS 了。

zerol:用 CDQ×3,CDQ×2+BIT,K-D tree (带重构/带有效标记)都能过。K-D tree 需要剪枝才能过,因为是求 max,所以能剪枝,否则如果是计数题的话就 T 了。

Problem H

Solved by kblack. 01:10 (+)

题意:单点加,求 n 次前缀和。

题解:结合两种暴力,贡献只与距离有关达到查询 $O(M)$ 修改 $O(1)$,暴力一次前缀和达到查询 $O(1)$ 修改 $O(kn)$选个好参数(然后数据可能比较松?)卡了过去。正确方法似乎是推广二维情况的树状数组解法,对 $0 \leq k \leq K$ 维护 $\sum_{i=1}^{x}{i^ka_i}$,然后搞一搞。