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;
}
