【Fortuna OJ】10/22 Contest / 题解

Posted on by xgzepto

逛公园

琥珀色黄昏像糖在很美的远方，思念跟影子在傍晚一起被拉长……

题目描述

小 B 带着 BF 去逛公园，公园一共有 n 个景点，标号为 1 . . . n。景点之间有 m 条路径相连。
小 B 想选择编号在一段区间 [l, r] 内的景点来游玩，但是如果这些景点的诱导子图形成了环，那么 BF 将会不高兴。
小 B 给出很多个询问 [x, y]，想让你求有多少个区间 [l, r] 满足 x ≤ l, r ≤ y 且不会使 BF不高兴。

思路

首先我们可以找出所有的环。一个环对答案的影响只取决于其上点编号的最值。O(n) 预处理出所有的环左右端点的编号，将问题转化为有不包含一些区间的合法区间数量后，我们令 $faraway_i$ 为以 $i$ 为左端点的合法区间的右端点最大值，发现 $faraway$ 数组是单调的。于是对于每个询问 $[l,r]$，在 $[l,r]$ 中二分找出最大的 $p$ 使得 $faraway_p < r$，然后将询问拆成两部分分别计算贡献。

  • 如何求 $faraway$ 数组：左端点排序维护对当前点有影响的环，优先队列维护这些环右端点的值。
  • 如何统计答案：前缀和 + 等差数列求和。

代码

风筝

当一阵风吹来，风筝飞上天空，为了你，而祈祷，而祝福，而感动……

题目描述

oyiya 在 AK 了 IOI 之后来到了乡下，在田野中玩耍，放松身心。

他发现前面有一排小朋友在放风筝，每一个风筝有一个高度 hi，风筝的高度可能会随着小朋友的心情而改变。这时，毒瘤的 oyiya 有了一个毒瘤的 idea，他想知道改变高度之后风筝的最长严格上升子序列。oyiya 太强了表示并不想做这种水题，你能解决这个问题吗？

思路

我们先求出新序列经过这个点的 LIS 长度，然后将它与原序列 LIS 长度（考虑是否减一）取最大值。原序列 LIS 长度需要减一当且仅当这个位置是原序列 LIS 的必经之处。

解决以上问题只需要预处理出两个数组：$pre_i$ 和 $suf_i$，分别表示不考虑修改，以第 $i$ 个点为结尾 / 开头的 LIS 长度。对于第 $i$ 个点，如果满足 $pre_i+suf_i=len+1$（len 为 总LIS 长度），则这个点在 LIS 的第 $pre_i$ 位上。枚举所有的位置，如果只有 $i$ 在这一位上，则 $i$ 是 LIS 的必经之处。

现在我们考虑修改位置 $p$ 上的值为 $h$。如果新序列 LIS 不经过 $p$，答案就是 $len$ 或者 $len-1$，取决于这个点是不是原序列 LIS 必经之处。如果新序列 LIS 经过 $p$，我们找出 $p$ 之前 / 之后第一个小于 / 大于 $h$ 的位置，经过 $p$ 和这两个位置的子序列才可能是新序列 LIS。

如何计算后一种情况呢？将问题离线，可以在计算 $pre, suf$ 数组的同时更新后一种情况的答案。

代码

种花

院子落叶，跟我的思念厚厚一叠；窗台蝴蝶，像诗里纷飞的美丽章节……

题目描述

小 H 是一个喜欢养花的女孩子。

她买了 n 株花，编号为一里香，二里香……七里香……n 里香，她想把这些花分别种在 n 个不同的花盆里。

对于一种方案，第 $i$ 个花盆里种的是 $a_i$ 里香，小 H 定义其美丽值为：

$$\sum\limits_{i<j,a_i>a_j}(j-i)*(a_i-a_j)$$

另外，由于一些特殊原因，第 $i$ 个花盆里不能种 $p_i$ 里香。

现在，小 H 想知道，所有合法方案的美丽值的和是多少。你能帮她解决这个问题吗？

思路

首先我们发现这是一个错排问题。

$f_{i,j}$ 表示一共有 $(i + j)$ 个元素，其中 $j$ 个没有限制，另外 $i$ 个被禁止放入一个位置。

我们先计算 $j=0$ 的情况，也就是经典的错排问题，此时每个元素都有限制。

首先，考虑加入第 $x$ 个元素，把它放在位置 $k$，一共有 $x-1$ 种方案；

对于原来在位置 $k$ 的元素，有两种情况：

  1. 把它放到位置 $x$，剩下 $x-2$ 个元素错排即可，有 $f_{x-2,0}$ 种方案；
  2. 第 $k$ 个元素不放到位置 $x$，这时对于这 $x-1$ 个元素的错排，有 $f_{x-1,0}$ 种方案。

现在我们加入一个没有限制的元素。如果该元素放置的位置是有限制的，那么以前有限制的元素就变成了没有限制的了，有 $x$ 种选择方法，剩下的元素的放置方案数为 $f_{x−1,y}$；如果该元素放置的位置是没有限制的，那么有 $y$ 种选择方法，剩下的元素的放置方案数为 $f_{x,y−1}$。

于是得到转移方程：

$$f_{0,0} = 1$$
$$f_{x,0} = (x − 1)(f_{x−1,0} + f_{x−2,0})$$
$$f_{x,y} = f_{x,y−1} × y + x × f_{x−1,y}$$

回到这道题目本身。我们枚举每一对 $i,j (i<j)$，确定 $(j-i)$ 的值之后，剩下的贡献需要分三种情况讨论：

  • $p_j$ 放在 $i$ 上，$p_i$ 放在 $j$ 上，那么有 $f_{n-2,0}$ 种方案，贡献 $a_1 = \max (0,p_j-p_i)$。
  • 上述两个条件只有一个成立，那么有 $f_{n-3,1}$ 种方案，贡献 $a_2=\sum_{k=1}^{p_j-1}k+\sum_{k=1}^{n-p_i}k-2a_1$。
  • 上述条件均不成立，那么有 $f_{n-4,2}$ 种方案，贡献 $a_3=\sum_{k=2}^n (n-k+1)k-a_1-a_2-\sum_{k=1}^{p_i-1}k-\sum_{k=1}^{n-p_j}k+\max (0,p_i-p_j)$。

我们是如何计算 $a_2$ 的呢？显然，当 $p_j$ 放在 $i$ 上，对于所有满足条件的 $a_j$，有$a_j-a_i = a_j-p_j$，它们的和为 $\sum_{k=1}^{p_j-1}k$。类似地，我们求出 $p_i$ 放在 $j$ 上的答案为 $\sum_{k=1}^{n-p_i}k$。由于两次计算导致和 $a_1$ 重复，故减去 $2a_1$。

对于 $a_3$，我们枚举所有的 $a_i < a_j$，它们差值的和为 $\sum_{k=1}^{n-p_i}k$。这个值包含了 $a_1, a_2$，以及非法方案 $(a_i=p_i, a_j=p_j)$，故全部减去，两种非法的方案有重复的部分，故加上 $\max (0,p_i-p_j)$。

至此，我们可以直接计算答案了：

$$\sum_{i<j}(j-i)(a_1 f_{n-2,0}+a_2 f_{n-3,1}+a_3 f_{n-4,2})$$

代码