“辜负了……期望……”

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\,pos\,c$ 将 $s_{pos}$ 更新为字符 $c$

$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$ 都小于剩余人数时，报若干次数不至于绕一圈，可以直接跳过这些状态到需要取余的那一步。

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)$。
这题……其实不怎么想写上来，纯粹是因为想再记一下线性公式的推导。

Hello World.

题解 07

CF 1509 C The Sports Festival

CF 1343 D Constant Palindrome Sum

CF 1234 D Distinct Characters Queries

2018-2019 ICPC Shenyang C Insertion Sort

2018-2019 ICPC Shenyang K Let the Flames Begin