A – Tourist Problem

非常有趣的一道数学题，我们来分析一下。原讲稿：https://comfortablecom.wordpress.com/2017/10/06/jzoj-b%E7%BB%84-10-6-%E6%80%BB%E7%BB%93/

我们先设一种情况的答案为\(S_x\)，显然，可以写成：

\[ S_x = |a_{x_1}-0|+|a_{x_2}-a_{x_1}|+|a_{x_3}-a_{x_2}|+|a_{x_4}-a_{x_3}|+\dots +|a_{x_n}-a_{x_{n-1}}| \]

这一长串的答案其实就是被减数与减数的组合。我们会发现，几乎每一个数都在这个式子中扮演了被减数与减数的角色，除了最后一个元素，即\(a_{x_n}\)。这个元素只充当了一次被减数，仅此而已。

我们考虑\(i\)对答案的贡献。首先，\(i\)作为被减数一共有\(n!\)中可能，其中减数缺了一部分的可能，这一缺失的部分就是\(i\)作为\(a_{x_n}\)的可能数，也就是\((n-1)!\)。之后，考虑在一种序列中\(i\)的贡献。当\(j<i\)时，包括\(0\)，一共有\(i\)个数使\(i\)可以在不变号的情况下减去减数；而，当\(i<j\)时，情况就不同了，一共有\(n-i\)种数是的\(i\)在变号的情况下进行对答案的贡献。部分分析结束，总结为一个式子：

\[ a_i(n-1)!i+(-a_i)(n-1)!(n-i) \]

结合上面我所分析的可能方案数和不同情况下的讨论，请读者用心领悟。

而作为减数其实就是换汤不换药了。只要把正负的两种关系变化一下即可，计算式为：

\[ (-a_i)(n-1)!(n-i)+a_i(n-1)!(i-1) \]

注意，此式中最后一项中的\(i-1\)是因为\(0\)无法作为其被减数而造成的。有那么一点点不对称吧。

代码

// A.cpp
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MAX_N = 100200;
int n, arr[MAX_N];
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    sort(arr + 1, arr + 1 + n);
    ll x = 0;
    for (int i = 1; i <= n; i++)
        x = x + 1LL * arr[i] * (1LL * 4 * i - 1LL * 2 * n - 1);
    ll d = gcd(x, n);
    printf("%lld %lld", x / d, n / d);
    return 0;
}

B – 工作安排 Work

这道题其实在考场上连斜率式子都推完了，但是因为太懒而且不知道怎么隔着\(k\)进行转移所以弃疗，最后边界忘记检查 50 分傻*暴力都没拿到。

这道题的 DP 方程式可通过一眼法得出，其中需要先进行排序：

\[ dp[i] = min\{ f[j-1]+C+(f[i]-f[j])^2 \}, j-1 \in [0,i-k] \]

之后我们来思考如何进行斜率优化。斜率优化是一个非常常用的 DP 优化手段，建议深入了解。我们设\(k\)为我们想要的最优解，那它一定满足：

\[ f[k-1]+C+(f[i]-f[k])^2 < f[j-1]+C+(f[i]-f[j]))^2, j \in [1, i-k+1], j \neq k \\ (f[k-1]-f[j-1])+(f[k]^2-f[j]^2) < 2f[i](f[k]-f[j]) \]

判断时，注意正负号对不等式的影响。

代码

// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 2e6 + 20000;
const ll INF = (0x3f3f3f3f3f3f3f3f);
ll f[MAX_N], arr[MAX_N], n, k, c, q[MAX_N << 2];
int head = 1, tail = 0;
ll pow(ll num) { return num * num; }
double check(ll a, ll b)
{
    return ((f[b - 1] + pow(arr[b])) - (f[a - 1] + pow(arr[a]))) / (2.0 * (arr[b] - arr[a]));
}
void insert(int x)
{
    while (head <= tail && arr[q[tail]] == arr[x])
        if (f[x - 1] < f[q[tail] - 1])
            tail--;
        else
            return;
    while (head < tail && check(q[tail - 1], q[tail]) > check(q[tail], x))
        tail--;
    q[++tail] = x;
}
int main()
{
    freopen("work1.in", "r", stdin);
    scanf("%lld%lld%lld", &n, &k, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    f[0] = 0;
    sort(arr + 1, arr + 1 + n);
    for (int i = 1; i < k; i++)
        f[i] = INF;
    for (int i = k; i <= n; i++)
    {
        int x = i - k + 1;
        insert(x);
        while (head < tail && check(q[head], q[head + 1]) < arr[i])
            head++;
        f[i] = f[q[head] - 1] + c + pow(arr[q[head]] - arr[i]);
    }
    printf("%lld", f[n]);
    return 0;
}

C – 阿Q的停车场 Park

一道线段树的题目（我改题的时候差点下定决心整晚写个 Treap 的版本来搞，最后发现线段树绰绰有余）。我们维护左边极点、右边极点、最长空位长度和最佳停车点。线段树更新的时候选择左区间、合并区间和右区间进行比较即可。

代码

// C.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 200200, INF = 0x3f3f3f3f;
int n, m, tree_l[MAX_N << 2], tree_r[MAX_N << 2], tree_len[MAX_N << 2], tree_pt[MAX_N << 2], park[(int)1e6 + 2000];
int getFirst(int a, int b, int c, int d)
{
    if (a > 0)
        return a;
    if (b > 0)
        return b;
    if (c > 0)
        return c;
    if (d > 0)
        return d;
    return d;
}
void update(int qx, int l, int r, int p)
{
    if (l == r && l == qx)
    {
        tree_l[p] = l, tree_r[p] = r, tree_len[p] = 0, tree_pt[p] = 0;
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
    tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
    // check three intervals;
    // first;
    tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
    if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
        tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
    if (tree_len[rson] > tree_len[p])
        tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
void remove(int qx, int l, int r, int p)
{
    if (l == r && l == qx)
    {
        tree_l[p] = tree_r[p] = tree_len[p] = tree_pt[p] = 0;
        return;
    }
    if (qx <= mid)
        remove(qx, l, mid, lson);
    else
        remove(qx, mid + 1, r, rson);
    tree_l[p] = getFirst(tree_l[lson], tree_r[lson], tree_l[rson], tree_r[rson]);
    tree_r[p] = getFirst(tree_r[rson], tree_l[rson], tree_r[lson], tree_l[lson]);
    // check three intervals;
    // first;
    tree_len[p] = tree_len[lson], tree_pt[p] = tree_pt[lson];
    if (tree_l[rson] > 0 && tree_r[lson] > 0 && ((tree_l[rson] - tree_r[lson]) >> 1) > tree_len[p])
        tree_len[p] = (tree_l[rson] - tree_r[lson]) >> 1, tree_pt[p] = (tree_r[lson] + tree_l[rson]) >> 1;
    if (tree_len[rson] > tree_len[p])
        tree_len[p] = tree_len[rson], tree_pt[p] = tree_pt[rson];
}
int main()
{
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            if (tree_l[1] > 0)
            {
                int tmp = tree_len[1], key = tree_pt[1];
                if (tree_l[1] - 1 >= tmp)
                    key = 1, tmp = tree_l[1] - 1;
                if (n - tree_r[1] > tmp)
                    key = n, tmp = n - tree_r[1];
                park[x] = key;
            }
            else
                park[x] = 1;
            printf("%d\n", park[x]), update(park[x], 1, n, 1);
        }
        else
            remove(park[x], 1, n, 1);
    }
    return 0;
}