题解
知识点：贪心，构造。
注意到有 \(1\) 就一定能构造。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n, k;
cin >> n >> k;
bool ok = 0;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
ok |= x;
}
if (ok) cout << "YES" << '\n';
else cout << "NO" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
题解
知识点：枚举，双指针。
用对撞指针，枚举左侧 \(1\) 和 右侧 \(0\) ，一次操作能消除一对。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
int l = 1, r = n;
int cnt = 0;
while (l <= r) {
while (l <= r && a[l] == 0)l++;
while (l <= r && a[r] == 1)r--;
if (l <= r) {
l++;
r--;
cnt++;
}
}
cout << cnt << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题解
知识点：枚举。
容易发现，我们可以通过操作将序列变成非减序列，只要我们从左到右操作每组 \(a_i<a_{i-1}\) 的 \(a_i\) ，使 \(a_i \geq a_{i-1}\) 。这样的相邻数对之差大于 \(i\) 的不会超过 \(n-i\) 组，即第 \(i\) 次操作修改的一定小于等于 \(i\) ，因此我们一定可以通过 \(n\) 次操作修改所有这样的数对。
把所有相邻两数的差带着下标从小到大排序输出下标就行。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
vector<pair<int, int>> v;
v.push_back({ 0,1 });
for (int i = 2;i <= n;i++) {
v.push_back({ a[i - 1] - a[i], i });
}
sort(v.begin(), v.end());
for (auto [i, j] : v) cout << j << ' ';
cout << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题解
知识点：树形dp，贪心。
此题重点在于如何分配路径到子节点。
显然，为了保证子节点路径数至多相差 \(1\) ，若父节点有 \(p\) 或 \(p+1\) 条路径，那么 \(s\) 个子节点可能的路径数只有 \(\lfloor \frac{p}{s} \rfloor\) 或 \(\lfloor \frac{p}{s} \rfloor + 1\) 。
- \(s>2\) 和 \(s=1\) 时，显然成立。
- \(s = 2\) 时， \(p\) 能被整除时显然成立。
- \(s = 2\) 时， \(p\) 不能被整除时 \(p+1\) 一定能被整除，但只有 \(\lfloor \frac{p}{s} \rfloor + 1\) 一种合法情况，\(p\) 有 \(\lfloor \frac{p}{s} \rfloor\) 或 \(\lfloor \frac{p}{s} \rfloor + 1\) 两种，同样成立。
我们知道了子节点可能分配到路径后，对分配方法进行dp就行。
设 \(f[u][0/1]\) ，表示对于节点 \(u\) 的子树， \(u\) 具有路径数为 \(p\) 或 \(p+1\) 时，子树的总贡献。对于 \(f[u][0/1]\) ，先加上 \(u\) 本身的贡献，以及子节点 \(v\) 路径数为 \(\lfloor \frac{p}{s} \rfloor\) 的一种贡献，即 \(f[v][0]\) ，这是子节点都能分配到的。
然后，对于 \(f[u][0]\) ，可以给 \(p \mod s\) 个子节点多分配一条路径；对于 \(f[u][1]\) 可以给 \((p+1) \mod s\) 个子节点多分配一条路径。这些子节点的贡献可以加一个增量 \(f[v][1]-f[v][0]\) ，我们按照这个增量排序，就能找到增量最大的几个子节点，我们给它们分配即可。
最后输出 \(f[1][0]\) ，根节点没有多一条路径的选择。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> g[200007];
int s[200007];
ll f[200007][2];
void dfs(int u, int p) {
f[u][0] = 1LL * p * s[u];
f[u][1] = f[u][0] + s[u];
if (!g[u].size()) return;
vector<ll> tb;
for (auto v : g[u]) {
dfs(v, p / g[u].size());
f[u][0] += f[v][0];
f[u][1] += f[v][0];
tb.push_back(f[v][1] - f[v][0]);
}
sort(tb.begin(), tb.end(), [&](ll a, ll b) {return a > b;});
int r = p % g[u].size();
for (int i = 0;i < r;i++) f[u][0] += tb[i];
for (int i = 0;i <= r;i++) f[u][1] += tb[i];
}
bool solve() {
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) g[i].clear();
for (int i = 2;i <= n;i++) {
int p;
cin >> p;
g[p].push_back(i);
}
for (int i = 1;i <= n;i++) cin >> s[i];
dfs(1, k);
cout << f[1][0] << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}