题意：
给定 $n$个集合$S_1,S_2,…,S_N$ ，对于每次操作：
- 选择两个交集不为空的两个集合 $X$和 $Y$ ；
- 合并两个集合为 $X∪Y$ 。
求可以得到一个同时包含元素 1 和 $m$的集合的最小操作次数，若找不到输出 −1 。
题解：点和集合建边，集合对应的点的权值为1，跑dijkstra，原点为，求d[m]即可。
int n, m; int d[maxn << 1]; int w[maxn << 1]; vector<int> G[maxn << 1]; void dijkstra() { priority_queue<P, vector<P>, greater<P>> q; // 小根堆 vector<bool> vis(maxn << 1, false); q.push({0, 1}); // 经过的集合个数，起点是1号顶点 d[1] = 0; while (!q.empty()) { auto [x, u] = q.top(); q.pop(); if (vis[u]) continue; vis[u] = true; for (auto i : G[u]) { if (vis[i]) continue; if (x + w[i] < d[i]) { d[i] = x + w[i]; q.push({d[i], i}); } } } } void solve() { cin >> n >> m; for (int i = 1; i <= n + m; i ++) d[i] = inf; for (int i = 1; i <= n; i ++) { int k; cin >> k; w[i + m] = 1; for (int j = 1; j <= k; j ++) { int x; cin >> x; G[x].push_back(m + i); G[m + i].push_back(x); } } dijkstra(); if (d[m] == inf) { cout << -1 << "\n"; } else cout << d[m] - 1 << "\n"; }
题意：
一开始有一些菊花图，然后随便选了两个度数为1的不相连通的点，连一条边。最终得到了一棵树。
现给定这棵树，还原出原来的菊花图，以升序告诉每个菊花图的边数。
题解：
找到一个边缘点，即度数为一的点，它的下一个点一定是菊花图的中心点，再往下搜三个点也是菊花图的中心，以此类推，满足搜索顺序$i mod 3 == 1$的点都是菊花图的中点（起点是次序为0），边数为其度数，跑一边dfs，时间复杂度$O(n)$.
int n; int in[maxn]; int dis[maxn]; vector<int> G[maxn]; vector<int> vis(maxn, false); vector<int> res; void dfs(int x, int cnt) { vis[x] = 1; if (cnt % 3 == 1) res.push_back(in[x]); for (auto i : G[x]) { if (vis[i]) continue; dfs(i, cnt + 1); } } void solve() { cin >> n; for (int i = 1; i < n; i ++) { int u, v; cin >> u >> v; in[u] ++; in[v] ++; G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) { if (in[i] == 1) { dfs(i, 0); break; } } sort(res.begin(), res.end()); for (auto i : res) cout << i << " "; cout << '\n'; }
题意：
给定$n$个商品的价格，以及 $m$个优惠券，每个优惠券只能用于一个商品，且每个商品购买时只能用一个优惠券。
第 $i$个优惠券可以优惠$d_i$元，但要求对应商品价格至少 $l_i(l_i≥d_i)$元。
问购买这 $n$个商品需要的最少价格。
题解：
对于不同折扣的优惠券，优先使用大的；
对于一张优惠券，优先给能使用且价格低的商品使用，因为对于价格高的，可能还会有其他选择，就算没有其他选择，也肯定能用低价格剩余的优惠券，可以回退。
int n, m; struct bonus { int l, d; bool operator <(const bonus &a) { return d > a.d; } } b[maxn]; int ans; multiset<int> st; void solve() { cin >> n >> m; for (int i = 1; i <= n; i ++) { int x; cin >> x; ans += x; st.insert(x); } for (int i = 1; i <= m; i ++) { cin >> b[i].l; } for (int i = 1; i <= m; i ++) { cin >> b[i].d; } sort (b + 1, b + m + 1); for (int i = 1; i <= m; i ++) { if (st.lower_bound(b[i].l) != st.end()) { ans -= b[i].d; st.erase(st.lower_bound(b[i].l)); } } cout << ans << endl; }
题意：
题解：
设某数字$A_{i, j}$在组内的位置为$x$，那么它在进行和下面集合合并时，每次也会有至少$x$的贡献，共合并$n - i$次，总贡献为$(n - i) * x$；如果下面集合中还有比它小的元素，每个元素贡献为1，用树状数组维护下面集合中比它小的元素个数，逆序遍历序列即可。
int st[maxn]; int a[10010][150]; vector<int> nums; int lowbit(int x) { return x & -x; } void update(int x) { while (x <= nums.size()) { st[x] ++; x += lowbit(x); } } int ask(int x) { int res = 0; while (x) { res += st[x]; x -= lowbit(x); } return res; } void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { cin >> a[i][j]; nums.push_back(a[i][j]); } } auto get = [&](int x) { return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1; }; sort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end()); for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { a[i][j] = get(a[i][j]); } } int ans = 0; for (int i = n; i >= 1; i --) { for (int j = 1; j <= m; j ++) { ans += j * (n - i) + ask(a[i][j] - 1); } for (int j = 1; j <= m; j ++) { update(a[i][j]); } } cout << ans << endl; }
题意：
有 N 个房间，每个房间住着一个客人。$M$ 条通道连接着这个房间，通道的长度为 $W_{i }(1 \le i \le M)$ 。在第 0 天，住在$A_1, A_2, \cdots, A_k$ 的这些人感染了病毒。在从此以后的 $D$ 天里，每天如果一个未感染的客人和已感染的病人间的最短距离小于$ X_i$ ，这个客人就会被感染。
请输出每个客人是在哪天被感染的，如果一直没感染病毒，就输出 $−1$ 。
题解：
开一个小根堆，里面存放当下可能被感染的节点，当前可能被感染的节点一定是被有感染能力的节点传染的，所以更新距离的时候要从算与这一天之前被感染节点的相对距离，即算的其实是这一天中新出队的点的上一个点和它接下里点的距离，更新为$w + u.w$。而没有出队的点自身不满足条件，也自然不会更新后续节点了。
时间复杂度还需要考证
int ans[maxn]; vector<P> G[maxn]; void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i ++) { int u, v, w; cin >> u >> v >> w; G[u].push_back({v, w}); G[v].push_back({u, w}); } priority_queue<P, vector<P>, greater<P>> q; int k; cin >> k; for (int i = 1; i <= k; i ++) { int x; cin >> x; ans[x] = 1; for (auto [u, w] : G[x]) { q.push({w, u}); } } int d; cin >> d; for (int i = 2; i <= d + 1; i ++) { int x; cin >> x; vector<int> tmp; while (!q.empty()) { auto [w, u] = q.top(); if (w > x) break; q.pop(); if (ans[u]) continue; ans[u] = i; tmp.push_back(u); for (auto [v, w1] : G[u]) { if (ans[v]) continue; q.push({w1 + w, v}); } } for (auto v : tmp) for (auto [t, w] : G[v]) q.push({w, t}); } for (int i = 1; i <= n; i ++) cout << ans[i] - 1 << endl; }
题意：构造一个关于$n$的排序，使得最多有$k$个位置满足$i\neq q_i$，问总共有多少种排序满足.
题解：
错排公式
f[i] = (i - 1) * (f[n - 1] + f[n - 2])
组合数递推公式
for (int i = 0; i <= n; i ++) { for (int j = 0; j <= i; j ++) { if (!j) f[i][j] = 1; else f[i][j] = f[i - 1][j - 1] + f[i - 1][j]; } }
本题中元素满足$i\neq q_i$的个数可以为$x \in [0, k]$ $(x \neq1)$，所以总共满足条件的个数为 $1 + \sum_{i =2}^{k} (C_{n}^{i} * f[i])$
题解 ‘01’串长度等于其对应的十进制数大小，长度最大为$2e^5$，也就是最多不到20位的长度