【题解】Codeforces Round 975 (Div. 2) A~E

分别假设答案为取第偶数位的最大值和取第奇数位的最大值两种情况, 取更优解.

取偶数位的最大值时, 把所有其他都偶数位都取上. 奇数同理.

code:

int solve(int _) {int n;cin >> n;vector<int>a(n + 1);int Maxj = 0, Maxo = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];if (i % 2)Maxj = max(Maxj, a[i]);else Maxo = max(Maxo, a[i]);}int ans2 = n / 2;int ans1 = n / 2 + n % 2;return max(ans1 + Maxj, ans2 + Maxo);
}

先把输入的 a 数组 sort 一下.

对于每个 $a_i$ 分别由有 $a_{i+1}$ ~ $a_n$, 共 $n-i$ 个区间有贡献, 只用从前往后遍历每个 $a$, 实时更新当前有多少个区间在做贡献.

当前的总有效区间为 $now$ 个, 加入第 $i$ 个节点时.

1. 新增了以他为左端点的 $n-i$ 个区间, $now+=n-i$.
   所以 $a[i]$ 这个点被 $now$ 个区间覆盖.
2. 减少了以他为右端点的 $i-1$ 个区间, $now-=i-1$.
   所以 $a[i]+1$ ~ $a[i+1]-1$ 被 $now$ 个区间覆盖.

注意, a[n] 是一个特例.

code:

#define int long long
void solve(int _) {int n, q;cin >> n >> q;vector<int>a(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];}map<int, int>ma;sort(1 + a.begin(), a.end());int now = 0;for (int i = 1; i <= n; ++i) {now += n - i;ma[now]++;now -= i - 1;if (i != n)ma[now] += a[i + 1] - a[i] - 1;}while (q--) {cin >> n;cout << ma[n] << " ";}cout << endl;
}

** 答案没有二分性**, fk, 赛时写了一个小时的二分.

答案的范围为 $[1-n]$, 只用枚举每个答案, 然后 $O(1)$ 做 check.

check:

对于答案 $x$, 也就是这些牌要排成 $x$ 行.

先求至少要多少列 $clm$;

1. $clm>最多元素的个数$, 因为这些不能在同一列.
2. 如果 $Ma{x}_{e}lement\ast X>su{m}_o{f}_{a}l{l}_{e}lement$, 那就是所有牌摆 $Maxelement$ 列用不完, 还要加新列, 此时 i128 clm = max(Max, sum / i + !!(sum % i));

$clm$ 求出来了, 检查空的位置是否小于 $k$ 就好, 只要有解且 $k$ 够用, 就一定能填出来.

code:

#define int long long
#define i128 __int128
int solve(int _) {int n, k;cin >> n >> k;vector<int>a(n + 1);i128 sum = 0;int Max = 0;for (int i = 1; i <= n; ++i) {cin >> a[i];Max = max(Max, a[i]);sum += a[i];}sort(1 + a.begin(), a.end());int ans = 0;for (int i = 1; i <= n; ++i) {i128 clm = max(Max, sum / i + !!(sum % i));if (clm * i - sum <= k)ans = i;}return ans;
}

注意到: 所有小于 $t$ 的数都包含在一个长度不大于 $t$ 的区间内时, 对于这个区间, 一定有解 ( 可以从这个区间的最小值开始往两边扩散, 哪边吉往哪边去).

那么对于所有的 $t=i$ 都可以维护一个上述区间. 遍历每一个区间: 此时对于这个区间 $[l,r]$, 可行的答案是 $[max(1,r-t+1),min(n,l+t-1)]$( 分别从区间两头往另一头走长度为 $t$ 的区间).

对于所有区间求并集即可. 注意到如果数组中没有小于等于 t 的数, 那它对应的区间就是全部.

code:

int n, a[200010];
int solve(int _) {cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}vector<pair<int, int>>tle(n + 1);tle[n] = {1, n};for (int i = n - 1; i >= 1; --i) {auto [l, r] = tle[i + 1];while (l <= r && a[l] > i)l++;while (r >= l && a[r] > i)r--;tle[i] = {l, r};if (r - l + 1 > i)return 0;}vector<int>pre(n + 2, 0);int cnt = 0;for (int i = 1; i <= n; ++i) {auto [l, r] = tle[i];if (l <= r) {cnt++;int ll = min(l, max(1, r - i + 1));int rr = max(r, min(n, l + i - 1));pre[ll]++;pre[rr + 1]--;}}int ans = 0;for (int i = 1; i <= n; ++i) {pre[i] += pre[i - 1];if (pre[i] == cnt)ans++;}return ans;
}

所有叶子与根的距离 <=> 保留所有 $deep$ 相同的节点. 于是可以对这个树跑一个层次 bfs, 对每层的答案取 $min$.

在每层:

1. 维护去除高于它的点, 要删除多少边:
   即对每一个高于它的点 x,从 x 往上回溯, 直到到 x 的某个祖先, 且这个祖先有一个深于 x 的孙子, 停止. 同时个每个边打个 id, 回溯到已删除的 边也要停止.
2. 低于它要删除多少边: 就是这层所有节点的 son 的数量.

code:

#define int long long
#define id(a,b) ((a)*1000000+(b))
const int Maxn = 5e5 + 10;int n, v, u;
int dep[Maxn], son[Maxn], ans[Maxn], fa[Maxn], Maxdep[Maxn];
vector<int>eg[Maxn];
set<int>se;
void getdep(int x, int deep) {dep[x] = deep;Maxdep[x] = deep;for (auto c : eg[x]) {if (c == fa[x])continue;fa[c] = x;getdep(c, deep + 1);Maxdep[x] = max(Maxdep[x], Maxdep[c]);}
}
int getson(int x) {son[x] = 0;for (auto c : eg[x]) {if (c == fa[x])continue;son[x] += getson(c);}return son[x] + 1;
}
int done(int x, int fromdep) {if (x == 1)return 0;if (fromdep < Maxdep[x])return 0;if (se.count(id(x, fa[x])))return 0;se.emplace(id(x, fa[x]));return done(fa[x], fromdep) + 1;
}
int solve(int _) {cin >> n;se.clear();for (int i = 1; i <= n; ++i) {eg[i].clear();Maxdep[i] = 0;}for (int i = 1; i < n; ++i) {cin >> v >> u;eg[u].emplace_back(v);eg[v].emplace_back(u);}int ans = n - 1;getdep(1, 1);getson(1);for (int i = 1; i <= n; ++i) {debug(i, fa[i], son[i])}int last = 1, now = 0, ended = 0, pre_ended = 0;deque<int>q;q.emplace_back(1);while (!q.empty()) {int tis = q.front();q.pop_front();if (dep[tis] != last) { // 上一层删除完了,ans = min(ans, ended + now);debug(last, ended, now)now = 0;ended += pre_ended;pre_ended = 0;last = dep[tis];}now += son[tis];if (eg[tis].size() == 1) {int tp = done(tis, dep[tis]);debug(tis, tp);pre_ended += tp;}for (auto c : eg[tis]) {if (fa[tis] == c)continue;q.emplace_back(c);}}ans = min(ans, ended + now);return ans;
}