GYM 105264 C
题目描述
给定一个长度为 \(N\) 的数组 \(A\)，每次你可以令 \(A_i \leftarrow A_i+1\) 或 \(A_i-1\)。求进行至多 \(k\) 次操作后 \(A\) 中最少不同元素数量。
思路
首先对 \(A\) 进行排序。
令 \(dp_{i,j}\) 表示考虑前 \(i\) 个数，有 \(j\) 个不同的值时最多还能剩余几次操作。
很明显有 \(dp_{i,j}=\max \limits_{1\le l\le x\le i} \{dp_{l-1,j-1}+sum_i - sum_{x}-(i-x)\cdot A_x + (x - l)\cdot A_x - sum_{x-1}+sum_l\}\)。
这个式子中似乎只能优化 \(x\)，所以我们考虑怎么优化。
这里的 \(x\) 实际上就是在枚举变成哪个值，假设一开始我们不用下标而用值来表示。每次令 \(x\leftarrow x+1\)，这样做会使答案 \(+\le x的个数-> x的个数\)，一开始这个增量是负的，逐渐变大。而当增量 \(=0\) 时也就是最小值。
而哪个地方 \(=0\) 呢？此时 \(\le x的个数=> x的个数\)，也就是在 \(\lceil \frac{l+i}{2} \rceil\) 处。
空间复杂度 \(O(N^2)\)，时间复杂度 \(O(N^3)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 301;
int T, n, a[MAXN], ans;
ll k, sum[MAXN], dp[MAXN][MAXN];
void Solve() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= n; ++j) {
dp[i][j] = -1;
}
}
dp[0][0] = k;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
for(int l = 1; l <= i; ++l) {
dp[i][j] = max(dp[i][j], dp[l - 1][j - 1] + sum[(l + i + 1) / 2] + 1ll * a[(l + i + 1) / 2] * (i - (l + i + 1) / 2) - 1ll * a[(l + i + 1) / 2] * ((l + i + 1) / 2 - l) + sum[(l + i + 1) / 2 - 1] - sum[l - 1] - sum[i]);
}
}
}
for(int i = 1; i <= n; ++i) {
if(dp[n][i] >= 0) {
cout << i << "\n";
return;
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
for(cin >> T; T--; Solve()) {
}
return 0;
}
GYM 105264 E
题目描述
给定一个 \(N\) 个点的树，你要从中选出一个大小为 \(k\) 的子树出来，求这个子树的最小直径。
思路
由于此题允许 \(O(N^2)\) 的时间复杂度，所以考虑枚举子树的中心。
接着以该中心为根向下搜出深度为 \(i\) 的结点数 \(cnt_i\)，接着枚举直径长度除 \(2\)。由于这里直径可能长度为偶数，则此时中点在一条边上。所以我们把每条边也看作一个点（但不统计在 \(cnt\) 中）。找到第一个 \(\sum \limits_{i=0}^x cnt_i \ge k\) 的 \(x\)，并统计答案即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N^2)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2001;
int n, k, dep[MAXN], cnt[MAXN], ans;
vector<int> e[MAXN];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
cnt[dep[u]] += (u <= n);
for(int v : e[u]) {
if(v != fa) {
dfs(v, u);
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for(int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
e[u].push_back(n + i);
e[n + i].push_back(v);
e[v].push_back(n + i);
e[n + i].push_back(u);
}
ans = 2 * n;
for(int i = 1; i < 2 * n; ++i) {
for(int j = 1; j <= 2 * n; ++j) {
dep[j] = cnt[j] = 0;
}
dfs(i, 0);
int res = 0;
for(int j = 1; j <= 2 * n; ++j) {
res += cnt[j];
if(res >= k) {
ans = min(ans, j);
break;
}
}
}
cout << ans;
return 0;
}