邮寄
开场秒 B。
A 稍微退了一会儿，推出一个解法（后面发现假掉了）......
然后 CD，D 感觉是一个 SA。结果 SA 写错了，算法假掉了......
A 智乃的差分
分类讨论。
\(x > 0\)
最大值 \(= x\)，最小值 \(= 0\)
此时可以直接找一个不是 \(x\)，不是 \(0\) 的数来（严格次小值），然后其他的数从大往小排序。
其他情况
直接从大往小排序。
\(x < 0\)
std::sort(arr + 1, arr + n + 1);
\(x = 0\)
这是最复杂的情况。
先把所有的数的出现次数统计出来，然后按照出现次数 从多至少 排序。
如果数组的头部是 \(0\)，还得把这些 \(0\) 扔到后面。
排序部分参考：
//mp[x] 代表 x 的出现次数
bool cmp(int a, int b) {return (mp[a] == mp[b]? a > b : mp[a] > mp[b]);
}...sort(arr + 1, arr + n + 1, cmp);
if(arr[1] == 0) {rotate(arr + 1, arr + mp[0] + 1, arr + n + 1);
}
Code:
#include <bits/stdc++.h>
using namespace std;int t, n, x, arr[200020], brr[200020];
map<int, int> mp;bool check() {for(int i = 1; i <= n; i++) {if(arr[i] - arr[i - 1] == x) {return 0;}}return 1;
}bool cmp(int a, int b) {return (mp[a] == mp[b]? a > b : mp[a] > mp[b]);
}int main() {freopen("difference.in", "r", stdin);freopen("difference.out", "w", stdout);for(cin >> t; t--; ) {cin >> n >> x;for(int i = 1; i <= n; i++) {cin >> arr[i];}sort(arr + 1, arr + n + 1);if(check()) {cout << "yes" << '\n';for(int i = 1; i <= n; i++) {cout << arr[i] << " \n"[i == n];}goto nxt;}sort(arr + 1, arr + n + 1, greater<int>());if(arr[1] == x && arr[n] == 0) {for(int i = 2; i <= n; i++) {if(arr[i] != arr[1] && arr[i] != arr[n]) {swap(arr[1], arr[i]);break;}}}if(check()) {cout << "yes" << '\n';for(int i = 1; i <= n; i++) {cout << arr[i] << " \n"[i == n];}goto nxt;}for(int i = 1; i <= n; i++) {mp[arr[i]]++;}sort(arr + 1, arr + n + 1, cmp);if(arr[1] == 0) {rotate(arr + 1, arr + mp[0] + 1, arr + n + 1);}if(n & 1) {for(int i = 1, j = 1; i <= n; i++, j += 2) {if(j > n) {j -= n;}brr[j] = arr[i];}}else {for(int i = 1, j = 1; j <= n; i++, j += 2) {brr[j] = arr[i];}for(int i = n / 2 + 1, j = 2; j <= n; i++, j += 2) {brr[j] = arr[i];}}copy(brr + 1, brr + n + 1, arr + 1);if(check()) {cout << "yes" << '\n';for(int i = 1; i <= n; i++) {cout << arr[i] << " \n"[i == n];}goto nxt;}cout << "no" << '\n';nxt:;mp.clear();}return 0;
}
/*
4
10 0
9 9 9 9 9 3 3 3 3 3
10 0
9 9 9 9 9 9 3 3 3 3
10 0
0 0 0 0 0 0 0 0 0 0
403 -3
5 1 10 1 9 6 7 3 7 2 1 3 4 2 5 10 1 3 4 9 5 3 5 9 2 1 2 7 2 1 4 1 7 3 5 10 8 9 10 3 4 8 8 2 8 6 8 2 4 2 5 5 5 10 4 10 7 1 2 7 2 4 9 10 5 2 7 2 4 4 5 8 5 1 2 1 5 6 4 3 6 4 7 2 4 8 1 10 2 9 2 9 2 4 8 10 5 10 7 7 7 7 9 10 4 1 10 10 9 5 3 2 10 9 5 4 9 3 10 3 1 6 8 6 6 5 4 5 9 8 7 6 7 6 2 7 3 8 2 10 8 4 3 8 8 4 9 8 1 3 4 3 10 6 10 7 7 9 4 1 1 2 7 5 2 10 8 8 5 2 2 8 2 5 7 5 5 4 10 7 10 8 6 5 4 1 10 2 3 6 10 10 8 9 4 1 6 7 8 3 10 8 1 6 7 8 7 1 6 5 4 3 10 3 7 8 6 5 9 9 10 2 2 9 9 5 9 7 4 3 3 7 10 5 2 6 6 8 1 5 1 7 9 2 2 8 3 5 4 2 2 2 7 3 3 10 2 10 4 5 4 6 5 3 5 1 7 9 8 1 4 3 4 7 9 6 3 9 10 1 10 4 6 2 1 8 2 2 8 6 1 7 3 4 10 7 5 6 6 6 5 6 3 10 2 6 8 9 7 7 1 7 5 4 5 6 4 9 3 7 1 1 1 5 5 7 5 5 8 9 4 7 3 4 4 9 4 10 10 9 10 9 10 2 2 4 3 10 4 8 4 3 5 9 5 4 10 10 9 4 3 8 8 4 5 7 8 6 8 7 10 10 9 7 4 8 1 6 7 7 5 4 4 8 10 9 3 3 4 7 6 4 2 2 8 10 3 1 5 7 8 10 4
*/
B 牛牛的旅行
sb 离线处理板子题。
对于点权最大值和边权和分开处理。
点权最大值
这里的思想是经典的最小瓶颈路。
我们从小往大考虑每一个点：
然后，对于这个点，我们看所有与这个点有边的 已经考虑 的点。
组合数学计算这个点的贡献。
边权和
弱智题，一遍 DFS 稍微处理一下就可以了。
#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;const int kMod = int(1e9) + 7;int n, val[1000010], fa[1000010], sz[1000010], u, v, id[1000010], is[1000010], ans, sb[1000010];
vector<int> to[1000010];bool cmp(int x, int y) {return val[x] < val[y];
}int findfa(int x) {return fa[x] == x? x : (fa[x] = findfa(fa[x]));
}void unionn(int x, int y) {x = findfa(x), y = findfa(y);if(x == y) {return ;}if(sz[x] < sz[y]) {swap(x, y);}sz[x] += sz[y], fa[y] = x;
}void DFS(int x = 1, int pa = 0) {sb[x] = 1;for(auto i : to[x]) {if(i != pa) {DFS(i, x);sb[x] += sb[i];}}ans = (ans - 2 * sb[x] * (n - sb[x]) % kMod + kMod) % kMod;
}signed 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; i <= n; i++) {cin >> val[i], fa[i] = id[i] = i, sz[i] = 1;}for(int i = 1; i < n; i++) {cin >> u >> v;to[u].push_back(v);to[v].push_back(u);}stable_sort(id + 1, id + n + 1, cmp);for(int i = 1; i <= n; i++) {int tot = 1;is[id[i]] = 1;for(auto j : to[id[i]]) {if(is[j]) {tot += sz[findfa(j)];}}for(auto j : to[id[i]]) {if(is[j]) {ans = (ans + val[id[i]] * sz[findfa(j)] % kMod * (tot - sz[findfa(j)])) % kMod;}}ans = (ans + val[id[i]] * (tot - 1)) % kMod;for(auto j : to[id[i]]) {if(is[j]) {unionn(id[i], j);}}}DFS();cout << ans << '\n';return 0;
}
C 第 \(K\) 排列
第十四剪枝。
Part 1
我们定义 \(dp_{i, j}\) 表示当前在 \([i \cdots n]\) 的范围内的最大权值。
Part 2
放弃一个即使最大化权值也无法达到 \(x\) 的状态... 这应该很好做的。
Part 3
放弃了这些状态之后，剩下的状态应该不会很多... 直接暴搜，在丢弃掉所有的无用状态后，剩下的状态会极其精确，所以真正的搜索数量其实真的不多，也就 \(O(NK)\) 吧。
#include <bits/stdc++.h>
using namespace std;const char c[] = {'P', 'O', 'N', 'I'}, c2[] = {'N', 'O', 'I', 'P'};int n, rc, k, v[256][256], dp[1010][256], cnt;
string s, ans;void DFS(int x, int lst, int val) {if(x > n) {if(val < rc) {return ;}cnt++;if(cnt == k) {cout << ans << '\n';exit(0);}return ;}if(val + dp[x - 1][lst] < rc) {return ;}for(int i = 0; i < 4; i++) {if(s[x] == '?' || s[x] == c[i]) {ans += c[i];DFS(x + 1, i, val + v[c[lst]][c[i]]);ans.pop_back();}}
}int main() {freopen("permutation.in", "r", stdin);freopen("permutation.out", "w", stdout);cin >> n >> rc >> k >> s;n = s.size();s = ' ' + s;for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {cin >> v[c2[i]][c2[j]];}}for(int j = 0; j < 4; j++) {if(s[n] == '?' || s[n] == c[j]) {dp[n][j] = 0;}else {dp[n][j] = -1e8;}}for(int i = n - 1; i >= 1; i--) {for(int j = 0; j < 4; j++) {if(s[i] == '?' || s[i] == c[j]) {for(int k = 0; k < 4; k++) {dp[i][j] = max(dp[i][j], dp[i + 1][k] + v[c[j]][c[k]]);}}else {dp[i][j] = -1e8;}//cout << dp[i][j] << ' ';}//cout << '\n';}ans += c[0];DFS(2, 0, 0);ans.pop_back();ans += c[1];DFS(2, 1, 0);ans.pop_back();ans += c[2];DFS(2, 2, 0);ans.pop_back();ans += c[3];DFS(2, 3, 0);ans.pop_back();cout << -1 << '\n';return 0;
}
/*
4 3 108
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
*/
D 牛牛的border
如果你不会后缀数组（SA）
先放一张图：
倍增排序的思想是，我们先把一个字符排好序，然后就可以利用双关键字排序（去重离散化），然后就可以完美进行后缀排序了。
实现（用下面的代码，输入 adsadsadsadsads，即可获得上面的输出）：
#include <bits/stdc++.h>
using namespace std;struct node {int a1, a2, id;
}arr[100010];int n, bc[256], val[256], cnt, sa[100010], rk[100010], ht[100010];
string s;void lfsort(int x) {cout << "Concat the substrings of x and x + " << x << "(may DNE):" << '\n';for(int i = 1; i <= n; i++) {arr[i] = {rk[i], (i + x <= n? rk[i + x] : 0), i};cout << arr[i].a1 * 10 + arr[i].a2 << ' ';}cout << '\n';sort(arr + 1, arr + n + 1, [](node a, node b) {return a.a1 == b.a1? a.a2 < b.a2 : a.a1 < b.a1;});int tmp = 0;for(int i = 1; i <= n; i++) {tmp += arr[i].a1 != arr[i - 1].a1 || arr[i].a2 != arr[i - 1].a2;rk[arr[i].id] = tmp;}
}char sufc(int id, int x) {return s[id + x - 1];
}int main() {cin >> s;n = s.size();for(auto i : s) {bc[int(i)]++;}s = ' ' + s;for(int i = 'a'; i <= 'z'; i++) {if(bc[i]) {val[i] = ++cnt;}}for(int i = 1; i <= n; i++) {rk[i] = val[int(s[i])];}cout << '\n';cout << "Initiallize:" << '\n';for(int i = 1; i <= n; i++) {cout << rk[i] << ' ';}cout << '\n' << '\n';for(int i = 1; ; i <<= 1) {lfsort(i);cout << "The order of s[x ... x + " << (i << 1) << "]:" << '\n';for(int i = 1; i <= n; i++) {cout << rk[i] << ' ';}cout << '\n' << '\n';if(i > n) {break;}}for(int i = 1; i <= n; i++) {sa[rk[i]] = i;}for(int i = 1; i <= n; i++) {ht[rk[i]] = max(ht[rk[i - 1]] - 1, 0);for(; sufc(i, ht[rk[i]] + 1) == sufc(sa[rk[i] - 1], ht[rk[i]] + 1); ht[rk[i]]++) {}}cout << " Rank = ";int cnt = 45;for(int i = 1; i <= n; i++) {cnt += 2;cnt += rk[i] >= 10;cnt += rk[i] >= 100;cnt += rk[i] >= 1000;cnt += rk[i] >= 10000;cnt += rk[i] >= 100000;cout << rk[i] << ' ';}cout << '\n';for(; cnt--; ) {cout << '-';}cout << '\n';for(int i = 1; i <= n; i++) {//cout << "height[i] = " << ht[i] << ',' << "sa[i] = " << sa[i] << ' ';cout << "height[" << i << "]";if(i < 10) {cout << ' ';}if(i < 100) {cout << ' ';}if(i < 1000) {cout << ' ';}if(i < 10000) {cout << ' ';}if(i < 100000) {cout << ' ';}cout << " = " << ht[i];if(ht[i] < 10) {cout << ' ';}if(ht[i] < 100) {cout << ' ';}if(ht[i] < 1000) {cout << ' ';}if(ht[i] < 10000) {cout << ' ';}if(ht[i] < 100000) {cout << ' ';}cout << ",sa[" << i << "]";if(i < 10) {cout << ' ';}if(i < 100) {cout << ' ';}if(i < 1000) {cout << ' ';}if(i < 10000) {cout << ' ';}if(i < 100000) {cout << ' ';}cout << " = " << sa[i];if(sa[i] < 10) {cout << ' ';}if(sa[i] < 100) {cout << ' ';}if(sa[i] < 1000) {cout << ' ';}if(sa[i] < 10000) {cout << ' ';}if(sa[i] < 100000) {cout << ' ';}cout << ' ';cout << s.substr(sa[i]) << '\n';}return 0;
}
我们可以迅速知道一件事：我们要统计每一个后缀在另一个后缀中的出现次数。
你会想到什么，当然是 \(height\) 数组啊！
只要 \(height\) 永远不小于某一个值（\(lcp(sa_i, sa_j) = \min \limits_{k = i + 1}^j height_k\)），这个后缀就会一直出现，否则，它就无法变回去了。
所以我们可以按照 \(height\) 顺序合并后缀，并在合并过程中维护答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;struct node {int a1, a2, id;
}arr[100010];int n, sa[100010], rk[100010], ht[100010], cur, fa[100010], sz[100010], ans;
vector<int> num[100010];
string s, t;void lfsort(int x) {for(int i = 1; i <= n; i++) {arr[i] = {rk[i], (i + x <= n? rk[i + x] : 0), i};}stable_sort(arr + 1, arr + n + 1, [](node a, node b) {return a.a1 == b.a1? a.a2 < b.a2 : a.a1 < b.a1;});int tmp = 0;for(int i = 1; i <= n; i++) {rk[arr[i].id] = tmp += (arr[i].a1 != arr[i - 1].a1 || arr[i].a2 != arr[i - 1].a2);}
}int sufc(int x, int c) {return s[sa[x] + c - 1];
}void cal() {sort(t.begin(), t.end());int l = unique(t.begin(), t.end()) - t.begin();for(int i = 1; i <= n; i++) {rk[i] = lower_bound(t.begin(), t.begin() + l, s[i]) - t.begin() + 1;}for(int x = 1; ; x <<= 1) {lfsort(x);if(x > n) {break;}}for(int i = 1; i <= n; i++) {sa[rk[i]] = i;}for(int i = 1; i <= n; i++) {if(rk[i] == 1) {continue;}ht[rk[i]] = max(0ll, ht[rk[i - 1]] - 1);for(; sufc(rk[i], ht[rk[i]] + 1) == sufc(rk[i] - 1, ht[rk[i]] + 1); ht[rk[i]]++) {}}for(int i = 1; i <= n; i++) {num[ht[i]].push_back(i);}
}int findfa(int x) {return fa[x] == x? x : (fa[x] = findfa(fa[x]));
}void unionn(int x, int y) {x = findfa(x), y = findfa(y);if(x == y) {return ;}if(sz[x] < sz[y]) {swap(x, y);}cur -= sz[x] * (sz[x] + 1) / 2;cur -= sz[y] * (sz[y] + 1) / 2;fa[y] = x, sz[x] += sz[y];cur += sz[x] * (sz[x] + 1) / 2;
}signed main() {freopen("border.in", "r", stdin);freopen("border.out", "w", stdout);cin >> n >> s;n = s.size(), t = s;s = ' ' + s;cal();iota(fa, fa + n + 1, 0);fill(sz, sz + n + 1, 1);for(int i = n; i; i--) {cur++;for(auto j : num[i]) {unionn(j, j - 1);}ans += cur * i;}//*for(int i = 1; i <= n; i++) {ans -= i * (n - i + 1);}//*/cout << ans << '\n';return 0;
}
