0%

题解 07

“辜负了……期望……”

CF 1509 C The Sports Festival

长为 $n$ 的数列 $s$,定义其所有前缀的极差之和 $\sum_{i = 1}^{n}\max(s_1,s_2,\cdots, s_n) - \min(s_1,s_2,\cdots, s_n)$,改变 $s$ 中元素的顺序,使这个值最小,输出最小的值。
$1\le n\le 2000,1\le s_i\le 10^9$

区间 dp。本来想直接贪心的,因为发现把相同的数字连在一起最好,但是发现连在一块的元素还可能交换位置。

定义 $dp_{ij}:=子段[i, j]的最小前缀极差和$,则一个状态可以来自两个方向。

最值 + 允许 $n^2$ 的数据,一般就是 dp。其实贪心也可以当 dp 来做,所以遇到直接当成一样的想就行了。至于状态定义,有的确实难想,要多做题。

CF 1343 D Constant Palindrome Sum

长度为 $n$ 的数列 $a$,元素都是在 $[1, k]$ 的整数,且 $n$ 是偶数。替换(或不替换)数列中的某些数,使得 $\forall i\in [1, \frac{n}{2}]: ai + a{n - i + 1} = x$,其中 $x$ 是某个常数。
多组样例
$1\le t\le 10^4, 2\le n\le 2\cdot 10^5, 1\le k \le 2\cdot 10^5,1\le a_i\le k$
$\sum n \le 2 \cdot 10^5, \sum k \le 2 \cdot 10^5$

要求对称位置的和都是一样的数,求最小的修改次数。则数对可以分成三类:一个都不需要改的 $p_0$ 对、需要改动其中一个数的 $p_1$ 对、两个数都需要改动的 $p_2$ 对。全部替换完的 $x$ 显然应该是原来各种数对和的其中一个。结合题目数据规模,我们可以从数对和中枚举这个 $x$,计算需要替换的最少次数。

对于每个枚举到的 $x$,需要替换的次数为 $n - 2p_0 - p_1 = 2p_2 + p_1$。统计每种数对和的个数,以及替换其一可以到达 $x$ 的数对个数(注意不替换的也被包含)即可计算得到答案。前者直接数,后者需要用差分。时间 $O(n + k)$。

在 $[1,k]$ 中枚举时,有许多原来就不会得到的数对和,这部分需要跳过,而求差分用的前缀和又要求连续,那么我们可以采用离散化 + 差分的方法,或者说扫描线。

每个数对有原始和、最大和、最小和一共至多 $3n$ 个元素,离散化存储后,对每个元素做相同的统计。因为离散化的压缩,需要用二分查找来确定位置。时间 $O(n\log n)$,主要开销在离散化后重新遍历统计。

对于这道题的 $k$,这个方法的提升似乎不是特别大,但是将复杂度缩减到与“数值”无关是十分重要的,背包问题就做不到这一点,它的 $O(nV)$ 是一个伪多项式复杂度。简单来说,“输入规模”的扩大必须体现在输入比特大小上,以表示信息变多。

CF 1234 D Distinct Characters Queries

一个小写字符串 $s$,两种操作共 $q$ 次:

  1. $1\,pos\,c$ 将 $s_{pos}$ 更新为字符 $c$
  2. $2\,l\,r$ 输出子串 $[l,r]$ 中字符的种类数

$1\le|s|\le 10^5, 1\le q\le 10^5, 1\le pos, l, r\le |s|$

简单线段树,出现在这里是因为维护的数据比较特殊,可以用来练手。

2018-2019 ICPC Shenyang C Insertion Sort

定义一个长度 $n$ 的序列是“接近有序的”当且仅当其 LIS(Longest Increasing Subsequence) 的长度至少为 $n - 1$。在 $1$ 到 $n$ 的所有排列中,求将前 $k$ 个数排升序后接近有序的排列数量,对大数 $q$ 取余。
$1\le n, k\le 50,10^8\le q\le 10^9$

组合数学题。首先考虑 LIS 长 $n$ 的,即后面 $n - k$ 个都有序,一共 $k!$ 种。

然后考虑 LIS 长 $n - 1$ 的,即只允许一个逆序对。在前 $k$ 个里做交换会被排序消除,只能在后 $n - k$ 个里面交换,或者前后两段之间交换,而前 $k$ 个自由排列,一共 $k!(n - k)(n - 1)$ 种。

50 以内的阶乘可以开递归或循环处理。记得在可能溢出的地方取余。

2018-2019 ICPC Shenyang K Let the Flames Begin

$n$ 个人围一圈,编号逆时针从 $1$ 到 $n$。一号从 $1$ 开始逆时针报数,报到 $k$ 的人出列,从他的下家继续这个过程。出列的人不参与报数。求第 $m$ 个出列的人的编号。
$1\le n, m, k \le 10^{18}, m\le n, T\le 1000, \sum\min(m, k) \le 2\cdot 10^6$

经典约瑟夫问题。首先要明白那个线性递推公式的意义:$n - 1$ 规模时留下的最后一人,与 $n$ 规模的相差了一个偏移量 $k$。$J{n, k} = (J{n - 1, k} + k) \mod n$。(从 0 编号,下同,答案加一个偏移即可)

这里用线性循环来推显然会超时,需要两个优化。根据线性公式,可以知道第 $m$ 个出列的人,在那个规模($n - m + 1$ 个人)的编号是 $(k - 1) \mod (n - m + 1)$,从此出发往前推,这样可以少推几个状态。这是第一个优化。

第二个优化基于这一点:当几倍的 $k$ 都小于剩余人数时,报若干次数不至于绕一圈,可以直接跳过这些状态到需要取余的那一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(int casei) {
cout << "Case #" << casei << ": ";
long long ans = (K - 1) % (N - M + 1);
if (K == 1) {
cout << M << endl;
return;
}
for (ll i = N - M + 2; i <= N; i++) {
ans = (ans + K) % i; // normal iteration
// jump forward
ll rem = (i - ans - 1) / K;
rem = min(rem, N - i); // limit the times of jump
i += rem; // jump
ans += rem * K;
}
cout << ans + 1 << endl;
}

时间复杂度按照 OI-wiki 上的类似算法,应该是 $O(k\log n)$。
这题……其实不怎么想写上来,纯粹是因为想再记一下线性公式的推导。