~

div1+2A.存在一个 $i \geq x$ 就是 YES。 B.首先如果 $n$ 是一个偶数，那么无解。 $\lfloor\frac{n-1}{2}\rfloor$ 和 $\lceil \frac{n+1}{2}\rceil$ 一奇一偶，递归构造即可。 123456789101112131415vector<int> ff;auto f = [&](auto f, int x) -> void { if (x == 1) { return; } int y1 = (x + 1) / 2; int y2 = (x - 1) / 2; if (y1 % 2 == 1) { f(f, y1); ff.emplace_back(1); } else { f(f, y2); ff.emplace_back(2); }}; C.首先答案有一个固定的上界，是全部删完之后加一个 $ ...

A.构造 $()\times n$，$(\times n + )\times n$。 B.模拟。 C.定义 I 类点：左边没有一个比他大的。 如果起点在 $i$，左边只有 I 类点，那么这个 $i$ 是一个合法的起点。 edu 的时候写了个 rmq，感觉自闭了。 事实上只要维护前面的最大值，还有合法点的最小值可以了。 模拟。 D.首先考虑，一个点最多被交换一次（显然）。也就是相当于改变的点的个数 / 2。 考虑 $dp_{i, j, k}$ 为前 $i$ 个里面有了 $j$ 个 1且 $k = cnt_{10} - cnt_{01}$ 时候最少需要改变几个数字。 最后答案为 $dp_{n, cnt_1, 0} / 2$。dp 可以滚动数组，能过。 没看太懂别人的做法。 E.其实就是两个操作，之前 cf 出过一次（x 走到相邻的点 走到颜色相同的点 代价都是 1。 做法: 可以多源最短路，定义 $dis_{col,i}$ 表示颜色 $col$ 走到 $i$ 需要多少次操作。 最后的答案是 $\min {\min dis_{col,x} + dis_{co ...

A.模拟。 B.考虑到只有 $a_i \geq a_{i-1}$ 才会塞数字，当 $a_{i} \geq a_{i - 1}$ 的时候直接塞，否则连塞两个。 C.差分后前缀和。 D.二分答案，找到最大的 $x \times (x - 1) \leq 2 \times n$，然后答案就是 $x + n - \frac{x \times (x - 1)}{2}$。 E.发现答案是 $[1, i]$ 选最大的 $m$ 个，然后减掉 $d \times i$，用堆贪心维护即可。 F.背包。 G.考虑怎么样才会变成答案，首先不难想到，有一个简单的 $O(n^2)$ 算法，因为每次操作相邻的会差分减一。所以我们选择操作 $\min{a_i - a_{i-1}}$ 次，这样稳定消掉一个，就可以做到 $O(n^2)$，发现每次都是相邻的合并，所以最大值一定会一直留着（可能会被合并，但是没有关系）。 所以是 $\max +$ 操作次数。 考虑操作次数要怎么求，具体的，每次选差分最小值，整体再减掉最小值，重复这个过程，容易知道总操作次数为 $\max a_i - a_{i-1}$，所以是可以动态维护这个东 ...

A.倒着模拟。 B.观察 2 操作会改变奇偶性，全部排序。如果 2 操作不会改变奇偶性，分开排序。 C.每个数不能被加两次，很容易的想到二进制（因为 0/1）。然后先找到最大的 $2^k \leq n$，再由高到低逐位构造即可。 123456789101112131415vector<int> ans{1};while (ans.back() * 2 <= x) { ans.emplace_back(ans.back() * 2);}x -= ans.back();for (int i = 30; i >= 0; i--) { if (x >> i & 1) { ans.emplace_back(ans.back() + (1LL << i)); }}reverse(all(ans));cout << sz(ans) << "\n";for (int x : ans) { c ...

牛客第一场rank 15 D所有后缀的 xor. 注意到任何后缀都可以用前缀和 $S_n - S_i$ 表示。 也就是我们可以用一个 $F(x) = \oplus (x-S_i)$ 来做这个答案。 考虑 $(x - S_i) \mod 2^{k+1}$ 的结果来做讨论 $2^k$ 这一位是 $1$ 还是 $0$。 转化为单点加法，区间求和的问题。 J考虑两维独立，只有左右边界，那么可以二分到第一个碰壁的位置，然后碰壁和碰壁之间可以倍增求解。 倍增的代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70133770 也可以类似 HoMaMa 一样:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70123888 1234567891011121314151617181920212223242526struct Fun { Int a, b, c, d; Int f(Int x) const
...

E简单 dp，两维限制转成一维。 F区间建边的 MST，可以考虑区间取 min，是等价的。 G斯坦纳树。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/stdc++.h>#define int long longusing namespace std;const int INF = 1e18;signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, m, k; cin >> n >> m >> k; vector<vector<pair<int, int>>> e(n); for (int i = 0; i < m; i++) { int u, ...

A.先用 4 填，填不了用 2. 被 codeforces better 骗了，过了样例，A wa2 12345678void solve() { int N; cin >> N; int ANS = N / 4; if (N % 4 == 2) { ANS++; } cout << ANS << "\n";} B.手动模拟. 123456789101112131415void solve() { int N; cin >> N; int K; cin >> K; vc<vi> A(N, vi(N)); rep(i, N) rep(j, N) { char c; cin >> c; A[i][j] = c - '0'; } for (int i = 0; i < N; i += K) { for (int j = 0; j & ...

A-E 一眼。 F 是一个贪心，一一配对的话，那么如果有超过一半的，别的都能和他配对，然后再考虑剩下的部分，直接贪就好了，如果没有超过一半的，那么全都可以互相配对，就做完了。 G 是一个区间 xor hash。

A. 模拟 B. 模拟 C. 贪心的从高到低取，二进制拆分一样的思路，能取就取。 D. 笛卡尔 dp。 https://codeforces.com/contest/1913/submission/238025170 E. 最小费用最大流。 我的建图方案是：考虑让流量是 n*m，这样刚好一一对应，然后就看一个点要不要改了。 https://codeforces.com/contest/1913/submission/238025260

A. max(n, m) B. (leaf+1)/2 C. 选出来的 t 每次减少 1。 https://codeforces.com/contest/1905/submission/238024495 D. 倍长之后，每次往后增加一个数，删掉开头的数字，区间取 max，区间求和，线段树二分。 E. 令 $f(n, p)$ 为有 n 个点，当前是 p 的答案，然后发现其实是一个类似二次函数的东西，递归就能维护了。