【CF】Day72——Codeforces Round 890 (Div. 2) CDE1 (二分答案 | 交互 + 分治 | ⭐树上背包)

C. To Become Max

题目：

思路：

二分挺好想的，但是check有点不好写

看到最大值，试试二分，如果 x 可以，那么 x - 1 肯定也可以，所以具有单调性，考虑二分

如何check呢？由于 n 很小，我们可以考虑 n² 的 check，我们可以考虑枚举每一个位置为 mid，那么如果这个位置要是 mid 那么下一个位置就起码是 mid - 1，以此类推，直接模拟即可

特别的，由于 n 处无法继续往后，所以记得判断一下

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n, K;cin >> n >> K;vector<int> A(n);int mx = 0;for (int i = 0; i < n; i++){cin >> A[i];mx = max(A[i], mx);}auto check = [&](int mid) ->bool{for (int i = 0; i < n - 1; i++){int nd = 0;int m = mid;int j = i;for (; j < n; j++){if (A[j] >= m){break;}nd += m - A[j];m--;}if (K >= nd && A[j] >= m && j < n){return true;}}return false;};int l = mx, r = 1e18;while (l + 1 < r){int mid = l + r >> 1;if (check(mid)){l = mid;}else{r = mid;}}if (check(r)){cout << r << endl;return;}cout << l << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

---

D. More Wrong

题目：

思路：

找结论题

交互题通常喜欢二分，这里也不例外

我们先要知道一个关键点，假设 x 是最大值的位置，那么对于任意一个左端点 l，都有以下结论： [l, x-1] = [l,  x]，即这两个区间的逆序对一定相同，因为 x 是最大值，那么加在后面是无影响的 

如果我们直接一个一个枚举的话肯定会超时，所以我们考虑优化，我们考虑分治，我们像线段树一样每次取一半，然后把每个子区间的最大值求出来，再依次合并

具体的，假设我们要求 [l r] 的最大值，我们要先求出 [l mid] [mid+1 r] 的两个最大值的位置 Lmx和 Rmx，其中 mid = (l+r) / 2，然后根据我们的结论，如果 Rmx 是最大值，那么就有 [Lmx Rmx - 1] = [Lmx Rmx]，否则就是 Lmx 是区间的最大值

模拟即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"int ask(int l,int r)
{if (l == r)return 0;else{cout << "? " << l << " " << r << endl;int w = 0;cin >> w;return w;}
}int solve(int l,int r)
{if (l == r){return r;}else{int mid = l + r >> 1;int Lmx = solve(l, mid), Rmx = solve(mid + 1, r);if (ask(Lmx,Rmx) == ask(Lmx,Rmx-1)){return Rmx;}return Lmx;}
}signed main()
{int t = 1;cin >> t;while (t--){int n; cin >> n;int w = solve(1, n);cout << "! " << w << endl;}return 0;
}

---

E1. PermuTree (easy version)

题目：

思路：

看似lca？实则dp

这一题我们看着好像无法下手，但是注意到 n <= 5000，我们可以考虑 n² 做法

题目意思转化一下就是你可以自由分配树的顶点的权值 val[i]，使得所有权值最后是一个排列，最后的答案是对于任意一个父节点选取其两个子节点 (u,v)，满足 val[u] < val[fa] < val[v] 的(u,v)对数

我们可以将 lca，变化一下，因为我们其实不需要知道子节点具体是什么，我们只在乎它的权值，那么我们就可以考虑枚举每一个节点当这个 lca

那么如果这个点是 lca，那我们如何计算其奉献呢？我们贪心的想，我们肯定是考虑将其子树分成两个子集，一个是权值全小于父节点，一个是权值全大于父节点，那么答案就是 size_small * size_big

那么问题再转化一下，对于每一个子树，我们可以考虑其是大于还是小于父节点，然后对于所有情况求最大值，那么这其实就是一个树上01背包，对于每个子树我们都可以选or不选，所以直接套就行了

那为什么我们一定可以这样构造呢？我们这样想，我们肯定是先分配最小的子树，比如对于下面例子

我们可以分配给子树小的，然后再给父节点一个中间值，然后再分配比父节点大的子树，如 1 2 | 3 | 4 5 | 6 7 这样，不过由于不需要我们输出具体的权值，所以我们不需要考虑具体的构造，但是肯定是能构造的 

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"int ans = 0;
int treesize[5005];
vector<vector<int>> g(5005);
void dfs(int fa)
{treesize[fa] = 1;vector<int> sontreesize;for (auto & son : g[fa]){dfs(son);treesize[fa] += treesize[son];sontreesize.push_back(treesize[son]);}vector<int> f(5005, 0);f[0] = 1;int sum = 0;for (auto& sonsize : sontreesize){sum += sonsize;for (int i = sum; i >= sonsize; i--){f[i] |= f[i - sonsize];}}int mx = 0;for (int i = 0; i <= sum; i++){if (f[i]){mx = max(mx, i * (sum - i));}}ans += mx;
}void solve()
{int n;cin >> n;for (int i = 2; i <= n; i++){int fa; cin >> fa;g[fa].push_back(i);}dfs(1);cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;while (t--){solve();}return 0;
}