T1
冒泡排序趟数期望
显然趟数是每个数前面比它大的数的个数的 \(\max\)。容斥，计算每个答案 \(\le x\) 的概率。从大往小填数，则每个 \(x\) 的答案容易表示为一个阶乘乘以一个次方。于是再求个差分就做完了。
代码
#include <iostream>
#include <string.h>
#define int long long
using namespace std;
const int P = 1000000007;
int qpow(int x, int y = P - 2) {int ret = 1;while (y) {if (y & 1) ret = ret * x % P;y >>= 1;x = x * x % P;}return ret;
}
int n;
int a[1000005], fac[1000005];
signed main() {freopen("bubble.in", "r", stdin);freopen("bubble.out", "w", stdout);cin >> n;fac[0] = 1;for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % P;for (int i = n - 1; ~i; i--) {a[i] = fac[i + 1] * qpow(i + 1, n - i - 1) % P;}int ans = 0;for (int i = n - 1; i; i--) a[i] = (a[i] - a[i - 1] + P) % P;for (int i = n - 1; ~i; i--) ans += a[i] * i % P;cout << ans % P * qpow(fac[n]) % P << "\n";return 0;
}
T2
成语接龙
直接从终点开始拓扑排序，如果最后存在没有走到的点，那么这些点的依赖一定构成环，一定有手段将局面控制在环中。于是就做完了。
代码
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> G[500005], iG[500005];
int f[500005][2];
struct node { int x, y, dis; };
bool operator<(node a, node b) { return a.dis > b.dis; }
priority_queue<node> q;
int deg[500005];
bool vis[500005][2];
int main() {freopen("idioms.in", "r", stdin);freopen("idioms.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;G[u].emplace_back(v);iG[v].emplace_back(u);}memset(f, -1, sizeof f);for (int i = 1; i <= n; i++) {deg[i] = G[i].size();if (G[i].empty()) {f[i][0] = f[i][1] = 0;q.push((node) { i, 0, 0 });q.push((node) { i, 1, 0 });}}while (!q.empty()) {node tmp = q.top(); q.pop();int x = tmp.x, y = tmp.y;if (y) { for (auto v : iG[x]) if (f[v][0] == -1 || f[v][0] > f[x][y] + 1) f[v][0] = f[x][y] + 1, q.push({ v, 0, f[v][0] }); }else for (auto v : iG[x]) {--deg[v];if (!deg[v]) f[v][1] = f[x][y] + 1, q.push({ v, 1, f[v][1] });}}for (int i = 1; i <= n; i++) cout << f[i][0] << "\n";return 0;
}
T3
LIS 与 LDS
将 LIS 和 LDS 的折线画在平面上，不难发现一定会交于一点（不是格点）（可能在最开始或最后）。枚举交点横坐标在 \([p, p + 1]\)，一个纵坐标可以是合法的交点当且仅当 \((p, q)\) 往四个象限延伸的 LIS 和 LDS 之和为原序列的两个之和。于是枚举横坐标，线段树维护每个纵坐标的答案。接下来只讨论维护左下矩形。
考虑贪心求 LIS 的方法，我们维护数组 \(f_i\) 表示长度为 \(i\) 的 LIS 末尾最小是多少。每次加入一个数 \(v\) 的时候找到数组中第一个比 \(v\) 大的位置 \(x\)，执行 \(f_x \leftarrow v\)。那么发现这个时候 \([f_x, v)\) 这一段区间的答案都会 \(+1\)。于是线段树只需要维护区间加，区间 \(\max\) 及其个数即可。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cassert>
#include <array>
using namespace std;
int n;
int a[500005];
array<int, 2> op[500005][2];
struct Segment_Tree {array<int, 2> mx[2000005];int tg[2000005];void tag(int o, int v) { mx[o][0] += v, tg[o] += v; }void pushdown(int o) {if (!tg[o]) return;tag(o << 1, tg[o]);tag(o << 1 | 1, tg[o]);tg[o] = 0;}void Build(int o, int l, int r) {mx[o][0] = 0;if (l == r) return mx[o][1] = l, void();int mid = (l + r) >> 1;Build(o << 1, l, mid);Build(o << 1 | 1, mid + 1, r);mx[o] = max(mx[o << 1], mx[o << 1 | 1]);}void Add(int o, int l, int r, int L, int R, int v) {if (L <= l && r <= R) return tag(o, v);pushdown(o);int mid = (l + r) >> 1;if (L <= mid) Add(o << 1, l, mid, L, R, v);if (R > mid) Add(o << 1 | 1, mid + 1, r, L, R, v);mx[o] = max(mx[o << 1], mx[o << 1 | 1]);}int Query(int o, int l, int r, int L, int R) {if (L <= l && r <= R) return mx[o][0];pushdown(o);int mid = (l + r) >> 1;if (R <= mid) return Query(o << 1, l, mid, L, R);if (L > mid) return Query(o << 1 | 1, mid + 1, r, L, R);return max(Query(o << 1, l, mid, L, R), Query(o << 1 | 1, mid + 1, r, L, R));}
} seg;
int f[500005], g[500005];
int f2[500005], g2[500005];
int ans1[500005], ans2[500005], sz1, sz2;
int lst[500005][2];
int main() {freopen("c.in", "r", stdin);freopen("c.out", "w", stdout);cin >> n;seg.Build(1, 0, n);for (int i = 1; i <= n; i++) cin >> a[i], f[i] = n + 1;for (int i = n; i; i--) {int x = lower_bound(f + 1, f + n + 1, a[i]) - f;op[i][0] = (array<int, 2>) { a[i], f[x] - 1 };seg.Add(1, 0, n, a[i], f[x] - 1, 1); f[x] = a[i];x = lower_bound(g + 1, g + n + 1, a[i]) - g - 1;op[i][1] = (array<int, 2>) { g[x], a[i] - 1 };seg.Add(1, 0, n, g[x], a[i] - 1, 1); g[x] = a[i];}int X = 0, Y = 0;for (int i = 1; i <= n; i++) if (f[i] == n + 1) { Y = i - 1; break; }for (int i = n; i; i--) if (g[i] == 0) { X = n - i; break; }for (int i = 1; i <= n; i++) f[i] = n + 1, g[i] = 0;int p = -1, q = -1;for (int i = 1; i <= n + 1; i++) {if (seg.mx[1][0] == X + Y) {p = i - 1, q = seg.mx[1][1];break;}if (i == n + 1) break;int x = lower_bound(f + 1, f + n + 1, a[i]) - f;seg.Add(1, 0, n, a[i], f[x] - 1, 1); f[x] = a[i];x = lower_bound(g + 1, g + n + 1, a[i]) - g - 1;seg.Add(1, 0, n, g[x], a[i] - 1, 1); g[x] = a[i];seg.Add(1, 0, n, op[i][0][0], op[i][0][1], -1);seg.Add(1, 0, n, op[i][1][0], op[i][1][1], -1);}for (int i = 1; i <= n; i++) f[i] = n + 1, g[i] = 0, f2[i] = g2[i] = -1;if (p == -1) return cout << "-1\n", 0;array<int, 2> mxf{ 0, 0 }, mxg{ 0, 0 };for (int i = 1; i <= p; i++) {int x;if (a[i] <= q) {x = lower_bound(f + 1, f + n + 1, a[i]) - f;f[x] = a[i], f2[x] = i;lst[i][0] = f2[x - 1];mxf = max(mxf, (array<int, 2>) { x, i });} else {x = lower_bound(g + 1, g + n + 1, a[i]) - g - 1;g[x] = a[i], g2[x] = i;lst[i][1] = g2[x + 1];mxg = max(mxg, (array<int, 2>) { n - x + 1, i });}}for (int i = mxf[1]; i; i = lst[i][0]) ans1[++sz1] = i; reverse(ans1 + 1, ans1 + sz1 + 1);for (int i = mxg[1]; i; i = lst[i][1]) ans2[++sz2] = i; reverse(ans2 + 1, ans2 + sz2 + 1);memset(lst, 0, sizeof lst);for (int i = 1; i <= n; i++) f[i] = n + 1, g[i] = 0, f2[i] = g2[i] = -1;mxf = mxg = { 0, 0 };for (int i = n; i > p; i--) {int x;if (a[i] <= q) {x = lower_bound(f + 1, f + n + 1, a[i]) - f;f[x] = a[i], f2[x] = i;lst[i][0] = f2[x - 1];mxf = max(mxf, (array<int, 2>) { x, i });} else {x = lower_bound(g + 1, g + n + 1, a[i]) - g - 1;g[x] = a[i], g2[x] = i;lst[i][1] = g2[x + 1];mxg = max(mxg, (array<int, 2>) { n - x + 1, i });}}for (int i = mxg[1]; i; i = lst[i][1]) ans1[++sz1] = i;for (int i = mxf[1]; i; i = lst[i][0]) ans2[++sz2] = i;cout << sz1 << "\n";for (int i = 1; i <= sz1; i++) cout << ans1[i] << " ";cout << "\n";cout << sz2 << "\n";for (int i = 1; i <= sz2; i++) cout << ans2[i] << " ";cout << "\n";return 0;
}
T4
购物博弈
考虑对每个 \(l\) 求出最大合法 \(r\)。记为 \(f_l\)。显然 \(f\) 单调，考虑决策单调性的分治。每次求出中点处的答案，并向左右递归。求中点答案使用二分，每次 chk 过后把不进入的那边的东西加入背包。每次递归向儿子的时候加入不在儿子的两个区间里的东西。统计答案是容易的。
代码
#include <iostream>
#include <string.h>
#include <numeric>
#include <vector>
#define int long long
using namespace std;
int n, V, L;
int a[200005], b[200005], c[200005];
int F[200005];
vector<int> f;
void upd(int x, int y) { for (int i = V; i >= x; i--) f[i] = max(f[i], f[i - x] + y); }
int work(int l, int r) {if (l == r) return l;int mid = (l + r) >> 1;vector<int> tmp = f;for (int i = l; i <= mid; i++) upd(b[i], c[i]);for (int i = mid + 1; i <= r; i++) upd(a[i], c[i]);if (accumulate(f.begin(), f.end(), 0ll) > V * L) {f = tmp;for (int i = l; i <= mid; i++) upd(b[i], c[i]);return work(mid + 1, r);} else {f = tmp;for (int i = mid + 1; i <= r; i++) upd(a[i], c[i]);return work(l, mid);}
}
void Solve(int l, int r, int pl, int pr) {if (l > r) return;int mid = (l + r) >> 1;vector<int> tmp = f;for (int i = l; i < mid; i++) upd(a[i], c[i]);for (int i = mid; i < min(r + 1, pl); i++) upd(b[i], c[i]);int p = F[mid] = work(max(mid, pl), pr);f = tmp;for (int i = mid; i < min(r + 1, pl); i++) upd(b[i], c[i]);for (int i = p + 1; i <= pr; i++) upd(a[i], c[i]);Solve(l, mid - 1, pl, p);f = tmp;for (int i = l; i <= mid; i++) upd(a[i], c[i]);for (int i = max(r + 1, pl); i < p; i++) upd(b[i], c[i]);Solve(mid + 1, r, p, pr);
}
signed main() {freopen("shopping.in", "r", stdin);freopen("shopping.out", "w", stdout);cin >> n >> V >> L;f.resize(V + 1);for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];Solve(1, n, 1, n + 1);int ans = 0;for (int i = 1; i <= n; i++) ans += n - F[i] + 1;cout << ans << "\n";return 0;
}
T2。
贪心求 LIS。
)
