~

A.模拟题。 B.马拉车或者 substr+reverse，模拟题。 substr(i, j) 表示从 $i$ 位置开始拿 $j$ 个。 C.枚举。 D.考虑建图，然后跑一遍，没有遍历到的就是不确定的点。 E.用 set 模拟。 F.定义状态 $dp_{i, x, y}$ 表示到 $i$ 这个位置，正方向还剩下 $x$ 油，负方向还剩下 $y$ 油的最小代价。 最后答案就是 $dp_{i,k,k}$。 123456789101112131415161718192021222324252627282930int lst = 0; vector<vector<int>> dp(H + 1, vector<int>(H + 1, 0)); for (int i = 0; i < N; i++) { int d = X[i] - lst; lst = X[i]; vector<vector<int>> g(H + 1, vector<int>(H + 1, inf)); for ...

A.模拟题。 B.枚举删除哪个数字。 C.枚举前两个数字或者 dp。 D.考虑固定根的情况，然后换根就可以了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445void solve(){ int N; cin >> N; vector<ll> A(N); for(ll& x : A) cin >> x; vector<vector<int> > tree(N); for(int i = 0; i < N-1; i++){ int u, v; cin >> u >> v; u--; v--; tree[u].push_back(v); tree[v].push_back(u); } vector<ll> ans(N); vector<ll> ssz(N); vector<int> par(N); y_co ...

一段区间的贡献是这段区间最小的 $h$ 的下标对应的 $b_i$。 分成若干个区间，使得所有区间的贡献和最大。 1234567891011121314151617181920int main() { int N; cin >> N; vc<ll> A(N), B(N); rep(i, N) cin >> A[i]; rep(i, N) cin >> B[i]; vc<ll> dp(N + 1, -lnf); dp[0] = 0; rep(i, N) { int p = i; rep(j, i, N) { if (A[p] > A[j]) { p = j; } cmax(dp[j + 1], dp[i] + B[p]); } } cout << dp[N] << "\n"; return 0;} 强行优化这个 $dp ...

题目 方法学习于 maspy 的博客。 一个很简单的想法是，可以使用背包。 使得 $dp_{a, b}$ 表示用了 $a$ 个 I 类球和 $b$ 个 II 类球。 但是直接转移的话是 $O(NAB)$ 的，无法接受。 这位日本哥采用的办法是，将 $N$ 个神奇宝贝随机，然后用 I 类球的期望个数是 $\frac{i}{N} \times A$，然后在这附近找 $K$ 个就可以了。 复杂度就是 $O(NK^2)$，错误率分析在他的博客。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647void solve() { int n, a, b; read(n, a, b); vc<double> p(n), q(n); read(p, q); vi per(n); iota(all(per), 0); shuffle(all(per), rng); vc<double> P(n), Q(n); rep(i, n)
...

矩阵求逆12345678910111213141516171819202122232425262728vc<vc<ll>> inverse(vc<vc<ll>> &a) { int n = sz(a); vc<vc<ll>> b(n); rp(i, n) b[i].resize(n), b[i][i] = 1; rp(i, n) { int r = -1; rep(j, i, n) if (a[j][i]) r = j; if (r == -1) return {}; swap(a[r], a[i]), swap(b[r], b[i]); ll inv = inverse(a[i][i]); rp(j, n) { if (j == i) continue; ll p = a[j][i] * inv % P; rp(k, n) { a[j] ...

A.判断数位严格递减。 123456789101112void solve() { string s; cin >> s; auto t = s; sort(all(t), greater<char>()); t.resize(unique(all(t)) - t.begin()); if (t == s) { cout << "Yes"; } else { cout << "No"; }} B.其实可以做到 $O(N)$，但是写了 $O(NX)$ 的做法。 12345678910111213141516171819202122232425void solve() { int N, X; cin >> N >> X; N -= 1; vector<int> A(N); for (int i = 0; i < N; i++) { cin ...

A.通过排序，一个正序一个倒序。 B.先考虑偶数的情况，如果对称的位置不同，可以算出来最小的操作次数，最多的操作次数显然是 n-ans，然后奇偶性相同的都是合法的。 然后奇数，考虑中间的位置，可以随意更改，此时就没有奇偶性的限制。 123456789101112131415161718192021222324void solve() { int n; cin >> n; string s; cin >> s; int i = 0; int j = n - 1; int ans = 0; while (i < j) { if (s[i] != s[j]) { ans += 1; } i++; j--; } for (int i = 0; i <= n; i++) { if (i <= n - ans && i >= ans && ((i - ans) % 2 == 0 || n % 2 == ...

A.模拟题。 B.考虑两种情况一种是所有 $b_i$ 都选，一种是都不选，最后输出 minmax 即可。 C.找到最靠前并且大于等于 $a_i$ 的位置，和最靠后并且大于等于 $a_i$ 的位置，就做完了。 D.考虑在 $i \leq j$ 的时候一定会有 $c_i \leq c_j$，否则 $c_i > c_j$ 肯定选 $j$，所以按照这个思路贪心即可。 1234567891011121314151617181920212223void solve() { int n; cin >> n; vi c(n); for (int i = 0; i < n; i++) { cin >> c[i]; } ll k; cin >> k; for (int i = n - 1; i > 0; i--) { cmin(c[i - 1], c[i]); } int a = k; for (int i = 0; i < n; i++) { ...

题面 题解

https://www.luogu.com.cn/problem/P4721 $f_i = \sum f_{i - j} g_{j}$，边界是 $f_{0}=1$，$g$ 给出。 考虑设置一个 $B$，然后每次将 $f$ 扩展长度 $B$，然后块内可以用 $B^2$ 来处理。 复杂度为 $O(\frac{N}{B}(B^2 + N \log N))$。 实测和普通的分治 fft 差距并不大。 普通的分治 fft 类似 cdq 分治的方式，考虑得到一个区间 $[l, r]$。 先递归左边，得到左边答案。 假设左边得到的是正确的，计算给右边的贡献。 然后递归右边。 $O(N\log^2 N)$:https://www.luogu.com.cn/record/33663228 $O(\frac{N}{B}(B^2 + N \log N))$:https://www.luogu.com.cn/record/123853754 123456789101112131415161718192021222324252627const int BLOCK = 4000;void ...