赛时没想到c是二分答案
C. To Become Max
题意
给定一个长度为\(n\)的数组\(a\)，可对\(a_i\)加1当\(a_i\le a_{i+1}\)，最多可进行\(k\)次这样的操作，求最多\(k\)次操作后数组\(a\)中的最大值。
思路
首先找出原数组中最大的值，然后枚举1到n-1，对每个点二分答案，维护最大值。
代码
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
int ans = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
ans = max(ans, a[i]);
}
for(int i = 0; i < n - 1; i++) {
int lo = a[i], hi = 2e8;
while(lo < hi) {
int mid = lo + hi + 1 >> 1;
ll cost = 0;
bool ok = false;
for(int j = i, x = 0; j < n - 1; j++, x++) {
if(a[j] >= mid - x) break;
if(j == n - 2 && a[j + 1] + 1 < mid - x) {
ok = true;
}
cost += mid - x - a[j];
}
if(ok || cost > k) {
hi = mid - 1;
} else {
lo = mid;
}
}
ans = max(ans, lo);
}
cout << ans << "\n";
}
E1. PermuTree (easy version)
题意
给定一棵树，给每个节点赋权值\(p_1,p_2\cdots p_n\)，且\(p_1,p_2\cdots p_n\)是一个排列。求一种赋权值的方案，最大化符合条件的二元组\((u,v)\)的数量。二元组\((u,v)\)符合条件当且仅当\(p_u<p_{lca(u,v)}<p_v\)
思路
首先dfs一遍求的每个节点的子节点数量。要使得二元组数量最多，我们把每个节点的子树分为两块，让两块子树的节点数相乘最大。要使得两块子树的节点数相乘最大，就尽量让两部分节点数尽量接近，这个可以用01背包解决，设容量为所有子节点数量的一半。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for(int i = 2; i <= n; i++) {
int p;
cin >> p;
adj[p].push_back(i);
}
vector<int> siz(n + 1, 1);
auto getSize = [&](auto self, int u) ->int {
for(int v : adj[u]) {
siz[u] += self(self, v);
}
return siz[u];
};
getSize(getSize, 1);
int ans = 0;
for(int x = 1; x <= n; x++) {
int sum = siz[x] - 1 >> 1;
vector<int> dp(sum + 1);
for(int y : adj[x]) {
for(int k = sum; k >= siz[y]; k--) {
dp[k] = max(dp[k], dp[k - siz[y]] + siz[y]);
}
}
ans += dp[sum] * (siz[x] - dp[sum] - 1);
}
cout << ans << "\n";
return 0;
}