因为补题的时候，发现网上找不到一篇题解（补题补的很是痛苦），所以写了一篇，希望能帮助之后补这场比赛的人~~~
有些太简单签到就没写，还有 \(2-3\) 题还没补出来，之后补了会加上去。
A. Gym Plates
解题思路
比较裸的一个状压 DP，我们考虑把数字的选取次数压到 DP 里面去，显然 \(0\backsim 9\) 这些数的状态会构成一个 \(10\) 位的 \(3\) 进制数。然后正常转移即可：
转移的时候维护好 \(state\) 的合法性即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int pw[20];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
pw[0] = 1;
for (int i = 1; i <= 10; i++) {
pw[i] = pw[i - 1] * 3;
}
while (t--) {
int n;
cin >> n;
vector<LL> w(n + 1);
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
vector<LL> dp(pw[10], -1);
dp[0] = 0;
for (int i = 0; i < n; i++) {
vector<LL> ndp(pw[10], -1);
for (int j = 0; j < pw[10]; j++) {
if (dp[j] == -1) continue;
ndp[j] = max(ndp[j], dp[j]);
vector<int> cnt(10, 0);
LL v = w[i + 1];
while (v) {
cnt[v % 10]++;
v /= 10;
}
int state = 0;
bool ok = true;
for (int k = 9; k >= 0; k--) {
int p = j / pw[k] % 3;
if (p + cnt[k] > 2) {
ok = false;
break;
}
state = state * 3 + p + cnt[k];
}
if (ok) {
ndp[state] = max(ndp[state], dp[j] + w[i + 1]);
}
}
dp = ndp;
}
cout << *max_element(dp.begin(), dp.end()) << "\n";
}
return 0;
}
B. Convarge To 1
解题思路
首先我们设 \(t_i\) 表示每个位置的数第一次变为 \(1\) 的操作次数，那么对于一个查询 \([l,r]\)，这个区间全变成 \(1\) 的最早操作时间 \(\iff\) \(\max_{l\leq i \leq r}t_i\)。问题就变成一个静态区间查询最大值问题了，可以采用 \(ST\) 表解决。
然后问题变成了我们如何求出每一个 \(t_i\)，如果根据题目的模拟，我们不难想到预处理出每个数的最大质因子，然后还要利用堆，我们想一下最坏复杂度是多少，每个数最多会被除 \(20\) 多次，加上堆的 \(\log\)，我们复杂度是 \(O(n\log^2 n)\)，显然不行。
我们考虑优化堆的这个 \(\log\)，我们可以采用递推的方法，因为我们的数是越来越小的，我们可以倒过来做，用一个 \(g[i]\) 维护值为 \(i\) 的所有数，然后它们都会进行操作后变到 \(g[i/mip_i]\) 里。
而且我们发现，当一个数变为质数了，那么下一次它一步一定会变到 \(1\)，那么当 \(i\) 不是质数，其实我们并不需要管里面数的顺序，因为它们整体的时间都要加上 \(g[i].size()\)。只有当 \(i\) 为质数了，说明它下一步要变成 \(1\) 了， 我们在考虑它的顺
序，此时我们在对 \(g[i]\) 按下标排序。
我们来分析一下这个复杂度，首先我们不管排序，我们知道每个数最多被除 \(\log\) 多次，那么相当于我们每个数最多被遍历 \(\log\) 次，故这一块的复杂度是 \(O(n\log n)\)，我们在考虑排序，我们只有当 \(i\) 是质数的时候才去排序，而每一个数最多只会
在自身变成质数的时候才会进行排序，所以我们知道了每个数最多被排序一次，所以这一块的复杂度也是 \(O(n\log n)\) 的，所以我们总体复杂度就是 \(O(n\log n)\)的。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int mip[N], a[N], t[N], lg[N];
int f[N][22];
vector<int> g[N];
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!mip[i]) {
mip[i] = i;
for (int j = 2 * i; j <= n; j += i) {
mip[j] = i;
}
}
}
}
void init_st(int n) {
for (int j = 0; j <= lg[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (!j) f[i][j] = t[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
int query(int l, int r) {
int k = lg[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin >> n >> q;
int mx = 0;
for (int i = 1; i <= n; i++) {
if (i > 1) lg[i] = lg[i / 2] + 1;
cin >> a[i];
mx = max(mx, a[i]);
g[a[i]].push_back(i);
}
init(mx);
int tot = 0;
for (int i = mx; i >= 2; i--) {
if (g[i].size() == 0) continue;
if (mip[i] == i) {
sort(g[i].begin(), g[i].end());
}
for (auto v : g[i]) {
tot++;
if (mip[i] == i) t[v] = tot;
else {
g[i / mip[i]].push_back(v);
}
}
}
init_st(n);
while (q--) {
int l, r;
cin >> l >> r;
cout << query(l, r) << "\n";
}
return 0;
}
C. Tree Permutation
解题思路
首先这类期望题，一眼看上去就是 DP 不了的，我们考虑推公式或者直接算贡献。
我们发现答案其实就是 \(\frac{sum}{n!}\)，其中 \(sum\) 是所有情况下所走的路径和。
我们考虑一下如何计算 \(sum\)，我们可以考树上任意一个点对 \((u,v)\) 对答案产生的贡献：如果 \(u\rightarrow v\)，那么 \(u,v\) 填的数必须是如下几种情况之一：
- \((1,2)\)
- \((2,3)\)
- \(.....\)
- \((n-1,n)\)
那么剩下的 \(n-2\) 个位置还有 \((n-2)!\) 中排列方式，那么这 \((u,v)\) 点对产生的贡献就是：\(dis(u,v)\times (n-1)\times (n-2)!=dis(u,v)\times (n-1)!\)
故求 \(\frac{sum}{n!}\iff \frac{\sum_{i=1}^n\sum_{j=1}^ndis(i,j)\times (n-1)!}{n!}=\frac{\sum_{i=1}^n\sum_{j=1}^ndis(i,j)}{n}\)
所以问题被转化为一个经典的问题，求树上任意两点的距离之和，这是一个经典的换根 DP。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
vector<int> g[N];
LL dp[N];
int sz[N];
void dfs1(int u, int fa) {
dp[u] = 0, sz[u] = 1;
for (auto v : g[u]) {
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
dp[u] += dp[v];
}
dp[u] += sz[u] - 1;
}
void dfs2(int u, int fa) {
for (auto v : g[u]) {
if (v == fa) continue;
dp[v] = dp[u] + sz[1] - 2 * sz[v];
dfs2(v, u);
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0);
double ans = 0;
for (int i = 1; i <= n; i++) {
ans += dp[i];
}
cout << fixed << setprecision(12) << ans / n << "\n";
}
return 0;
}
H. Yaser In Baradah
解题思路
直接用 set + multiset 维护就好了。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
set<int> pos;
multiset<LL> val;
vector<LL> vgn(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
vgn[i] = x;
pos.insert(i);
val.insert(x);
}
cout << *val.rbegin() << "\n";
int Q;
cin >> Q;
while (Q--) {
int s;
cin >> s;
auto it = pos.upper_bound(s);
vgn[*it] += vgn[s];
pos.erase(pos.find(s));
val.insert(vgn[*it]);
cout << *val.rbegin() << "\n";
}
}
return 0;
}
J. Completely Balanced
解题思路
如果我们知道了数组最后的中位数，那么 \(X\) 是可以被算出来的：\(\frac{sum+X}{n+1}=mid\)
我们考虑加入一个数之后，数组的中位数可以是哪些数。
- 是原先数组中的数：把数组排序，那么 \(a[(n+2) / 2]\)，\(a[(n+2) / 2 - 1]\) 都有可能成为中位数。
- 是新加入的那个数 \(X\)。
我们只要依次检查这三种情况，取最小的 \(ans\) 即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<LL> a(n + 1);
LL sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
n += 1;
sort(a.begin() + 1, a.end());
// 1. 考虑中位数是原先的数字
int mid = (n + 1) / 2;
// 那么 x, a[mid] , a[mid - 1] 都有可能成为中位数
LL ans = 2e18;
LL x1 = (n * a[mid] - sum);
auto check = [&](LL x, LL y) {
vector<LL> b = a;
b.push_back(x);
sort(b.begin() + 1, b.end());
return b[mid] == y && (sum + x) % n == 0;
};
if (check(x1, a[mid])) ans = min(ans, x1);
if (mid - 1 >= 1) {
LL x2 = (n * a[mid - 1] - sum);
if (check(x2, a[mid - 1])) ans = min(ans, x2);
}
if (sum % (n - 1) == 0) {
LL x = sum / (n - 1);
if (check(x, x)) ans = min(ans, x);
}
cout << ans << "\n";
}
return 0;
}
K. Sam-Oh, the funny coach
解题思路
我们可以对于每一个字符串都维护一个长度最多为 \(26\) 的数组，存放每种字母出现的区间。
询问的时候，依次让两个字符串所在的区间求交，即可算出答案。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<array<int, 3>> g[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
int p = j;
while (p < m && s[j] == s[p]) p++;
g[i].push_back({j + 1, p, s[j] - 'a'});
j = p - 1;
}
}
int Q;
cin >> Q;
while (Q--) {
int p1, p2;
cin >> p1 >> p2;
vector<array<int, 3>> &it1 = g[p1], &it2 = g[p2];
vector<array<int, 2>> cur[26];
for (auto &[l, r, t] : it1) {
cur[t].push_back({l, r});
}
int ans = 0;
for (auto &[l, r, t] : it2) {
if (cur[t].size()) {
int L = cur[t][0][0], R = cur[t][0][1];
ans += max(0, min(R, r) - max(L, l) + 1);
}
}
cout << ans << "\n";
}
return 0;
}
L. Trip Discount
解题思路
首先考虑 \(m\) 次操作，本质是一个路径加，我们可以采用树上差分的方法，预处理出每个边被加的次数，那么最终我们每个边的最终花费就是 \(w\times d[i]\)，其中 \(d[i]\) 表示这条边被加的次数。
现在问题变成了，我们要选择 \(k\) 个点，然后可以使得这 \(k\) 个点任意两个点的路径边权全置成 \(0\)，考虑到 \(k\) 最大只有 \(1000\)。这类树上选点集的问题，我们可以想到用树上背包去做。
我们设 \(dp[i][j]\) 表示在以 \(i\) 为根的子树里面，选了 \(j\) 个点，可以免去去的最大边权贡献之和是多少。转移的时候，我们就类似树上背包的转移，枚举这棵子树选了几个点，依次合并其所有儿子的子树。
对于 \((u,v)\) 这条边要产生贡献，当且仅当 \(dp[v][j]\) 中的 \(j>0\) 且 \(j\not= k\)，这样一定会在 \(v\) 的子树外面选一个点，和 \(v\) 子树内有一个点，这两个点的路径一定会经过 \((u,v)\) 这条边。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 1e4 + 10, M = 1010;
const LL INF = 1e18;
vector<array<int, 2>> g[N];
int dep[N], f[N][16], d[N], val[N], sz[N];
LL dp[N][M];
int n, k, m;
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
for (auto &[v, w] : g[u]) {
if (v == fa) continue;
f[v][0] = u;
val[v] = w;
for (int i = 1; i <= 15; i++) {
f[v][i] = f[f[v][i - 1]][i - 1];
}
dfs(v, u);
}
}
void self(int u, int fa) {
for (auto &[v, w] : g[u]) {
if (v == fa) continue;
self(v, u);
d[u] += d[v];
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = 15; i >= 0; i--) {
if (dep[f[a][i]] >= dep[b]) {
a = f[a][i];
}
}
if (a == b) return a;
for (int i = 15; i >= 0; i--) {
if (f[a][i] != f[b][i]) {
a = f[a][i];
b = f[b][i];
}
}
return f[a][0];
}
void DFS(int u, int fa) {
sz[u] = 1;
dp[u][0] = dp[u][1] = 0;
for (auto [v, w] : g[u]) {
if (v == fa) continue;
DFS(v, u);
LL cost = 1LL * d[v] * w;
static LL tmp[M];
for (int i = 0; i <= min(k, sz[u] + sz[v]); i++) tmp[i] = -INF;
for (int i = 0; i <= min(k, sz[u]); i++) {
for (int j = 0; j <= sz[v] && i + j <= k; j++) {
tmp[i + j] = max(tmp[i + j], dp[u][i] + dp[v][j] + (j && j != k) * cost);
}
}
sz[u] += sz[v];
for (int i = 0; i <= min(k, sz[u]); i++) {
dp[u][i] = tmp[i];
}
}
}
void solve() {
cin >> n >> k >> m;
for (int i = 1; i <= n; i++) g[i].clear(), d[i] = val[i] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = -INF;
}
}
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
while (m--) {
int u, v;
cin >> u >> v;
d[u]++, d[v]++, d[LCA(u, v)] -= 2;
}
self(1, 0);
LL ans = 0;
for (int i = 1; i <= n; i++) {
ans += 1LL * val[i] * d[i];
}
DFS(1, 0);
cout << ans - dp[1][k] << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
- Programming Collegiate Contest HIAST 2023programming collegiate contest hiast 2023 programming collegiate contest programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate contest harbin