• 搬题人
  • 饼干：Wu_Ren
  • 消愁：hehezhou
  • 养鸡：flower
• 组题人：p_b_p_b
• 题解：Wu_Ren，ChatGPT，flower

饼干

来源：

• Petrozavodsk Summer 2020 Day 5: JAG Summer 2019+, Problem L
• https://qoj.ac/contest/505/problem/1346

Tutorial by Wu_Ren.

考虑如果仍然需要补魔，那么先施法再补魔一定比先补魔再施法更劣。

那么我们每次一定是，先施法然后补满，直到某次我们施法完之后，把魔补到剩下消耗的总和，然后依次施完。

那么这个过程就相当于我们每个魔咒变成 $a_i$ 个物品，第 $j$ 个物品权值是 $j$，然后我们有 $m$ 次机会把某个魔咒里权值最小的那个物品删去，我们称这个为操作一。

我们要求最后权值和最小。

然后吃饼干就是有 $k$ 次机会把某个魔咒里权值最大的那个物品删去，我们称这个为操作二。

仔细分析一下，我们就是每次对最大的 $a_i$，使用 $a_i$ 次操作一（不足就全用了）。等所有操作一用完后，贪心地使用操作二即可。

复杂度 $O(n\log n+m)$ 或 $O(n\log n)$。

消愁

来源：

• Petrozavodsk Summer 2021 Day 3: GP of IMO, Problem J
• https://qoj.ac/contest/693/problem/1839

由于出题人鸽没了，下面是一个 ChatGPT 翻译的题解。

你好！以下是将LaTeX文档翻译成中文的内容：

首先，$f(p, q)$显然只依赖于对$(p_i, q_i)$的顺序，所以我们可以假设初始时$p_i = i$。

引理。$f((1, 2, \ldots, n), q)$ = $q$的递增子序列的个数。

证明。让我们首先分析字符串$s$何时满足$p$，$q$。基本上，我们有$n$个节点对应上行，$n$个节点对应下行，以及它们之间的一些有向边$(u, v)$，表示单元格$u$中的数字必须小于单元格$v$中的数字。要将1到$2n$之间的数字放入这些节点中，以便满足所有关系的必要和充分条件是：\textbf{不能有有向环}。我们将证明在我们的图中，这等价于以下条件：\textbf{不存在大小为$4$的有向环}。

的确，考虑最小长度的有向环，假设其大小大于$4$。它必须包含来自两个不同行的节点之间的边，因为单行内不能有任何环。不失一般性地，从单元格$(1, i)$到$(2, i)$的边。现在必须有一条从$(2, i)$到某个地方的边，不失一般性地到$(2, j)$。最后，如果从$(2, j)$的边到$(2, k)$，我们可以通过从中移除$(2, j)$获得一个更短的环，因为有一条$((2, i), (2, k))$的边，所以它的边到$(1, j)$。现在，如果$p_i < p_j$，那么我们可以将路径$((1, i), (2, i), (2, j), (1, j))$替换为$((1, i), (1, j))$，否则我们得到一个大小为$4$的环。

因此，只需确保没有大小为$4$的有向环。让我们找到满足此条件的字符串$s$的数量。考虑使$q_i=n$的$i$。如果我们将$s_i$设置为\t{0}，我们可以忘记对$(p_i, q_i)$，因为它不能参与任何长度为$4$的环。否则，我们得到矩阵中$(1, i)$单元格的数字大于第二行中的最大数字，因此对于每个$j > i$，$(1, j)$单元格中的数字也大于$(2, j)$单元格中的数字。因此，如果我们将$s_i$设置为\t{1}，我们还必须将所有$j > i$的$s_j$设置为\t{1}。在此之后，我们可以丢弃所有$j \ge i$的对$(p_j, q_j)$，因为它们无法参与任何环。

因此，我们有一个数组$q$和两个操作：

• 删除最大元素
• 删除最大元素及其右侧的所有元素。

很容易证明，通过按某种顺序应用这些操作删除整个$q$的方法数等于$q$的递增子序列的数量。事实上，每个这样的操作序列对应于我们在它们是最大的时候将应用第二个操作的数字子序列。

引理得证

现在，我们有以下问题：

• 给定$q$的某些元素的排列，其他元素缺失。找到所有有效排列$q$（意味着它们在正确的位置上有给定的元素）的$f(q)$之和。

对于$n \le 100$，这是一个简单的问题。设置$q_0 = 0$和$q_{n+1} = n+1$，现在$f(q)$是从$q_0$开始到$q_{n+1}$结束的递增子序列的个数。对于已经设置的每个元素，比如$q_i$，计算$dp[i][k]$ --- 从$q_0$开始到$q_i$结束的递增子序列的数量，其中恰好包含$k$个\textbf{未设置}的元素。

以下是转移：对于每个$j < i$使得$q_j$也设置了且$q_j < q_i$，我们计算第$j$个和第$i$个之间的“自由”位置的数量，以及“允许”的元素的数量 —— 即 $[q_j+1, q_i-1]$ 中的元素，它们不是已经设置的元素。然后，对于不超过$max(free, allowed)$的每个$choose$和每个$chosen$，将$dp[j][chosen] \times (\binom{choose}{allowed} \times \binom{choose}{free})$添加到$dp[i][chosen+choose]$。

问题的答案就是$dp[n+1][x] \times (n-set-x)!$之和，其中$x$是已设置元素的数量。

养鸡

来源：

• Petrozavodsk Summer 2022. Day 7. HSE Koresha Contest, Problem A
• https://qoj.ac/contest/1016/problem/4878

Tutorial by flower.

显然是个二分图最大流的模型，接下来用用流的语言的来描述问题。

首先有个贪心做法。每次从 $n$ 扫到 $1$ 遇到一个区间的 $r$ 就加入这个区间，然后对于每个点尽量流 $l$ 最大的。

当 $l, r$ 递增的时候。可以发现上述贪心做的事情是，先加入的区间尽量先流，与 $l$ 具体啥样无关。如果从$n$担心到$p$，再从 $1$ 贪心到$p-1$。两侧的用到的区间是一个前缀和一个后缀。如果总和不爆那就不会冲突，也就是说答案是 $\min(lmaxflow + rmaxflow, \sum_{l_i \le p \le r_i} f_i)$。其中 $f$ 是区间的流量

计算 $rmaxflow$ 可以用 hall 定理，令 $s_i = \sum_{l_j \le p \le r_j \le i} f_j - \sum_{j = p}^{i} a_p $，其中 $a$ 是右侧一个点的流量。

那么答案就是所有区间流量和减去 $\max s_i$，用线段树维护即可。

考虑贪心在做的事情是保证右侧为最大流的情况下，尽量的选 $l$ 最大的，只要我们求出了每个点右侧的情况，那么把每个区间的剩余流量扔左侧跑个最大流即可。

考虑一个 $s_i$ 的含义是：$p$ 到 $i$里至少要浪费 $s_i$ 的区间的流量扔到左侧。把$s$的前缀最大值位置拎出来是 $i_1, i_2, \cdots, i_k$。

考虑 $p$ 到$i_k$ 里优先级最小（$l$ 最小）的区间假设在位置 $x$。令 $i_t \le x$ 且$t$最大，那么这个前缀要浪费$s_{i_t}$而总共要浪费$s_{i_k}$，那么就直接给这个区间的左侧部分增加 $\min(f, s_{i_k} - s_{i_t})$ 的流量，因为这些一定是被浪费的。

考虑直接线段树暴力维护上述过程，下面证明操作次数不超过$O(n\log n)$。

需要对于$s$ 数组做的事情是后缀加和把最大值和降低为非严格最大值。

考虑在线段树的结构，势能为有多少个节点的区间最大值来自右子树（如果相等认为在左子树）

那么每次操作都会使得使能少$1$（$i_k$, $i_t$ 在线段树的 lca），后缀加只会影响$\log n$个区间的相对顺序。 算上线段树操作的时间复杂度是 $O(n\log^2 n)$。