Qingyu' blog

Blog

PA 2021 简单题的简要题解

2022-01-01 00:28:59 By Qingyu

前几天做了做今年 PA 的题. 因为难题都不会做,所以把简单题的题解写了:

Round 1

[C] Koszulki

签到题. 排序以后找到对应位置把相等的元素都取了即可.

[B] Oranżada

注意到我们肯定是取前 $k$ 个不同的元素交换过去, 因为取后面的元素的话交换序列就会有交叉, 一定是不优的.

[A] Od deski do deski

首先注意到序列可以删除当且仅当序列可以划分成若干个长度 $\geq 2$ 的子序列使得端点元素的值相同.

注意若到此时的序列是 $S$, 假设我们当前可以通过在 $S$ 后添加元素 $x$ 使得序列变得合法, 那么 $S+x$ 也可以通过添加 $x$ 使得序列变得合法. 所以, 我们不妨设 $dp_{i,0/1,j}$ 表示考虑到 $i$, 当前序列合法/不合法, 最后有 $j$ 个 $x$ 使得 $S+x$ 变得合法. 转移为:

  1. 若当前序列合法, 则如果我们添加了 $j$ 个 $x$ 中的一个, 则转移到一个合法的序列; 否则, 我们转移到一个不合法的序列. 如果我们此时在后面接着接上上述 $j$ 个 $x$, 那么我们其实可以无视最后一个元素, 合法的选法仍然合法. 同时, 我们也可以选择直接接上一个上一次我们选的元素, 所以总的选法有 $j+1$ 个
    • $dp_{i,j,0} \cdot j \mapsto dp_{i+1,j,0}$
    • $dp_{i,j,0} \cdot (n-j) \mapsto dp_{i+1,j+1,1}$
  2. 若当前序列不合法, 则我们如果接了一个合法的序列, 显然会转移到一个合法的序列, 同时根据上文我们也有接下来合法选法有 $j$ 种. 否则, 相当于我们接了个没用的元素过来, 选法是不变的.
    • $dp_{i,j,1} \cdot j \mapsto dp_{i+1,j,0}$
    • $dp_{i,j,1} \cdot (n-j) \mapsto dp_{i+1,j+1,1}$

因此直接 DP 即可. 时间复杂度为 $O(n^2)$

Round 2

[C] Zakłócenia

我们暴力预处理一下最小和最大的popcount是多少, 然后只要保证填完以后仍然在取值范围里即可. 时间复杂度为 $O(n \log |\Sigma|)$

[B] Pandemia

首先, 如果我们不考虑第一段和最后一段的话, 那么相当于是这样一个问题:

有 $n$ 个数, 第 $i$ 个数为 $x_i$. 每天白天你可以选择一个数并获得它的大小的收益, 随后每天晚上每个数的大小减 $2$. 问你可能的最大收益是多少.

容易发现我们直接把 $x_i$ 从大到小排序后贪心选择是最优的. 这是因为我们相当于是每天除了已经被选走和已经小于 $0$ 的数以外, 每个数使得收益减了 $2$. 由于较小的数更快小于零, 所以我们留着它们是最优的.

对于有开头和结尾的情况, 我们可以将除了开头和结尾以外的每个连续段 $x$ 看成 $2$ 个 $x/2$, 这样一定是最优的. 因为我们注意到一个长度为 $l$ 的段, 我们是不可能堵住了一边, 然后另一边跨过了中线的 - 当我们堵住一部分的时候, 我们肯定会立刻堵住另一部分, 否则堵住左边没有意义.

[A] Poborcy podatkowi

我们考虑一个暴力 dp. 设 $f[x][i]$ 表示考虑以 $x$ 为根的子树, 且它往上贡献一个长为 $i$ 的链, 最大收益是多少. 转移时, 我们做一个背包, 记 $g[b][c][d]$ 表示选了 $b$ 个 $1$, $c$ 个 $2$, $d$ 个 $3$ 的最大收益, 那么我们可以获得一个高达 $O(n^4)$ 的做法.

注意到我们一定是1和3匹配,2和自己匹配. 所以我们只需要知道 $b-d$ 的值 $\Delta$ 和 $c$ 的奇偶性 $o$, 这样背包数组就是 $g[\Delta][0/1]$, 总的时间复杂度是 $O(n^2)$ 的.

注意到我们其实只需要知道 $g[-1/0/1][0/1]$ 的值, 而我们知道, 对于一个有 $n$ 个 +1 和 $n$ 个 -1 的序列, 将其 shuffle 后, 前缀和绝对值的最大值是 $O(\sqrt n)$ 级别的. 所以我们直接 shuffle 一下所有儿子, 然后第二维强制要求过程中不能超过 $O(\sqrt n)$ 的 bound 即可.

讨论区里有两个不同的 $O(n \log n)$ 的做法, 留坑待填.

Round 3

[C] Sumy

注意到答案肯定是一段后缀合法, 所以二分一下即可.

[B] Mopadulo

记 $S_i = \left(\sum_{k=1}^i A_i\right) \bmod P$, 那么有以下显然的转移: $$ f_i = \sum_{j < i} [(S_i-S_j) \equiv 2 \pmod P] f_j $$ 根据 $S_j$ 与 $S_i$ 的大小关系即可知道会不会多加一个 $P$, 开两个树状数组维护一下就好了. 时间复杂度为 $O(n \log n)$

[A] Wystawa

首先, 我们先令每个 $i$ 取 $\min (a_i,b_i)$, 这样肯定会得到一组最优的方案, 但这个方案不满足恰好选了 $k$ 个 $a$ 的限制.

因此, 问题转化成了, 有 $n$ 个整数 $a_i,b_i$, 且 $\mathbf{a_i \leq b_i}$, 需要恰好选 $k'$ 个 $a_i$ 换成 $b_i$, 最小化最大子段和.

考虑以下求最大子段和的算法:

  • 初始时 $ans \leftarrow 0, sum \leftarrow 0$
  • 对 $i=1, 2, \cdots, n$:
    • $sum\leftarrow \max(0, sum + a_i)$
    • $ans \leftarrow \max(ans, sum)$

我们考虑对着这个过程 dp. 我们需要知道的信息有 $(i,j,sum,ans)$ - 其中 $i$ 表示现在考虑到哪一个数, $j$ 表示已经替换了多少个数. 注意到我们可以通过二分答案去掉 $ans$ 这一维度 - 只要保证他不超过我们当前二分的值 $mid$ 即可.

因此, 我们不妨设 $f_{i,j}$ 表示若当前考虑到第 $i$ 个数, 已经换了 $j$ 个 $b_*$, 且此时最大子段和不超过 $mid$ 的情况下, $sum$ 的值最小能是多少. 转移时秩序枚举这个数换还是不换, 并判定是否仍满足条件即可. 时间复杂度与空间复杂度均为 $O(n^2)$.

注意到整个问题是个费用流, 所以显然 $f_{i,*}$ 是凸的, 我们直接使用 std::set / std::priority_queue 来维护差分数组, 每次转移时会改头部的元素并删掉所有的负数. 容易发现只要我们把相同的一段 $0$ 缩起来那么复杂度就是对的. 在维护的过程中记录一下是怎么转移过来的即可构造出方案.

代码写了一年.jpeg

Round 4

[C] Ranking sklepów internetowych

首先注意到, 如果我们单独选出 $n$ 这个元素, 那么我们会得到的答案为 $2n+1$. 容易发现我们肯定不能比这个更优, 这是因为长为 $2l+1$ 的区间中位数最大也只能是 $n-l$.

对于计数, 我们直接枚举区间长度, 维护一下区间端点的合法区间即可.

[B] Skrzyżowania

考虑一个固定的起点 $s$, 假设我们在某个时刻 $T_0$ 中暴力 BFS 出所有可达的点, 记 $A_{x,y}$ 表示 $(x,y)$ 是否可达, 那么我们注意到如果 $(x,y)$ 可达, 那么我们考虑 $A_{x,y},A_{x+1,y},A_{x,y+1},A_{x+1,y+1}$, 一定长成以下三种矩阵之一: $$ \left[\begin{matrix} 1 & 1\\ 0 & 0\\ \end{matrix}\right],\left[\begin{matrix} 1 & 0\\ 1 & 0\\ \end{matrix}\right],\left[\begin{matrix} 1 & 1\\ 1 & 1\\ \end{matrix}\right] $$ 这是因为任意时刻任意路口水平线路与竖直线路至少有一条能走. 这便意味着, 我们合法的可行区间一定是一个矩形, 且这个矩形要么水平方向无限延伸, 要么竖直方向无限延伸.

考虑一次询问 $(x_1,y_1) \to (x_2,y_2)$, 我们将会说明, 其答案要么是从第 $x_1$ 行任意一点走到 $x_2$ 行任意一点的时间, 要么是从第 $y_1$ 列任意一点走到 $y_2$ 列任意一点的时间.

为什么呢? 以第一个 Case 为例, 假设初始时起点可达的点是延水平方向无限延申的, 那么我们考虑任意一个 $R_{x_1} \to R_{x_2}$ 的方案, 我们在第一步肯定可以直接走到起点(因为水平方向的点均可达). 随后, 如果我们走到终点的时候仍然是水平延申, 那么我们可以直接走到正确的终点. 否则, 此时可达区域必定是竖直延申. 那么注意到整个平面一定是被若干个这样竖直方向无限延伸的矩形划分了, 在这之前, 我们一定可以选择进入哪一个竖直划分的区域, 且无论走到哪里都是立刻走到终点, 所以这一定是一种合法的方案.

这告诉我们两个维度是独立的, 我们只需要解决一维的问题. 不妨假设我们考虑如何解决水平方向的问题. 注意到整个地图的周期是 $k=\operatorname{lcm}(1,2,3,\cdots, t) (t=8)$, 那么首先我们对于每个 $i$, 我们可以 $O(n \cdot \frac{k}{w})$ 算出这两行之间什么时候可达, 建图的时间复杂度为 $O(nmk/w)$. 随后, 我们用点 $f_{i,j}$ 表示目前在第 $i$ 行, 时间模 $k$ 为 $j$ 的一个状态. 由于我们肯定会贪心地往右走, 所以如果一个点有往右的边, 那么就一定不会走往下的边. 把这样的边去掉后, 图显然是无环的, 所以我们直接对森林中的每一棵树 dfs 即可维护出需要的信息. 询问时只需要找到对应点的深度大力差分以下即可.

第一步的过程比较慢, 可以优化: 我们直接爆搜出所有可能的红绿灯 bitset 的状态, 预处理它们 and 的结果即可. 复杂度是 $O(4^t \cdot k/w + nm)$ 的.

[A] Areny

Unsolved.

Round 5

[C] Butelki

状态总数是线性的, 所以直接 BFS 即可.

[C] Drzewo czerwono-czarne

首先特判掉以下平凡 Case:

  • $c\equiv c'$, 输出 Yes
  • $c$ 中只有一种颜色, 输出 No
  • $c'$ 中, 任意 $(u,v) \in E$ 都有 $c'_u \ne c'_v$, 输出 No

前两个 Case 显然, 第三个 Case 是因为我们最后一次操作的时候肯定会造出来两个相同颜色的点, 所以不可能没有这样的点.

否则, 我们分类讨论:

  1. 若存在某个度数 $\geq 3$ 的点, 输出 Yes
    1. 不妨假设这个点是 $x$, 且 $(x,a) \in E, (x,b) \in E, (x,c) \in E$
    2. WLOG 设 $c_x = 0$, 我们先证明一定可以转化成 $c_a=0,c_b=c_c=1$ 的 Case:
      1. 如果初始就满足, 显然合法.
      2. 若 $c_a=c_b=c_c=1$, 那么我们直接一次操作改 $c_a$ 为 $0$ 即可.
      3. 若 $c_a=c_b=0,c_c=1$, 那么我们一次操作改 $c_x$ 为 $1$ 即可.
      4. 否则, 任取一个有 $1$ 的点然过去即可.
    3. 从上可知, 只要我们想, 我们就可以造出这种特殊的结构. 现在我们的目标是让最后答案中这四个点的结构也长成这个样子.
    4. 如果在最后答案中, $c'_x = c'_a $ (或 $c'_b, c'_c$), 那么我们只要调一下颜色就正确了.
    5. 因此, 需要解决的 Case 为 $c'_x \ne c'_* (* \in \{a,b,c\})$. 根据平凡 Case 3, 我们肯定能找到 $(u,v)$ 使得 $c'_u = c'_v$. 不妨设 $u$ 是离根较近的一个点, 那么我们将 $u$ 到根路径上的点按顺序写下来: $\lambda_1, \lambda_2, \cdots, \lambda_t$
      • WLOG, $\lambda_1 = u, \lambda_{t-1} = a,\lambda_t = x$
      • 我们令 $c''_{\lambda_1} = c'_{\lambda_2}, c''_{\lambda_2} = c'_{\lambda_3}, \cdots, c''_{\lambda_{t-1}} = c'_{\lambda_t}$. 其余点仍满足 $c''_i = c_i$
      • 注意到如果 $c''$ 有解, 那么 $c'$ 立刻有解, 只要从底向上把这条链复原回去即可.
    6. 所以我们把 5 的情况都转化成了 4. 对于 4 的情况, 我们直接从底向上依次修每个叶子即可, 同样讨论一下颜色是怎么传的, 发现我们总是可以在不破坏这四个特殊点的结构的前提下把答案传过去.
  2. 否则, 转化成了序列上的问题.
    1. 如果序列开头的元素不一样, 那么我们只能把头给删掉, 因为我们只能merge两个连续段, 不能swap或split
    2. 如果删掉以后, $c$ 的连续段数目 $<$ $c'$ 的连续段数目就是 No, 否则就是 Yes
    3. 证明仍然是类似的调整. 注意到我们总是有一段的长度 $\geq 2$, 所以我们一定可以通过伸缩一段让前面一段自由.

总的时间复杂度为 $O(n)$

[B] Autostrada

Unsolved

[B] Desant 2

我们建一张图:

  • $i \to i+1$, 边权为 $0$
  • $i\to i+k$, 边权为 $\sum_{j=i}^{i+k-1} a_j$

那么一组询问的答案就是 $u \to v$ 的最长路. 注意到如果我们把每个数表示成 $x=ik+j (0 \leq j < k)$ 的形式, 那么这张图基本是一个网格图. 仿照 ZJOI 旅行者那一道题目分治即可. 注意到比较恶心的是 $(i,k-1) \to (i+1,0)$ 的边, 所以我们在分治的时候需要看一下, 如果这是第一次沿着 $i$ 这一维切的话, 需要把第一行的贡献也跑出来.

直接写的话可能会得到一个跑40秒的垃圾做法, 所以不要建图BFS, 直接手动算一下每一类边的贡献, 这样可以快 10 倍.

时间复杂度 $O(n^{1.5} \log n)$

[A] Zbiory niezależne

这个题之前我搬了个一模一样的, 视频题解里讲了, 暂时先不写了, 以后补一个(

[A] Fiolki

我们回顾一下这一道题: https://qoj.ac/problem/61

发现这道题与这个题基本一样, 我们同样对前 $k$ 个点取一个单位向量, 后面每个点都是其入边对应点的随机线性组合. 那么区间 $[l, r]$ 的答案就是 $\vec v_l, \vec v_{l+1}, \cdots, \vec v_{r}$ 张成线性空间的秩.

我们枚举 $r$, 并尝试将向量插入线性基中. 插入时, 我们在消元之前看一下这个元的编号是不是比它小, 如果小的话就swap以下, 这样保留出来的就是最大的一个线性基. 求出线性基以后维护一下对应的区间即可.

时间复杂度为 $O(md+nd^2)$. 有点卡常数, 需要精细实现一下.

Petrozavodsk Winter 2022 开始报名了

2021-12-23 22:34:05 By Qingyu

Moscow International Workshops 2021 Day 2 题解 (aka GP of Southern Europe)

2021-11-30 10:23:33 By Qingyu

A. ABC Legacy

记 $c_A, c_B, c_C$ 分别表示每个字母的出现次数, $f_{AB}, f_{AC}, f_{BC}$ 表示每种匹配的出现次数, 那么显然有 $$ \begin{cases} c_A = f_{AB}+f_{AC}\\ c_B = f_{AB}+f_{BC}\\ c_C = f_{AC}+f_{BC}\\ c_A+c_B+c_C = 2n \end{cases} $$ 于是显然可以解出 $f_{AB}=n-c_C, f_{AC}=n-c_B, f_{BC}=n-c{A}$, 即每种匹配的数量是固定的. 考虑所有含有 B 的匹配, 注意到最后还要匹配 AC 型的pattern, 所以我们在选择匹配 B* 的时候, 肯定会尽量选择后缀一段 A 和前缀一段 C, 那么匹配的时候找到第一个能匹配的 B 显然是最优的. 如果最后配不出来, 就是无解.

B. New Queries On Segment Deluxe

留坑

C. Counting Phenomenal Arrays

首先说一下我们在现场的做法: 不妨设 $a_1\leq a_2 \leq \cdots \leq a_n$, 只计数有序的序列数量, 乘上对应的系数即可.

注意到 $a_1a_2\cdots a_n = a_1+a_2+\cdots+a_n \leq na_n $, 所以我们有 $a_1a_2\cdots a_{n-1} \leq n$, 即我们选出的数中, 去掉最大的数, 乘积不能超过 $n$.

而另一方面, 当我们确定了前 $n-1$ 个数后, 我们可以通过解方程 $Px = S + x$ 来求出 $x$ 的值, 因此我们不难设计出一个 dp: 设 $f_{i,j,\pi,\sigma}$ 表示已经填了 $i$ 个数, 上一次填的是 $j$, 目前乘积是 $\pi$, 总和是 $\sigma$ 的贡献总和.

但上述 dp 的复杂度过高, 我们完全无法接受. 但是注意到大多数状态是完全不可达的, 因此我们不妨将上述过程写成一个搜索的形式, 只搜索可能达到的状态. 通过暴力实现搜索, 我们可以轻松通过 $n \leq 1000$ 的数据, 但仍然无法通过本题.

注意到我们可以添加许多剪枝. 其中最重要的一个是, 我们考察当前填出来的状态, 并通过解方程解出此时最后一个数能填啥. 如果这个解出来的值已经小于目前的 $j$, 那么再填下去就没有意义了, 我们直接认为不合法. 同时, 再添加若干个不同的优化(例如不需要去枚举1的数量,最后算答案再计算), 我们便可以轻松通过本题.

上述算法看起来不太科学, 通过地比较侥幸, 那么有没有更靠谱的算法? 当然是有的. 我们还是计算有序序列的数量, 但这次我们规定 $a_1>1$. 我们不妨设 $\varphi(a) = \sum(a) - \prod(a)$, 则我们最终要求 $\varphi(a)=0$. 但注意到, 若 $b_i > 2$, 则必有 $\varphi(a_1 \cdots a_k) \leq \varphi(a_1 \cdots a_{k+1})$, 而初始时我们有 $\varphi(a_1)=0$, 因此我们只要开始填数, $\varphi$ 值就恒小于等于 $0$, 只能在最后填 $1$ 来补救.

由于一个 $1$ 只能恰好将 $\varphi$ 值加 $1$, 所以显然 $\varphi$ 值不能超过 $n$. 我们仿照上述过程实现一个 dfs, 当我们搜出一个 $b_1,b_2,\cdots,b_k(b_1>2, b_i \leq b_{i+1})$, 其积为 $\pi$, 和为 $\sigma$ 时, 我们有 $\varphi(b) = \pi - \sigma$, 显然我们只有在最后填恰好 $-\varphi(b)$ 个 $1$ 才能让他有可能有贡献, 所以我们任取一个不含 1 的序列, 其只有不超过 1 种方法使得其有贡献. 最后我们添加 $k$ 个 $1$ 的方案数即为 $\binom{k-\varphi(b)}{-\varphi(b)}$, 乘上对应贡献的系数即可.

所有元素大于 1, 且乘积不超过 $n$ 的序列非常的少, 通过暴力打表我们可以验证总的可能状态数可以接受, 且我们每次递归都能找到一个对应的解, 故整个过程的复杂度是有保证的.

D. LIS Counting

留坑

E. Flood Fill

首先注意到, 如果两个块 $A,B$ 是相邻的, 那么我们不可能同时将 $A,B$ 均反色. 因此, 我们的操作相当于选一个互不相邻的联通块集合 $S$, 使得最小化 $\sum_{i\in S}f(i) + \sum_{i \notin S}g(i) = \sum g(n) + \sum_{i \in S} (f(i)-g(i))$, 这是一个二分图最大权独立集问题, 所以直接写个网络流就好了.

F. to Pay Respects

首先注意到, 我们的操作可以分为两类, 一类减小 $r$, 另一类不减小.

对于不减小的那一类, 我们考虑最后一次这样的操作在时刻 $T$, 如果存在 $T_0 < T$ 且 $T_0$ 你没有操作, 那么你把这次操作转移到 $T_0$ 显然更优, 这是因为反正你也不能减小了, 不如先操作让对面增长地慢一些.这说明我们第二类操作一定占据了所有操作的一个前缀. 存在一个显然的贪心, 即考虑每个时刻 $i$ 对答案的贡献 $\Delta_i$, 如果这个时刻你操作, 那么如果对面操作, 你的贡献就是 $(n-i+1) \cdot (p+r)$, 否则是 $(n-i+1) \cdot p$, 这是因为你显然不会让对面有值的时候放过它到后面再操作, 所以只有对面是 $1$ 的时候才有可能减小. 这样我们直接排序并取前 $K$ 大, 时间复杂度为 $O(n \log n+K)$.

事实上, 根据进一步分析, 我们显然会从间断点后取一个 $1$ 的前缀操作, 所以我们可以直接做一个类似双指针一样的操作, 一开始取前 $k$ 个, 每次取后面第一个调整即可. 时间复杂度为 $O(n+K)$.

G. Replace Sort

首先将 $B$ 排序, 随后发现我们替换的时候位置显然是单调的. 设 $f_{i}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数不变的最小代价, $g_{i,j}$ 表示将 $A$ 的前 $i$ 个数排序, 且最后一个数替换成了 $B_j$ 的最小代价, $p(x)$ 表示最大的一个 $k$ 使得 $B_k \leq x$.

转移时, 对于 $f$ 直接枚举前面放没放:

  • $f_{i} \leftarrow f_{i-1} (A_{i-1} \leq A_i)$
  • $f_i \leftarrow \min_{1 \leq j \leq p(A_i)} g_{i,j}$

对于 $g$, 我们注意到如果前面替换成了 $B_k$, 那么这次一定替换成 $B_{k+1}$, 因为填更大的只会让后面的限制变得更严格, 所以:

  • $g_{i,j} \leftarrow f_{i-1} + 1 (A_{i-1} \leq B_j)$
  • $g_{i,j} \leftarrow g_{i-1,j-1} + 1$

直接做复杂度显然是 $O(n^2)$ 的, 注意到我们可以使用线段树来优化 $g$ 对 $g$ 的转移与 $g$ 对 $f$ 的转移 (只需要区间取min, 区间求min即可. 平移操作没什么用, 加的1全都是全局加). 总的时间复杂度为 $O(n \log n)$.

H. Werewolves

注意到如果一个联通块有贡献, 那么造成贡献的颜色只有恰好一种, 所以我们可以枚举这种颜色, 然后数有多少个有贡献的联通块, 这可以通过一个简单的树上背包 ( $dp_{i,\delta}$ 表示考虑以 $i$ 为根的子树, $i$ 必须选, 出现次数最多的元素减去总元素为 $\delta$ 的方案数 ), 总的时间复杂度为 $O(n^3)$.

注意到 $\sum_{i=1}^n c_i = n$, 而我们枚举颜色 $i$ 做树上背包的时候, size 显然是不超过 $c_i$ 的, 所以我们只需要做大小不超过 $k$ 的树上背包, 它的时间复杂度是 $O(nk)$ 的, 具体之前我讲杂题的时候讲了就跳过了.jpeg

综上, 总的时间复杂度为 $O(n^2)$

I. Colourful Permutation Sorting

留坑

J. Jason ABC

注意到两次操作是一定够的, 我们设 $f_{c,i}$ 表示 $\sum_{i=1}^n [s_i=c]$, 求最小的 $j$ 使得 $\max_{i \in \Sigma} f_{i,j} \geq n$, 随后两次操作把剩下两种不够的字符补齐即可.

所以只需要特判零次和一次操作. 零次操作显然, 一次操作的话, 我们枚举这种操作的是什么字符, 然后在枚举左端点, 右端点显然是单调的, 于是就稍微维护一下就做完了. 时间复杂度 $O(n)$

K. Amazing Tree

首先注意到第一个元素一定是某一个叶子, 不妨设编号最小的叶子为 $x$, 则我们序列的第一个元素必定为 $x$.

不妨设我们 dfs 时的根为 $r$, $x$ 的唯一邻居为 $y$

  1. 若 $r = y$, 则我们在访问完 $x$ 后, 相当于从 $y$ 开始依次遍历每一个子树(除了 $x$), 显然我们还是会走到最小的叶子所在的子树内, 就变成了一个根确定的子问题.
  2. 若 $r \ne y$, 则相当于要选择一个 $y$ 的子树, 当作根所在的联通块, 显然我们取最小叶子最大的那个子树当根是最优的, 随后 dfs 的时候, 非最大子树的相当于根已确定, 直接走完所有的子树, 剩下的那一个还是需要做类似的过程确定最优的 $r$

L. Primes and XOR? Nonsense

留坑

M. Many LCS

留坑

N. Max Pair Matching

不妨设 $a_i \leq b_i$, 那么 $w(i,j) = \max(b_i-a_j,a_i-b_j)$. 那么最大匹配的权值就是选出恰好 $n$ 个点当作 $b_i$, 另外 $n$ 个点当作 $a_i$, 最大化他们相减的值. 我们可以假设 $2n$ 个点全都选 $b_i$, 那么把一个 $b_i$ 改为 $a_i$ 的代价即为 $a_i+b_i$, 按照代价排序选 $n$ 个最小的减去就是答案.

Moscow International Workshops 2021 Day 1 题解 (aka AMPPZ 2021)

2021-11-23 14:44:06 By Qingyu

http://blog.qingyu.us/2021/11/moscow-international-workshops-2021.-day-1./

Warning: 这场比赛可能会被用作 XXII Open Cup 的 GP of Poland, 如果你到时候想参赛的话就别看这篇博客了~

A. AMPPZ in the times of disease

首先注意到, 如果我们对每个 $S_1,S_2, \cdots, S_k$ 都确定了一个元素, 那么其余点显然只能选择距离其最近的一个关键点, 并加入这个集合(若有多个则显然无解).

令 $P_1 \in S_1$, 随后我们考虑距离 $P_1$ 最远的点, 不妨假设其为 $P_2$. (若有多个, 我们随便取一个即可)

那么, 如果 $P_2 \in S_1$, 那么 $f(S_1) \geq \mathrm{dist} (P_1,P_2)$, 但另一方面, 限制要求我们有 $f(S_1) \leq \min _{x \in S_1, y \notin S_1} \mathrm{dist}(x, y)$, 因此除非 $U \setminus S_1 = \varnothing$, 否则一定无解.

不妨设 $P_2 \in S_2$, 那么我们同样找到一个 $P_3$, 使得 $\min(\mathrm{dist}(P_1,P_3), \mathrm{dist}(P_2,P_3))$ 最小, 同样我们有 $P_3 \in S_3$.

这样重复 $k$ 轮, 我们就为每个集合都找到了一个关键元素. 时间复杂度为 $O(nk)$.

B. Babushka and her pierogi

留坑.

C. Cake

这个旋转操作看起来比较强大, 但是注意到旋转前后两维的奇偶性都会改变, 所以如果设 $b_{i,0} = a_{i,i \; \bmod 2}, b_{i,1} = a_{i,(i+1)\;\bmod 2}$, 那么旋转操作等价于交换两个相邻的 pair, 问题转化成给你一个序列, 问最少交换相邻元素多少次变成目标序列. 在没有相同元素的时候就是逆序对数, 而有相同元素时, 容易发现我们直接按顺序匹配就是最优的. 时间复杂度 $O(n \log n)$.

D. Divided Mechanism

直接暴力模拟即可, 难度全在读题上. 时间复杂度 $O(\sum nmq)$.

实现的时候如果直接维护整个图形可能有点难写, 直接记一下差分了多少即可.

E. Epidemic

留坑

F. Fence

首先注意到, 对于一个 $(a_i,b)$ 的二元组, 我们可以 $O(1)$ 求出其生成序列的奇数位置和与偶数位置和.

注意到当我们将 $b$ 变为 $b+1$ 时, 只有 $a_i \geq b$ 的位置的值变化了, 而这样的变化总数是不超过 $\sum_{b \geq 0}\sum_{i=1}^n [a_i \geq b] = \sum_{i=1}^n a_i = S$ 的, 所以我们可以直接暴力修改.

由于修改一个位置会影响后面位置的贡献, 我们可以开一棵线段树, 支持一下单点修改和区间换标记即可, 由于只有两种标记, 直接暴力存两个区间和即可. 时间复杂度为 $O(n + S \log n)$, 足够通过.

注意到我们修改的时候, 凡是这一轮没修改过的位置, 以后都不会再改了, 所以我们其实没必要线段树, 直接暴力维护即可. 对于删除操作, 直接使用链表维护即可, 时间复杂度为 $O(n+S)$.

G. Gebyte's Grind

如果我们将每个点看作一个映射 $f: \mathbb Z \mapsto \mathbb Z$ 的话, 那么这三类节点分别相当于:

  1. $f(z) = \begin{cases}z-b & z > b\\ -\infty & \mathrm{otherwise}\end{cases}$
  2. $f(z) = \begin{cases} c & z \geq c \\ -\infty & \mathrm{otherwise} \end{cases}$
  3. $f(z) = \max (z, c)$

首先注意到第三类节点可以写成 $f(z) = \begin{cases} z & z \geq c \\ c & \mathrm{otherwise} \end{cases}$, 那么注意到, 我们任意取出若干个映射, 他们的复合一定可以写成 $(f \circ \cdots \circ f_*)(z) = \begin{cases} -\infty & z \leq a \\ c & a < z \leq b & \\ z + d & \mathrm{otherwise} \end{cases}$的形式(更特殊的, 其实一定有 $d=c-b$), 所以我们可以开一棵线段树, 每个节点维护这个区间的复合对应的映射长什么样. 容易发现我们可以 $O(1)$ 求两个映射的复合, 所以我们可以轻松合并标记. 对于修改操作, 我们直接做即可. 对于查询操作, 我们先从 $l_i$ 往上 jump, jump 的时候把 parent 对应的右儿子复合起来, 如果发现此时 $f(z)$ 已经是 $-\infty$ 了, 就代表需要左拐, 直接进去右儿子并不断往左跳即可(整个过程类似线段树二分). 总的时间复杂度为 $O((n+q) \log n)$.

H. Hidden Password

签到题.

I. Interesting Numbers

不妨假设 $a_i \in [0,2^b)$.

  1. 如果 $k < 2^{b-1}$, 那么显然选出的数的最高位必须全都相同, 我们将最高位为 $0$ 和为 $1$ 的分开做即可, 转化为 $a_i \in [0,2^{b-1})$ 的子问题.
  2. 如果 $k \geq 2^{b-1}$, 那么我们考虑建出一张图, 如果两个数异或小于等于 $k$ 连一条边, 答案即为图 $G$ 的最大团. 注意到最高位相同的 $a_i$ 之间一定会连边, 因此图事实上是两个团之间连了一些边, 求最大团.
    • 注意到 $G$ 的补图为二分图, 所以可以直接跑二分图最大匹配, 如果使用 Dinic 算法, 总的时间复杂度会达到 $O(n^{2.5} \log V)$, 无法通过.
    • 整个图的结构非常优秀, 我们可以考虑 Trie 树优化建图, 这样的时间复杂度优化到 $O(n^{1.5} \log n \log V)$, 可以通过. 当然, 如果做的时候精细实现一下, 把每一层重复的部分压缩起来, 应该可以做到 $O(n^{1.5} \log n + n \log V)$ (没写过, 口胡的)
    • 事实上不用这么复杂, 我们仍然可以使用类似分治的方法解决. 我们继续将两个团 $A,B$ 划分为第 $b-1$ 位为 $0$ 的部分 $A_0,B_0$ 与为 $1$ 的部分 $A_1,B_1$, 那么我们考虑 $k$ 的第 $b-1$ 位:
      1. 如果这一位为 $0$, 那么答案显然就是 $\max (f(A_0,B_0), f(A_1,B_1))$, 直接递归即可.
      2. 否则, 注意到只有 $A_0,B_1$ 与 $A_1,B_0$ 的部分需要决策, 答案即为 $\max(|A_0|+|B_0|, |A_1| + |B_1| , f(A_0, B_1), f(A_1, B_0))$.
    • 总的时间复杂度为 $O(n \log V)$

J. Jungle Trail

若起点与终点间不连通, 则无解. 否则, 容易发现, 我们任取一条起点到终点的长为 $n+m-2$ 的路径, 每次移动都会走到一个新的行/列, 直接调整这些位置就是一组合法的方案.

K. Kitten and Roomba

我们在走路的时候, 维护一个 $p_i$, 表示此时你站在 $i$ 号点的概率, 那么整个过程的答案可以使用以下过程求出:

  1. 初始 $E \leftarrow 0$
  2. 对于每一步所走的 $x$:
    1. 令 $E \leftarrow E + p_x$
    2. 对所有 $(x,y) \in G$, 令 $p_y \leftarrow p_y + p_x / \deg (x)$
    3. 令 $p_x \leftarrow 0$.
  3. $E$ 即为答案

由于图是一棵树, 我们直接随便钦定一个点当根, 然后对于修改一个点邻居的操作, 我们变成修改它的父亲并在自己位置打一个标记. 查询的时候直接询问真实的值与父亲的标记相加即可. 时间复杂度 $O(n+m)$

L. Lemurs

容易发现如果一个位置能放, 那么我们放了显然不会让答案变劣, 所以我们能放就放是最优的.

而对于一个位置 $(x,y)$, 其能放当且仅当对所有 $|x'-x|+|y'-y| \leq k$ 的 $(x',y')$ 都是 x, 这可以通过转 Chebyshev Distance 后询问矩形和实现. 而求出答案后, 做同样的操作即可.

唯一的问题是虽然 $1 \leq n,m \leq 1000$, 但最坏情况下有 $50$ 组测试数据, 上述算法的时间复杂度为 $O(T(n+m)^2)$, 于是以 4.5 秒(时限4.0秒)的好成绩 TLE 了.

考虑一个常数更小的算法: 对于一个 ., 本质上其限制了预期 Manhattan 距离 $\leq k$ 的位置不能放, 所以相当于这些位置都被 ban 了. 我们对每个点维护一个 $f_i$, 表示这个点的距离限制, 那么我们按照 $f_i$ 从大到小 BFS, 即可求出所有被 ban 的位置. 最后合法的位置同样可以求出, 这样的时间复杂度就优化到了 $O(Tnm)$, 可以通过.

M. Median

留坑.

Auto Post by QOJ Editorial bot

1664 题资料整合

2021-06-30 15:17:55 By Qingyu

GP of Ukraine K. Dance

Official Editorial: https://drive.google.com/file/d/1F1OWy6mRypYzxBRtK3PV8NylIeCGpUOl/view?usp=sharing

Discuss: https://codeforces.com/blog/entry/55726

Editorial by zimpha:

不妨先把所有人都往左移动$d$,那么第$i$个人的位置要么是$x_i$,要么是$x_i+2d$。可以发现:

1. 现在最大的可能坐标是$200$。
2. 对于两个组$[l_i,r_i]$和$[l_j, r_j]$,这两个区间一定没有任何公共点,否则一定有一个更优的分组。

那么令$v_i$表示位置$i$和位置$i+1$是否是属于同一组,是的话是`1`,否则是`0`。对于一个固定的$v$,我们很容易判定是否合法:$v_i$是`0`当且仅当位置$i-2d$上没有人 或者 $v_{i-2d}$是`1`。一个连续的`01`就是一段区间的开始。

考虑按照$d$的大小来dp这个$v$数组:

+ $2d \le 20$,令$dp(i, mask)$表示考虑到前$i$个位置,最后$2d$个位置状态是$mask$的最小代价。转移的时候只需要每个$i+1$位置是`0`还是`1`即可。如果是`1`的话,需要根据位置$i$是`0`还是`1`确定代价$cost_0=a$,$cost_1=\min(a,b)$;如果是`0`的话,需要判定这个`0`是否合法,用上述条件即可。
+ $2d > 20$,可以发现$\frac{200}{2d} < 10$。那么可以考虑这样一个暴力dp,先枚举$0,2d,4d,\dots,$位置的状态,之后考虑$1,2d+1,4d+1,\dots,$的,依次类推,直到$2d-1,4d-1,6d-1,\dots$位置的状态。直接暴力做复杂度是$O(2^{30})$的,因为我们需要枚举第一层的,用作和最后一层合并。只需要把中间层的转移用逐格dp的方式来做,就可以把复杂度变成$O(2^{20})$。填`0`或者`1`的代价处理方式和上面一样。

ysy 题解,标程和选手代码都传了,去题库里看(团队 19 权限)

Qingyu Avatar