前几天做了做今年 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

~~ GF 题狗都不做。~~

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

[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)$. 有点卡常数, 需要精细实现一下.