Diary / Solution Set -「WC 2022」线上冬眠做噩梦

??大概只有比较有意思又不过分超出能力范围的题叭。

??可是兔子的“能力范围” $=\varnothing$ qwq。

「CF 1267G」Game Relics

??任意一个状态可以描述为 $(m,s)$，表示剩下 $m$ 个·总价值为 $s$ 的物品未选。若当前决策为 X 操作，那么由于决策的确定性，我们必然不停 X 直到出货。所以代价为

\[\frac{x}{2}\left(\frac{n}{m}+1\right), \]

若当前决策为 C 操作，代价则为 $\frac{s}{m}$。

??同时注意到，两种操作对已有卡牌集合的影响都是：随机获得一张卡。所以相同大小的卡牌集合被抽到的概率是相同的。设 $c(m,s)$ 表示满足该状态的卡牌集数量，$w(m,s)=\min\left\{\frac{x}{2}\left(\frac{2n}{n-m}+1\right),\frac{s}{m}\right\}$ 表示状态的转移代价，那么答案 $\mathcal R$ 满足

\[\mathcal R=\sum_m\sum_s \frac{c(m,s)}{\binom{n}{m}}w(m,s). \]

??DP 计算 $c(m,s)/\binom{n}{m}$ 即可，复杂度 $\mathcal O(n^2m)$。

「CF 1510I」Is It Rated?

??~~离离原上谱了属于是。~~一个自然的想法是跟着当前的大佬猜，但如果两个人的对错情况是

TFTFTFTF...
FTFTFTFT...

我们就很容易比乱猜更摆烂。那么另一个自然的想法是设计一个关于正确数量/错误数量/正确率的权重函数，这里以错误数量为例，对于错了 $x$ 个人给出的答案，视为给这一答案投出 $w(x)$ 张票，最终我们以正比于票数的概率选取答案。经尝试令 $w(x)=127\cdot 1.0712^{-x}$ 可过，我有空一定证明正确性。（

「Gym 102483D」Date Pickup

??注意题意：Richard 可以在自己家里停留任意时刻再出发，出发后才不允许停留。

??问题比较复杂，答案具有单调性，可以先尝试二分答案 $W$ 强化约束条件。Richard 受到的约束大体分为两类：在 $A$ 时刻之前，他得保证可以在 $A+W$ 时刻或之前冲到 $n$；在 $[A,B]$ 时刻内，他得随时 on call，即前脚刚踏上一条边时接到电话，在 $W$ 时间内冲到 $n$。

??对于第一类约束，满足条件的点集为 $V'=\{u\in V\mid \operatorname{dist}(1,u)+\operatorname{dist}(u,n)\le A+W\}$；对于第二类约束，满足条件的边集为 $E'=\{\lang u,v\rang\in E\mid w\lang u,v\rang+\operatorname{dist}(v,n)\le W\}$。我们利用这两个集合等价地描述 Richard 的行动：

首先，通过最短路走到某个 $u\in S$；
若在 $u$ 有“绝对空余时间”，即 $\operatorname{dist}(1,u)+\operatorname{dist}(u,n)，就地睡觉（等价于先在家里睡觉，然后走到 \(u$）；
进入 $[A,B]$ 阶段，仅能通过 $E'$ 内的边游走。若不得不走不在 $E'$ 内的边，Janet 立马打电话，Richard 就失去了爱情；否则若 Richard 坚持到 $B$ 时刻，Janet 不得不打电话，Richard 完美到达。

??可见，设 $f(u)$ 表示从 $u$ 开始沿 $E'$ 游走的最长距离，Richard 保持成功的等价条件是存在一个 $u\in V'$，使得 $f(u)+A+W-\operatorname{dist}(1,u)-\operatorname{dist}(u,n)\ge B$。当然若存在环，$f(u)\rightarrow +\infty$ 自然合法；否则可以在 DAG 上 DP。瓶颈在于最短路 $\mathcal O(m\log m)$ 的 Dijkstra。

??注意一个坑点，答案上界是 $\operatorname{dist}(1,n)$，但当 $W=\operatorname{dist}(1,n)$，至少说，我的实现无法正确判断出“$W$ 可行”。原因在于此时“Richard 一直留在家里等电话”无法被等价模型描述。而我们可以通过加一条边 $\lang 1,1,0\rang$ 来很好地描述这一行动，这条边会在 $W=\operatorname{dist}(1,n)$ 时成为 $E'$ 中的环，保证了正确性。

「UOJ #592」新年的聚会

??自然地尝试寻找分治的可能。可以注意到：对于独立集 $A,B$，我们可以将 $A,B$ 分别拆成两个等大的集合，然后分治处理，最终询问得到 $A,B$ 间的连边。进而，联想到关于独立集划分的结论：图 $G=(V,E)$ 可以被划分为 $\mathcal O(\sqrt{|E|})$ 个独立集。

证明

??对于结点 $u\in V$，若其度数 $d_u\ge\sqrt{|E|}$，我们将其单独作为独立集；否则，在图上任意顺序遍历结点，定义结点的颜色为其邻接有色结点的颜色的 $\operatorname{mex}$，显然颜色编号 $\le d_u\l\sqrt{|E|}$，依据颜色划分独立集，最终得到不超过 $2\sqrt{|E|}$。?$\square$

??因此，考虑对原问题的分治：先将点集分为两份，求解各自诱导子图内的边并划分独立集，然后独立集两两进行处理。复杂度据说是 $\mathcal O(m\log n)$ 次询问，$\mathcal O(n\sqrt m)$ 的点集大小。此处没有细究。

「UER #9」「UOJ #604」赶路

??巧妙的分治做法：设 $\operatorname{solve}(S)$ 表示规划从 $S_1$ 出发，任意顺序经过 $S_{2..|S|-1}$，最终到达 $S_{|S|}$ 的合法路线，保证路线在 $S$ 的凸包内。在 $S_{2..|S|-1}$ 里随机一个中间点 $P$，按与 $\vec{S_0P}$ 的顺逆时针关系将 $S$ 划分为 $S_a$ 和 $S_b$ 递归处理，可见 $S_a$ 与 $S_b$ 的方案互不影响。复杂度为

\[\begin{aligned} T(n) &= \mathcal O(n)+\frac{1}{n-1}\sum_{k=1}^{n-1}(T(k)+T(n-k))\\ &= n\left(\sum_{k=2}^n\left(1-\frac{\binom{k-1}{2}}{\binom{k}{2}}\right)\right)\\ &= \mathcal O(n\ln n). \end{aligned} \]

「CF 566C」Logistical Questions

??设当前站在 $u$ 点，答案为 $f(u)$，不妨以 $u$ 为根，考虑让 $u$ 沿着 $(u,v)$ 走一个 $\text dx$，那么 $\text df=\frac{3}{2}\sum_{w\in\operatorname{subtree}(v)}\sqrt{\operatorname{dist}(u,w)}-\frac{3}{2}\sum_{w\not\in\operatorname{subtree}(v)}\sqrt{\operatorname{dist}(u,w)}$。显然最多一个 $v$ 使得 $\text df>0$，此时答案要不是 $u$，要不就在 $v$ 子树内。点分求解即可。复杂度 $\mathcal O(n\log n)$。

「CF 1083C」Max Mex

??询问可以转化为“求 $0..k$ 对应的点是否能被包含在一条树链里”，建关于点权的线段树维护这一信息即可。弄个 $\mathcal O(1)$ LCA 可以做到 $\mathcal O(n)/\mathcal O(n\log n)-\mathcal O(\log n)$，树链合并的细节的确很细节 qwq。

「Gym 102979K」Knowledge Is...

??照着 qls 的课件写？没想到吧，这个得反悔贪心。

「ICPC 2021 Nanjing」Secret of Tianqiu Valley (private link)

??不难求出 $\{x_n\}\in\{0,1\}^n$，表示位置 $i=0..n-1$ 需要被操作奇数次还是偶数次。接下来根据 $\{x_n\}$ 和 $\{s_n\}$ 构造方案。对于还需要被操作的 $(x_i,s_i)=(1,0)/(1,1)$，讨论：

$(x_i,s_i)=(1,0)$，这是最理想的情况，一步操作即可变成 $(0,1)$。
$(x_i,s_i)=(1,1)$，我们可以先处理完前一种情况，此时能操作的位置一定是 $(0,0)$，显然有一个 $(1,1)$ 与它相邻，继而，还有一个 $(1,1)$ 与这个 $(1,1)$ 相邻，这样才能保证 $\{x_n\}$ 是可行的。所以现在有形如

$x$ $0$ $1$ $1$

$s$ $0$ $1$ $1$

的情况，以此操作第 $1,2,1,3$ 个位置即可消掉两个 $(1,1)$，因此最坏 $2n$ 次完成操作。

\(x\)	\(0\)	\(1\)	\(1\)
\(s\)	\(0\)	\(1\)	\(1\)

「PA 2021 Round 1」Od deski do deski (private link)

??通过合法性判断方法设计 DP 状态。

??对于已知序列，可用 DP $f(i)=[\exist~j 来判合法，在计数的角度看，对于当前的 \(i$，我们只关心有多少中颜色 $c$ 满足 $\exist~j。因此，定义状态 \(f(i,j,0/1)$ 表示前 $i$ 个位置，有 $j$ 个符合条件的 $c$，当前序列不合法 / 合法的方案数。转移不难。

「CCO 2018 Day2」「LOJ #3519」Flop Sorting

??按照一贯套路，将问题简化为将两个排列分别排序。枚举已知排序算法，这里“不妨”先考虑归并，我们面临的问题是：合并两个升序的序列 $A,B$。首先如同归并的双指针，我们找到 $A$ 的一段后缀 $A[p:]$ 以及 $B$ 的一段前缀 $B[:q]$，满足 $A[p:]$ 排序后在 $B$ 序列上（下标 $>|A|$），$B[:q]$ 同理。依次翻转 $A[p:],B[:q],A[p:]+B[:q]$，即可归纳到合并 $(A[:p-1],A[p:])$ 以及 $(B[:q],B[q+1:])$ 的子问题。

??记归并两个长度为 $n,m$ 的序列的复杂度为 $f(n,m)$，总复杂度即为 $T(n)=2T(n/2)+f(n/2,n/2)$。如果把 $f$ 抽象成 $f(n,m)=\max_a\{\mathcal O(a)+f(n-a,a)+f(a,m-a)\}$ 的话，打表出来 $f(n,n)$ “长得像” $\mathcal O(n\ln n)$，那么总复杂度是 $\mathcal O(n\log^2n)$？这里存疑，求巨巨教导 qwq。

「AGC 056E」Cheese

??邓老师的做法我脑补出来大概 $\mathcal O(n^4)$？实在写不下去了搞了个 $\mathcal O(n^5)$ 的屑 qwq。

??奶酪顺序不重要，奶酪转圈圈不太重要，甚至……奶酪跑来跑去实在是灵异。我们现在钦定没有奶酪转了完整的圈圈，并考虑 $n-1$ 对“奶酪-老鼠”的匹配，也就是说，$n-1$ 块奶酪在圆上画出了 $n-1$ 段圆弧。现只计算第 $n-1$ 只老鼠没吃到奶酪的概率 $\mathcal R$，枚举经过了 $-0.1$ 位置的圆弧数量 $x$，以及初始时每条弧放上有多少奶酪弧的起始点 $\lang c_n\rang$，有

\[\mathcal R=\frac{1}{2}\sum_{x\ge 0}\sum_{\lang c_n\rang,\sum c=n-1}\left[\binom{n-1}{c_0,c_1,\cdots,c_{n-1}}\prod_{i=0}^{n-1}p_i^{c_i}\right]\left[2^{-x}\prod_{i=0}^{n-2}\left(1-2^{i-x-\sum_{j\le i}c_j}\right)\right]. \]

其中系数 $\frac{1}{2}$ 是因为奶酪可以疯狂转圈圈再被吃掉，算重了 $1+\frac{1}{2}+\frac{1}{4}+\cdots=2$ 次。无穷级数不好弄，我们尝试整理式子，令 $z=2^{-x}$，整理 $\sum_{x\ge 0}$ 后面的式子：

\[f(z)=\sum_{\lang c_n\rang,\sum c=n-1}\left[\binom{n-1}{c_0,c_1,\cdots,c_{n-1}}\prod_{i=0}^{n-1}p_i^{c_i}\right]\left[z\prod_{i=0}^{n-2}\left(1-2^{i-\sum_{j\le i}c_j}z\right)\right]. \]

那么

\[\mathcal R=\sum_{i=0}^n[z^i]f\cdot\sum_{x\ge 0}(2^{-x})^i. \]

后面就等比数列求和啦。算一次 $\mathcal O(n^4)$，所以算出 $n$ 个答案的复杂度是 $\mathcal O(n^5)$。

「AGC 044E」Random Pawn

??令 $f(i)$ 为从 $i$ 出发的期望最优收益，$f(k)=f(k\bmod n)$，显然

\[f(i)=\max\left\{a_i,\frac{f(i-1)+f(i+1)}{2}-b_i\right\}. \]

取到最大 $a_i$ 的位置有 $f(i)=a_i$，我们把它转到 $f(0)$，破环成链。接下来，联想到 $f(i)=\max\left\{a_i,\frac{f(i-1)+f(i+1)}{2}\right\}$ 所描述的上凸壳形式，配凑常数列 $\lang d_n\rang$，令

\[f'(i)=f(i)-d_i=\max\left\{a_i,\frac{f'(i-1)+f'(i+1)}{2}\right\}-d_i. \]

那么 $d_{i-1}+d_{i+1}=2b_i$。可以令 $d_0=d_1=0,~d_i=2(d_{i-1}-b_{i-1})-d_{i-2}~(i\in(1,n])$。此后，单调栈求出点集 $(i,a_i-d_i)$ 的上凸壳，计算 $x=0..n-1$ 的纵坐标之和的平均数即为答案。复杂度 $\mathcal O(n)$。注意尽量采用整数运算减少浮点误差。

「LOCAL」Stars (private link)

??当邓老师用锦囊这个意象去描绘 DP 的时候，他是这个世界上最伟大的诗人。??—— 毕飞宇《我读<时间简史>》（大雾

??还是通过合法性判断的方法设计 DP 状态，这道题真的神仙。

??如何判断一个序列是否奇妙呢？注意到 $k$ 很小，可以暴力一点——枚举一个锦囊序列 $S$，$S$ 是 $0..m-1$ 的排列。初始时，令奇妙整点 $P=(-1,-1,\cdots,-1)$，依次扫描序列。当 $P$ 与扫描到的整点 $A_i$ 失配时，依次打开锦囊，不妨设当前打开了锦囊 $S_k$，那么令 $P^{(S_k)}\leftarrow A_i^{(S_k)}$，可见 $P$ 能与 $A_i$ 匹配了，继续扫描。若不存在锦囊序列使 $P$ 完成匹配，则显然原序列不奇妙。换句话说：原序列奇妙，等价于存在这样一个锦囊序列。

??受此启发，设计 DP 状态：令 $f(i,S)$ 表示考虑从 $A_i$ 出发开始匹配，锦囊序列为 $S$ 时，锦囊序列非空前缀决定出的 $P$ 的失配位置序列。（注意 $A$ 下标从 $1$ 开始，$S$ 下标从 $0$ 开始。）

一个栗子 awa

??若 $A=\lang (1,1,4),(5,1,4),(1,9,1),(9,8,1),(0,0,0)\rang$，$S=\lang 0,1,2\rang$，那么 $f(1,S)=\lang 2,4,5\rang$，失配时对应的 $P$ 分别为 $(1,-1,-1),(1,1,-1)$ 和 $(1,1,1)$。

??考虑转移，对于 $f(i,S)$，我们出门必用锦囊 $S_0$，而我们希望找到一个与 $f(i,S)$ “相似”的 $f(i+1,S')$。可以先把 $S_0$ 丢到最后得到 $T$，考虑 $f(i+1,T)$ 中，可能存在一个失配位置 $p$，满足 $A_i^{(S_0)}=A_p^{(S_0)}$，可以发现，如果把 $p$ 失配后使用的锦囊替换为 $S_0$，那么 $p$ 失配后，两个锦囊对应的 $P$ 变得一样了，失配位置自然也是一样的，这样就能完成转移。如果不存在这样的 $p$，就先将就着用 $f(i+1,T)$，但是删掉最后一个失配位置（$S_0$ 重复使用没有意义）。

??最后，$r_i=\max_S\{f(i,S)_{m-1}\}$ 即为 $i$ 开始最远端的奇妙序列右端点。复杂度 $\mathcal O(nk!k)$。

「PA 2021 Round 2」Poborcy podatkowi (private link)

??令 $f(u,i\in\{0,1,2,3\})$ 表示 $u$ 下挂了长度为 $i$ 的链时，$u$ 子树内部的最大和。合并时，$f(v,0)$ 和 $f(v,2)$ 可以匹配，$f(v,1)$ 和 $f(w,1)$ 可以匹配，匹配的选取过程可以用背包描述。令 $g_u(i,j)$ 表示（处理 $u$ 的 DP 信息时，）选的 $f(v,0)$ 数量与 $f(v,2)$ 数量之差为 $i$，$f(v,1)$ 数量奇偶性为 $j$ 是的最大和。最后真正需要的 $g_u(i,j)$ 满足 $i\in\{-1,0,1\}$，根据经典 trick，shuffle 孩子们，然后限制 $i$ 这一维绝对值不超过 $\sqrt n$ 即可。复杂度 $\mathcal O(n\sqrt n)$。

「Snackdown 2021 Final」Robbery (private link)

??不难证明：$2m$ 件物品可以分为两组，每组 $m$ 件，且质量和之差不超过 $n$。令 $f(k,w)$ 表示所求答案，构造如下递归方式：

\[f(k,w)=\begin{cases} \max_{i\in[1,n]}\{f(k-1,w-i)+a_i\},&2\nmid k\\ \max_{d\in[-n/2,n/2]}\{f(k/2,w-d)+f(k/2,w+d)\},&2\mid k \end{cases}. \]

可见仅会涉及 $\log$ 个 $k$，且 $k$ 一定时，$w$ 的取值在一个较小的区间内，大力记忆化即可。

「Snackdown 2021 Final」Queue at the Bakery (private link)

??暴力 DP，令 $f(i,j,k)$ 表示还要接待 $i$ 个客人，当前所考虑的服务员手上还有 $j$ 天的工作，前面还有 $k$ 个服务员先于他接客时，被这一服务员接待的客人的等待时间之和。可知转移式为

\[f(i,j,k)=\begin{cases} (1-p)f(i-1,\max\{j-1,0\},k)+pf(i-1,\max\{j-1,0\},k-1), & k\neq0\\ (1-p)f(i-1,\max\{j-1,0\},k)+p[f(i-1,j+d-1,m-1)+j], & k=0 \end{cases}. \]

注意 $i$ 维和 $k$ 维的大小是固定的，但是 $j$ 显得比较特殊——因为 $p\in[0.4,0.6]$，当 $d$ 较小时，服务员很难积累到较大的 $j$；当 $d$ 较大时，服务员将处于无休状态，此时再令 $j\leftarrow j+t$ 时，服务员接待的客人全部都要等待 $t$ 天，所以 $\Delta f=tg(i,k)$，其中 $g(i,k)$ 表示还要接待 $i$ 个客人，当前所考虑服务员前面还有 $k$ 个服务员先于他接客时，这一服务员期望接待的客人数。因此，我们设定一个阈值 $S$，钦定有

\[f(i,S+j,k)=f(i,S,k)+jg(i,k). \]

经~~邓老师~~分析，$S$ 取 $1500$ 是足够的。复杂度为 $\mathcal O(nSm)$。

Z.游记

Diary / Solution Set -「WC 2022」线上冬眠做噩梦

相关

标签