CF2138A Cake Assignment
犯唐了的一道题。因为任意时刻肯定是一个人 \(>2^k\)，另一个人 \(<2^k\)，那么我们倒过来做。每次那个 \(>2^k\) 的那个人肯定是上一步另一个人给了一半给它（因为如果它自己给了一半肯定不行）。
正着做也可以，就是我太蠢了手模了好久好久。下面是正着做的。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, k;
int main(){cin.tie(nullptr)->sync_with_stdio(0);int T; cin >> T;while(T--){cin >> k >> x;ll D = (1ll << k);char op[2] = {'1', '2'};if(x == D){ cout << "0\n\n"; continue; }if(x < D) swap(op[0], op[1]), x = (D << 1) - x;int l;for(l = 0; l <= k; ++l){if(x & (1ll << l)) break;}cout << k - l << '\n';for(int i = l + 1; i <= k; ++i){cout << op[bool(x & (1ll << i))] << ' ';}cout << '\n';}return 0;
}
CF2138B Antiamuny Wants to Learn Swap
只用操作 1 的答案等于区间逆序对数。
考虑什么时候使用操作二能减少次数，对相邻三个的大小关系做讨论，发现只有当 \([l, r]\) 的这个区间中存在 \(b_i > b_{j} > b_{k}(i < j < k)\) 才可能变少。这里不是相邻的因为我们总是可以把这三个数先一操作换到一起，然后再做二操作。
那么对于每个 \(i\)，找到前面的一个比它大的 \(pre_i\)，后面第一个比它小的 \(nxt_i\)。然后对每个区间数 \(l \le pre_i < nxt_i \le r\) 的点有几个就行。
Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 5;
int a[N], pre[N], nxt[N], n, st[N], tp, q, ans[N];
vector<pii> query[N];
struct BIT{int tr[N];#define lb(x) (x & (-x))void add(int x, int k){if(x == 0) return;for(int i = x; i <= n; i += lb(i)) tr[i] += k;}int qry(int x){int sum = 0;for(int i = x; i; i -= lb(i)) sum += tr[i];return sum;}
}tr;
void solve(){cin >> n >> q;for(int i = 1; i <= n; ++i) cin >> a[i];tp = 0;for(int i = 1; i <= n; ++i){tr.tr[i] = 0;query[i].clear();while(tp && a[st[tp]] > a[i]) nxt[st[tp]] = i, --tp;st[++tp] = i;}for(int i = 1; i <= tp; ++i) nxt[st[i]] = n + 1;tp = 0;for(int i = 1; i <= n; ++i){while(tp && a[st[tp]] < a[i]) --tp;pre[i] = st[tp];st[++tp] = i;}for(int i = 1; i <= n; ++i) query[nxt[i]].emplace_back(pre[i], 0);for(int i = 1; i <= q; ++i){int l, r; cin >> l >> r;query[r].emplace_back(l, i);}for(int i = 1; i <= n; ++i){for(auto t : query[i]){int l, idx; tie(l, idx) = t;if(!idx) tr.add(l, 1);else ans[idx] = tr.qry(n) - tr.qry(l - 1);}}for(int i = 1; i <= q; ++i){cout << (ans[i] == 0 ? "Yes" : "No") << '\n';}
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);int T; cin >> T;while(T--) solve(); return 0;
}
CF2138C2 Maple and Tree Beauty
题目等价于给定 \(k\) 个 0，\(n - k\) 个 1，每一层只能染相同的颜色，为最多能染满前几层？当然这个答案不能超过最浅的叶子节点的深度 \(mxdep\)。
经典的可行性 dp，记第 \(i\) 层有 \(d_i\) 个点。考虑 \(f_{i, j}\) 表示染了前 \(i\) 层，用了 \(j\) 个 0。那么有转移 \(f_{i, j} \gets \begin{cases} f_{i - 1, j - d_i} & j \ge d_i \\ f_{i - 1, j} & n - j \ge d_i \end{cases}\)。
考虑 bitset 优化。直接做常数太大了，无法通过。发现随着层数的递增，我们要保证 1 的点不被用成负的，那么可能的最小的 \(j\) 是单调递增的。那么维护这个最小的位置 \(l\)，再维护一个 bitset \(lim\) 是 \(\ge l\) 的全都是 1，小于 \(l\) 的全都是 0。那么每次从 \(i - 1 \to i\) 只需要，左移 \(d_{i}\) 位然后与上这个 \(lim\) 即可。这个 \(lim\) 的维护完美表达了第二种转移。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
bitset<N> f, leaf, lim;
int n, p[N], k, dep[N], cnt[N], mxdep;
void solve(){cin >> n >> k;dep[1] = 1;leaf.set();mxdep = n;lim.reset();for(int i = 0; i <= k; ++i) lim[i] = 1;for(int i = 1; i <= n; ++i) cnt[i] = 0;for(int i = 2; i <= n; ++i){cin >> p[i];dep[i] = dep[p[i]] + 1;cnt[dep[i]]++, leaf[p[i]] = 0;}for(int i = 1; i <= n; ++i) if(leaf[i]) mxdep = (mxdep > dep[i] ? dep[i] : mxdep);int nw = 0;f.reset();f[0] = 1;int sum = 0, l = 0;for(int i = 1; i <= mxdep; ++i){nw ^= 1;while(l < cnt[i] + sum - n + k) lim[l] = 0, ++l;f = (f | (f << cnt[i])) & lim;if(!f.any()) return cout << i - 1 << '\n', void();sum += cnt[i];}cout << mxdep << '\n';
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);int T; cin >> T;while(T--) solve();return 0;
}
CF2138D Antiamuny and Slider Movement
推箱子的计数版本。下面在 \(a'_i \gets a_i - i\) 意义下考虑，算答案的时候加回来就好。
考虑一下推箱子操作对 \(i\) 的影响，对于一个操作 \((x, y)\)。有 \(a_i \gets \begin{cases} \max(a_i, y) & x < i \\ y & x = i \\ \min(a_i, y) & x > i \end{cases}\)。
考虑怎么把这个 \(max/min\) 去掉。一个经典 trick，我们考虑对最终 \(i\) 被移动到了 \(\ge j\) 的位置的方案数 \(f_j\) 进行计数，那么最后落在 \(j\) 的方案就是 \(f_j - f_{j + 1}\)。那么现在我们只关心位置与 \(j\) 的大小关系。那么我们认为 \(<j\) 的是 0，\(\ge j\) 的是 1。那么一次操作就变成了赋值 0 / 1 或者无影响。我们对最后一个有影响的操作是 1 计数方案即可，在知道了操作 0 / 1 / 无影响的个数之后（可以前缀和维护），这是 trivial 的（用插空的想法把无影响的操作插进去即可）。
离散化后复杂度 \(O(nq)\)。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, mod = 1e9 + 7;
typedef long long ll;
ll fac[N], inv[N], s1[N], s2[N], s3[N], f[N], V[N];
int n, m, q, x[N], a[N], y[N], tot;
void add(ll &x, ll y){ (x += y) %= mod; }
void solve(){cin >> n >> m >> q;tot = 0;for(int i = 1; i <= n; ++i) cin >> a[i], a[i] -= i, V[++tot] = a[i];for(int i = 1; i <= q; ++i) cin >> x[i] >> y[i], y[i] -= x[i], V[++tot] = y[i];sort(V + 1, V + 1 + tot);tot = unique(V + 1, V + 1 + tot) - V - 1;for(int i = 1; i <= n; ++i) a[i] = lower_bound(V + 1, V + 1 + tot, a[i]) - V;for(int i = 1; i <= q; ++i) y[i] = lower_bound(V + 1, V + 1 + tot, y[i]) - V;for(int i = 1; i <= n; ++i){for(int j = 1; j <= tot; ++j) s1[j] = s2[j] = s3[j] = 0;for(int j = 1; j <= q; ++j){if(x[j] < i) s1[y[j]]++;else if(x[j] > i) s2[y[j]]++;else s3[y[j]]++;}for(int j = 1; j <= tot; ++j) s1[j] += s1[j - 1], s2[j] += s2[j - 1], s3[j] += s3[j - 1]; for(int j = 1; j <= tot; ++j){f[j] = 0;int s = s1[tot] - s1[j - 1] + s3[tot] - s3[j - 1], t = s2[j - 1] + s3[j - 1];// s = 1, t = 0if(s == 0 && t == 0){f[j] = (a[i] >= j) * fac[q];continue;}else if(s == 0 && t > 0) continue;f[j] = s * inv[s + t] % mod * fac[q] % mod;}ll ans = f[tot] * (V[tot] + i) % mod;for(int j = 1; j < tot; ++j) add(ans, (mod + f[j] - f[j + 1]) * (V[j] + i) % mod);cout << ans << ' ';}cout << '\n';
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);fac[0] = fac[1] = inv[1] = 1;for(int i = 2; i <= 5e3; ++i){fac[i] = (fac[i - 1] * i) % mod;inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;}int T; cin >> T;while(T--) solve();return 0;
}