rk4，\(0+30+40+30=100\)，T1挂惨了
#A. 智乃的差分
分类讨论，由于 \(a_i\ge0\)，当 \(x < 0\) 时，可以直接升序排列
当 \(x > 0\) 时，大部分情况下可以降序排列，但可能会出现 \(a_1=x\) 的情况，就可以找到第一个不为 \(x\) 且不为 \(0\) 的数，swap 掉即可
然后是最麻烦的 \(x=0\)，当出现最多的数出现次数大于 \(\lceil\frac{n}{2}\rceil\)，一定无解，如果等于，还要分类。如果这个最多的数不是 \(0\)，就直接和其他数插空放，如果是 \(0\)，当 \(n\) 是偶数时，可以将所有偶数位放 \(0\)，其他位插空放，如果时奇数，则无解
否则，由于最大出现次数小于 \(\lceil\frac{n}{2}\rceil\)，排序后直接按顺序先放奇数位再放偶数位即可，此时如果第一位等于 \(x\)，就把数组 reverse 掉
// BLuemoon_
#include <bits/stdc++.h>using namespace std;const int kMaxN = 1e5 + 5;int t, n, a[kMaxN], c[kMaxN], x, mx = -1, k;
map<int, int> mp;int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("difference.in", "r", stdin), freopen("difference.out", "w", stdout);for (cin >> t; t; t--, mp.clear(), mx = -1) {cin >> n >> x;for (int i = 1; i <= n; i++) {cin >> a[i];}if (n == 1) {cout << (x == a[1] ? "no" : "yes") << '\n';(x != a[1]) && (cout << a[1] << '\n');continue;}if (x < 0) {sort(a + 1, a + n + 1);} else if (x > 0) {sort(a + 1, a + n + 1, greater<int>());bool flag = 1;if (a[1] == x) {for (int i = 2; i <= n; i++) {if (a[i] != a[1]) {(a[i] == 0) ? (flag = 1) : (swap(a[1], a[i]), flag = 0);break;}}if (flag) {cout << "no\n";continue;}}} else {int e = (n / 2) + (n % 2), v;for (int i = 1; i <= n; i++) {mp[a[i]]++, (mx < mp[a[i]]) && (mx = mp[a[i]], v = a[i]);}if (mx > e) {cout << "no\n";continue;}if (mx == e) {if (v == x) {if (n & 1) {cout << "no\n";continue;}for (int i = 2; i <= n; i += 2) {c[i] = v;}for (int i = 1, j = 1; i <= n; i += 2, j++) {for (; a[j] == v; j++) {}c[i] = a[j];}cout << "yes\n";for (int i = 1; i <= n; i++) {cout << c[i] << ' ';}cout << '\n';continue;}for (int i = 1; i <= n; i += 2) {c[i] = v;}for (int i = 2, j = 1; i <= n; i += 2, j++) {for (; a[j] == v; j++) {}c[i] = a[j];}} else {sort(a + 1, a + n + 1), k = 1;if (a[1] == x) {reverse(a + 1, a + n + 1);}for (int i = 1; i <= n; i += 2, k++) {c[i] = a[k];}for (int i = 2; i <= n; i += 2, k++) {c[i] = a[k];}}for (int i = 1; i <= n; i++) {a[i] = c[i];}}cout << "yes\n";for (int i = 1; i <= n; i++) {cout << a[i] << ' ';}cout << '\n';}return 0;
}
#B. 牛牛的旅行
比较典的拆贡献题，显然对于总长度和总最大值可以分开解决，总长度可以使用换根 dp，而最大值部分稍麻烦一些
对于每一个点，定义其“影响域”为，一个最大的包含此点的连通块，其内任意路径过此点的两点之间的 \(max_{val}\) 为这个点的权值
然后对于“影响域”内的每一个点，它到“影响域”内其他点路径经过关键点的个数乘上关键点的权值。即令关键点为 \(x\)，\(y\) 为“影响域”内与 \(x\) 相连的点，那么 \(x\) 的贡献为 \(\sum (size_{x}-sz_{y})\times sz_{y}\)，其中 \(size\) 为“影响域”大小，\(sz\) 为“影响域”内的子树大小
按权值升序排序后计算贡献即可
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const LL kP = 1e9 + 7;
const int kMaxN = 1e6 + 5;struct P {LL id, x;bool operator<(const P& _) const {return x < _.x;}
};int n;
P a[kMaxN];
LL ans, sz[kMaxN], fa[kMaxN];
bool vis[kMaxN];
vector<int> g[kMaxN];int F(int x) {return (fa[x] == x) ? x : (fa[x] = F(fa[x]));
}
void DFS(int u, int fa) {sz[u] = 1;for (int v : g[u]) {if (v != fa) {DFS(v, u), sz[u] += sz[v], ans -= sz[v] * (n - sz[v]) % kP, (ans += kP) %= kP;}}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("tour.in", "r", stdin), freopen("tour.out", "w", stdout);cin >> n;for (int i = 1, x; i <= n; i++) {cin >> x, a[i] = (P){i, x}, fa[i] = i;}for (int i = 1, u, v; i < n; i++) {cin >> u >> v, g[u].push_back(v), g[v].push_back(u);}DFS(1, 0), sort(a + 1, a + n + 1);fill(sz + 1, sz + n + 1, 1);for (int u = 1; u <= n; u++) {for (int v : g[a[u].id]) {if (vis[v]) {(ans += (a[u].x * sz[F(a[u].id)] % kP) * sz[F(v)] % kP) %= kP;int X = F(a[u].id), Y = F(v);(X != Y) && (fa[X] = Y, sz[Y] += sz[X]);}}vis[a[u].id] = 1;}cout << (ans << 1) % kP << '\n';return 0;
}
#C. 第K排列
std 写什么【】矩阵乘法啊，还是我们 csr 有实力
令 \(dp_{i,j}\) 为已经填了 \(i\sim n\) 位，第 \(i\) 位填了 \(j\) 的最大值，直接枚举转移即可
然后由于 \(k\) 只有 \(1000\)，我们可以 DFS 暴力枚举所有填数序列，当当前值已经大于 \(k\) 时直接剪枝掉，就可以愉快的卡过去了
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const int kMaxN = 1e3 + 5;int n, x, k, a[5][5];
LL dp[kMaxN][5];
map<char, int> mp;
string s, ans, tmp = "NOIP", O = "INOP";void DFS(int t, LL e) {if (t > n) {if (e >= x) {if (!--k) {cout << ans.substr(1) << '\n', exit(0);}}return;}if (s[t] == '?') {for (int i = 3; ~i; i--) {LL f = dp[t][i];(t > 1) && (f += a[mp[ans[t - 1]]][i]);if (f + e >= x) {LL cur = e;(t > 1) && (cur += a[mp[ans[t - 1]]][i]);ans[t] = O[i], DFS(t + 1, cur);}}return;}int i = mp[s[t]];ans[t] = s[t];LL f = dp[t][i];(t > 1) && (f += a[mp[ans[t - 1]]][i]);if (f + e >= x) {LL cur = e;(t > 1) && (cur += a[mp[ans[t - 1]]][i]);ans[t] = O[i], DFS(t + 1, cur);}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), mp['I'] = 0, mp['N'] = 1, mp['O'] = 2, mp['P'] = 3;freopen("permutation.in", "r", stdin), freopen("permutation.out", "w", stdout);cin >> n >> x >> k >> s, s = ' ' + s;for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {cin >> a[mp[tmp[i]]][mp[tmp[j]]];}}fill(dp[0], dp[kMaxN - 1], -1e18);(s[n] == '?') ? (dp[n][0] = dp[n][1] = dp[n][2] = dp[n][3] = 0) : (dp[n][mp[s[n]]] = 0);for (int i = n - 1; i; i--) {if (s[i] == '?') {for (int j = 0; j < 4; j++) {for (int k = 0; k < 4; k++) {dp[i][j] = max(dp[i][j], dp[i + 1][k] + a[j][k]);}}} else {for (int j = 0; j < 4; j++) {dp[i][mp[s[i]]] = max(dp[i][mp[s[i]]], dp[i + 1][j] + a[mp[s[i]]][j]);}}}ans.resize(n + 1), DFS(1, 0);cout << "-1\n";return 0;
}
#D. 牛牛的 border
std 写什么【】后缀数组啊，还是我们 csr 有实力
直接大力 SAM，由于两个相同的子串可以唯一确定一个子串的一个 border。所以令每种字符串长度为 \(len\)，出现次数为 \(p\)，那么它的贡献为 \(len \times \mathrm{C}_{p}^{2}\)
建出 \(link\) 树后进行树形 dp 算式子即可
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const int kMaxN = 1e5 + 5, kMaxC = 26 + 5;LL n, ans;struct SAM {struct P {LL lnk, maxl, to[kMaxC], sz;vector<int> g;};int tot, lst;P s[kMaxN << 1];SAM() {lst = tot = 0, s[0].maxl = 0, s[0].lnk = -1;}void Insert(int ch, int c, int p = 0) {for (s[c].maxl = s[p = lst].maxl + 1, s[c].sz = 1; (p != -1) && (!s[p].to[ch]); s[p].to[ch] = c, p = s[p].lnk) {}if (p == -1) {return s[lst = c].lnk = 0, void();}int ed = s[p].to[ch];if (s[p].maxl == s[ed].maxl + 1) {return s[lst = c].lnk = ed, void();}for (s[++tot] = s[ed], s[tot].sz = 0, s[tot].maxl = s[p].maxl + 1; (~p) && (s[p].to[ch] == ed); s[p].to[ch] = tot, p = s[p].lnk) {}s[ed].lnk = s[lst = c].lnk = tot;}void Update(string str, int sz) {for (int i = 0; i < sz; i++) {Insert(str[i] - 'a' + 1, ++tot);}}void Link() {for (int i = 0; i <= tot; i++) {(~s[i].lnk) && (s[s[i].lnk].g.push_back(i), 1);}}void DFS(int u, int fa) {for (int v : s[u].g) {DFS(v, u), s[u].sz += s[v].sz;}ans += (s[u].maxl + s[fa].maxl + 1) * (s[u].maxl - s[fa].maxl) * s[u].sz * (s[u].sz - 1) / 4;}
};SAM sam;
string s;int main() {freopen("border.in", "r", stdin), freopen("border.out", "w", stdout);cin >> n >> s, sam.Update(s, n), sam.Link(), sam.DFS(0, 0);cout << ans << '\n';return 0;
}
