饼干
来源:
- Petrozavodsk Summer 2020 Day 5: JAG Summer 2019+, Problem L
- https://qoj.ac/contest/505/problem/1346
Tutorial by Wu_Ren.
考虑如果仍然需要补魔,那么先施法再补魔一定比先补魔再施法更劣。
那么我们每次一定是,先施法然后补满,直到某次我们施法完之后,把魔补到剩下消耗的总和,然后依次施完。
那么这个过程就相当于我们每个魔咒变成 ai 个物品,第 j 个物品权值是 j,然后我们有 m 次机会把某个魔咒里权值最小的那个物品删去,我们称这个为操作一。
我们要求最后权值和最小。
然后吃饼干就是有 k 次机会把某个魔咒里权值最大的那个物品删去,我们称这个为操作二。
仔细分析一下,我们就是每次对最大的 ai,使用 ai 次操作一(不足就全用了)。等所有操作一用完后,贪心地使用操作二即可。
复杂度 O(nlogn+m) 或 O(nlogn)。
消愁
来源:
- Petrozavodsk Summer 2021 Day 3: GP of IMO, Problem J
- https://qoj.ac/contest/693/problem/1839
由于出题人鸽没了,下面是一个 ChatGPT 翻译的题解。
你好!以下是将LaTeX文档翻译成中文的内容:
首先,f(p,q)显然只依赖于对(pi,qi)的顺序,所以我们可以假设初始时pi=i。
引理。f((1,2,…,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)。现在,如果pi<pj,那么我们可以将路径((1,i),(2,i),(2,j),(1,j))替换为((1,i),(1,j)),否则我们得到一个大小为4的环。
因此,只需确保没有大小为4的有向环。让我们找到满足此条件的字符串s的数量。考虑使qi=n的i。如果我们将si设置为\t{0},我们可以忘记对(pi,qi),因为它不能参与任何长度为4的环。否则,我们得到矩阵中(1,i)单元格的数字大于第二行中的最大数字,因此对于每个j>i,(1,j)单元格中的数字也大于(2,j)单元格中的数字。因此,如果我们将si设置为\t{1},我们还必须将所有j>i的sj设置为\t{1}。在此之后,我们可以丢弃所有j≥i的对(pj,qj),因为它们无法参与任何环。
因此,我们有一个数组q和两个操作:
- 删除最大元素
- 删除最大元素及其右侧的所有元素。
很容易证明,通过按某种顺序应用这些操作删除整个q的方法数等于q的递增子序列的数量。事实上,每个这样的操作序列对应于我们在它们是最大的时候将应用第二个操作的数字子序列。
引理得证
现在,我们有以下问题:
- 给定q的某些元素的排列,其他元素缺失。找到所有有效排列q(意味着它们在正确的位置上有给定的元素)的f(q)之和。
对于n≤100,这是一个简单的问题。设置q0=0和qn+1=n+1,现在f(q)是从q0开始到qn+1结束的递增子序列的个数。对于已经设置的每个元素,比如qi,计算dp[i][k] --- 从q0开始到qi结束的递增子序列的数量,其中恰好包含k个\textbf{未设置}的元素。
以下是转移:对于每个j<i使得qj也设置了且qj<qi,我们计算第j个和第i个之间的“自由”位置的数量,以及“允许”的元素的数量 —— 即 [qj+1,qi−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)。