昨晚跟时队一起vp了 Codeforces Round 1048 (Div. 2)
总结了一下就是D题犯糖了然后F还不会做，本质菜逼了。
A. Maple and Multiplication
考虑 \(a\) \(b\) 相等或者互为倍数两种特殊情况即可。
int T, a, b;signed main(void) {for (read(T); T; T--) {read(a), read(b);if (a == b) writeln(0);else if (a % b == 0 || b % a == 0) writeln(1);else writeln(2);}//fwrite(pf, 1, o1 - pf, stdout);return 0;
}
B. Cake Collection
由排序不等式可知最优情况
const int N = 1e5 + 5;
int T, n, m, a[N], b[N]; ll sum[N];signed main(void) {for (read(T); T; T--) {read(n), read(m); int mx = 0; ll ans = 0;for (int i = 1; i <= n; i++) read(a[i]), chkmax(mx, a[i]);for (int i = 1; i <= mx; i++) b[i] = 0;for (int i = 1; i <= n; i++) ++b[a[i]];int k = min(n, m), t = m;for (int v = mx; v >= 1 && k; v--) {while (b[v] && k) {ans += 1ll * v * t;--b[v], --k, --t;}}writeln(ans);}//fwrite(pf, 1, o1 - pf, stdout);return 0;
}
C. Cake Assignment
已知把自己的一半给另个人一定会使大小关系发生翻转。于是从后往前递推模拟即可。
int T; ll k, x;signed main(void) {for (read(T); T; T--) {read(k), read(x);ll a = x, b = (1ll << k + 1) - x;vector <int> ans;while (a != b) {if (a < b) {ans.push_back(1);b -= a, a *= 2;} else {ans.push_back(2);a -= b, b *= 2;}}reverse(ans.begin(), ans.end()); writeln(ans.size());for (auto u : ans) writeln(u, ' '); putchar('\n');}//fwrite(pf, 1, o1 - pf, stdout);return 0;
}
D. Antiamuny Wants to Learn Swap
通过冒泡排序的性质可知 \(f(b)=g(b)\) 当且仅当不存在一组 \((i,j,k): (i < j < k)\) 满足 \(b_i > b_j > b_k\)。那么我们只需要用单调栈，处理出对于一个位置 \(i\) 来说左侧离它最近且大于它的位置 \(L_i\) 和右边离它最近且小于它的位置 \(R_i\)，然后记录这个小区间。再判断一个询问区间 \([l,r]\) 中是否包含任意一个小区间就行了。
const int N = 5e5 + 5;
int T, n, q, a[N], L[N], R[N], mxl[N]; vector <int> in[N];signed main(void) {for (read(T); T; T--) {read(n), read(q);for (int i = 1; i <= n; i++) read(a[i]), mxl[i] = 0, in[i].clear();stack <int> stk; stk.push(1); L[1] = 0;for (int i = 2; i <= n; i++) {while (!stk.empty() && a[stk.top()] < a[i]) stk.pop();if (!stk.empty()) L[i] = stk.top(); else L[i] = 0;stk.push(i);}while (!stk.empty()) stk.pop(); stk.push(n); R[n] = n + 1;for (int i = n - 1; i >= 1; i--) {while (!stk.empty() && a[stk.top()] > a[i]) stk.pop();if (!stk.empty()) R[i] = stk.top(); else R[i] = n + 1;stk.push(i);}for (int i = 2; i < n; i++) in[R[i]].push_back(L[i]);for (int i = 1; i <= n; i++) {chkmax(mxl[i], mxl[i - 1]);for (auto u : in[i]) chkmax(mxl[i], u);}for (int i = 1; i <= q; i++) {int l, r;read(l), read(r);if (mxl[r] >= l) puts("No");else puts("Yes");}}//fwrite(pf, 1, o1 - pf, stdout);return 0;
}
E. Maple and Tree Beauty
E1 和 E2 两题只有数据规模的区别。我们易知最优的情况就是大家的公共前缀足够长，底层逻辑都是考虑一个按层来转移的树形DP \(f_{i,j}\) 表示到第 i 层填了 j 个 0 的合法性。然后可以用或来转移，自然想到 \(bitset\) 优化，注意就是 1 不能填超过 \(n - k\) 个，用一个合法性数组与一下来限制即可。
const int N = 2e5 + 5;
int T, n, k, dep[N], h[N], mndep, tot; vector <int> G[N];
inline void dfs(int u) {if (G[u].empty()) chkmin(mndep, dep[u]);for (auto v : G[u]) dep[v] = dep[u] + 1, dfs(v);
}bitset <N> f[2], g;signed main(void) {for (read(T); T; T--) {read(n), read(k); mndep = n + 1; tot = 0;for (int i = 1; i <= n; i++) dep[i] = h[i] = 0, G[i].clear();for (int i = 2, fat; i <= n; i++) {read(fat); G[fat].push_back(i);}dep[1] = 1; dfs(1);for (int i = 1; i <= n; i++) h[dep[i]]++;f[0].reset(); f[1].reset();for (int i = 0; i <= n; i++) g[i] = i <= k ? 1 : 0;f[0][0] = 1; int ans = 0;for (int d = 1, i = 0; d <= mndep; d++) {tot += h[d]; int o = d & 1;for (; tot - i > n - k; i++) g[i] = 0;f[o] = ((f[1 - o] << h[d]) | f[1 - o]) & g;if (f[o].count()) ans++; else break;}writeln(ans);}//fwrite(pf, 1, o1 - pf, stdout);return 0;
}