A.小红的陡峭值（一）

小红定义一个数组的陡峭值为：每两个相邻的元素，差值的绝对值之和。例如，数组${2,3,1}$​ 的陡峭值是 $∣2−3∣+∣3−1∣=3$​.
现在小红拿到了一个由 $3$​ 个整数组成的数组${a_1,a_2,a_3}$​，她希望你判断该数组的陡峭值是否为 $0$​，你能帮帮她吗？

直接模拟算一下

void solve() {
  int a, b, c;
  cin >> a >> b >> c;
  int ans = abs(a - b) + abs(b - c);
  if (ans == 0) {
    cout << "Yes";
  } else {
    cout << "No";
  }
}

B.小红的陡峭值（二）

小红定义一个数组的陡峭值为：每两个相邻的元素，差值的绝对值之和。例如，数组$ {2,3,1}$的陡峭值是 $∣2−3∣+∣3−1∣=3$

现在小红拿到了一个由 $n$ 个整数组成的数组 ${a_1,a_2,\dots,a_n}$，她希望你将该数组重新排列，使得数组的陡峭值尽可能小。请你输出小红有多少种不同的排列方案使得数组的陡峭值最小，并输出这个最小值。

两个方案被视为不同的，当且仅当存在一个位置 $i$使得两个方案中 $a_i$ 不同。

将数组排序后有

$b_1\leq b_2 \leq \cdots \leq b_n$

此时

$|b_2-b_1| + |b_3-b_2| +\cdots + |bn - b{n-1}| =-b_1 + b _2 - b_2 + b3 + \cdots - b{n-1} + b_n = b_n - b_1$

如果无序，例如将$b_3,b_1,b_2$则有 $b_3-b_1 + b _2 - b_1 =b_3 - b_2 + b_2-b_1 + b_2 - b_1 > b_n - b_n$

可证明当数组有序时最小，包括正序和逆序

但如果数组只有一个值，则答案为1种情况0

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(all(a));
  int ans = 0;
  for (int i = 1; i < n; i++) {
    ans += abs(a[i] - a[i - 1]);
  }
  vector<int> b = a;
  rev(b);
  if (b == a) {
    cout << 1 << " ";
  } else
    cout << 2 << " ";
  cout << ans << endl;
}

小红的陡峭值（三）（hard）

小红定义一个字符串的陡峭值为：每两个相邻字符，Ascii 码差值的绝对值之和。例如，$\texttt{"bca"}$ 的陡峭值是 $|\texttt{c'}-\texttt{b'}|+|\texttt{a'}-\texttt{c'}|=1 + 2 = 3$。

现在小红拿到了一个长度为 $n$，仅由小写字母构成的字符串 $s$。她希望你求出这个字符串所有长度为 $k$的连续子串的陡峭值之和，你能帮帮她吗？

相邻两个字符的绝对值记录为$v_i$,则构造一个关于$v$的前缀数组

间隔为$k-1$的前缀差即为一个连续子串的和，求和得到结果

void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<ll> v = {0};
  for (int i = 1; i < s.size(); i++) {
    v.push_back(abs(s[i] - s[i - 1]) + v.back());
  }
  ll ans = 0;
  for (int i = k - 1; i < v.size(); i++) {
    ans += v[i] - v[i - k + 1];
  }
  cout << ans;
}

小红的陡峭值（四）

小红定义一棵树的陡峭值为：每一条边连接的两个相邻节点，编号差值的绝对值之和；若一棵树只有 $1$个节点，则该树的陡峭值为 $0$。例如，对于一棵由 $3$个节点组成的树，若节点 $2$和节点 $3$连边，节点 $3$和节点 $1$连边，则该树的陡峭值为 $∣2−3∣+∣3−1∣=3$
现在小红拿到了一棵由 $n$​个节点组成的树，她准备断掉一条树边，使得形成两棵树。小红希望这两棵树的陡峭值尽可能的接近。请你求出这两棵树陡峭值之差的绝对值的最小值。

对于一颗树，DFS可以计算当前节点为根节点，其所在子树的陡峭值和$v_x$.

枚举断掉每个节点$i$何其父节点$f_i$的边

则有新的子树的的陡峭值为$v_i$

剩余的部分的陡峭值为整体的和 - 去掉的子树-断掉的边的权重

$newt = v_0 - v_i +|i-f_i|$

其中$v_0$是根节点的值（可以是任意一个点。

vector<int> adj[N + 1];
ll v[N + 1];
bool vis[N + 1];
int f[N + 1];
ll S = 0;
int n;

ll dfs(int x, int p) {
  f[x] = p;
  vis[x] = true;
  ll res = 0;
  for (int c : adj[x]) {
    if (!vis[c]) {
      ll lr = dfs(c, x);
      res += (lr + llabs((ll)x - c));
    }
  }
  v[x] = res;
  return res;
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    adj[i].clear();
    vis[i] = false;
    v[i] = 0;
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  ll rs = dfs(1, 0);
  S = rs;

  ll ans = LLONG_MAX;
  for (int x = 2; x <= n; x++) {
    int p = f[x];
    ll c = llabs(p - x);
    ll ori = S - v[x] - c;
    ll newt = v[x];
    ans = min(ans, abs(ori - newt));
  }

  cout << ans << "\n";
}

小红的陡峭值（五）（hard）

小红定义一个数组的陡峭值为：每两个相邻的元素，差值的绝对值之和。例如，数组 ${2,3,1}$的陡峭值是 $∣2−3∣+∣3−1∣=3$。
现在小红拿到了一个由 $n$ 个整数组成的数组${a_1,a_2,\dots,a_n}$，然后蒙眼打乱了数组。她希望你求出该数组陡峭值的期望。请将答案对$10^9+7$取模后输出。

陡峭值可以分解成两个元素相邻的组合的差值的求和

对于两个数$a_i,a_j$相邻，首先固定这两个数，剩下$n-1$个空的排列，同时两个数内部还有两个组合

则两个数相邻的情况有$2\times (n-1)!$种，在全部的情况下，有$n!$个排列

因此两个数$a_i,a_j$相邻的概率为$\frac{2\times (n-1)!}{n} = \frac{2}{n}$​

简化一下只考虑正序，不考虑reversed结果，则直接去掉一半组合

则期望为$E = \frac{2}{n}\sum (a_j-a_j)$​.

因此只需要求$1\leq i < j <n$时候$\sum (a_j-a_j)$

当$n=18$的时候直接$n^2$暴力

当n大了后可以用前缀和优化

$\sum_{i=1}^{j-1}a_j - a_i = (j-1)\cdot aj -\sum{i=1}^{j-1}a_i$

直接前缀和维护，计算这个式子就得到了对应的分子，分母则是$n$

求逆元做乘积得到结果

ll qpow(ll a, ll b, ll m) {
  ll res = 1 % m;
  a %= m;
  while (b > 0) {
    if (b & 1) res = (res * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}

ll inv(ll a, ll m) { return qpow(a, m - 2, m); }

void solve() {
  int n;
  cin >> n;
  vector<ll> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(all(arr));
  vector<ll> pre(n + 1, 0ll);
  for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + arr[i - 1];
  }
  ll cnt = 0;
  for (int j = 2; j <= n; j++) {
    ll tmp = arr[j - 1];
    ll lc = j - 1;
    cnt = (cnt + 1ll * lc * tmp - pre[j - 1]) % mod;
  }
  ll p = (2ll * cnt) % mod;
  ll iq = inv(n, mod);
  ll ans = (1ll * p * iq) % mod;

  cout << ans;
}