这篇文章信息量偏大，请谨慎阅读，注意高效利用右边的目录。
其他部分咕咕咕地更新中……敬请期待
1.1 二分 & 双指针
关联博文：Atserkcn-0/1分数规划
P1404 平均数
既然要让子串平均数最大，那就二分平均数，判断能否达到即可。复杂度 (O(nlog V))。
点击查看代码
signed main(){ read(n), read(m); for(register int i = 1; i <= n; i++) read(a[i]), a[i] *= 10000, Max = max(Max, a[i]); int l = 0, r = Max; while(l <= r) { int mid = (l + r) >> 1; bool flag = 0; int minn = 0; for(register int i = 1; i <= n; i++) { s[i] = s[i - 1] + (a[i] - mid); if(i >= m) { minn = min(minn, s[i - m]); if(s[i] > minn) { flag = 1; break; } } } if(flag) l = mid + 1; else r = mid - 1; } fwr(l / 10); return 0; } P4047 [JSOI2010] 部落划分
要求距离最远的部落距离最小，依然二分答案。但是判定时需要贪心地选择最近的两个部落合并，需要用到并查集维护集合。时间复杂度 (O(n^2log Vtimes alpha(n)))。
点击查看代码
int find(register int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } double mx, my; inline bool chk(double mid) { for(register int i = 1; i <= n; i++) fa[i] = i; int cnt = 0; for(register int i = 1; i <= n; i++) for(register int j = 1; j <= n; j++) { if((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]) <= mid) { fa[find(i)] = find(j); } } for(register int i = 1; i <= n; i++) if(find(i) == i) cnt++; return cnt >= k; } int main(){ read(n); read(k); for(register int i = 1; i <= n; i++) { read(x[i]), read(y[i]); mx = max(1.0 * x[i], mx), my = max(1.0 * y[i], my); } double l = 0, r = mx * mx + my * my, mid; while(r - l > 1e-4) { mid = (l + r) / 2; if(chk(mid)) l = mid; else r = mid; } printf("%.2lfn", sqrt(l)); return 0; } P6004 Wormhole Sort S
奶牛为什么要钻虫洞？
要求最大化被奶牛用来排序的虫洞宽度的最小值，还是二分答案。
考虑二分最小虫洞宽度。先对每个虫洞的宽度排序，然后判定的时候把满足 (wge mid) 的虫洞两端点用并查集合并到一起，最后看每个 (p_i) 和 (i) 是否在同一集合内就行了。时间复杂度 (O(nlog n + nlog V))。
点击查看代码
struct Edge { int u, v, w; } a[N]; int n, m, p[N], fa[N], cw[N], tot, ans; int find(register int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } inline bool cmp(const Edge &x, const Edge &y) { return x.w > y.w; } inline bool chk(register int x) { for(register int i = 1; i <= n; i++) fa[i] = i; for(register int i = 1; i <= m; i++) { if(a[i].w < x) break; register int f1 = find(a[i].u), f2 = find(a[i].v); fa[f1] = f2; } for(register int i = 1; i <= tot; i++) { if(find(p[cw[i]]) != find(cw[i])) return false; } return true; } int main(){ read(n); read(m); for(register int i = 1; i <= n; i++) { read(p[i]); if(p[i] != i) cw[++tot] = i; } if(!tot) return fwr(-1), 0; for(register int i = 1; i <= m; i++) read(a[i].u), read(a[i].v), read(a[i].w); sort(a + 1, a + m + 1, cmp); int l = a[m].w, r = a[1].w, mid; while(l <= r) { mid = (l + r) >> 1; if(chk(mid)) l = mid + 1, ans = mid; else r = mid - 1; } fwr(ans); return 0; } P4064 [JXOI2017] 加法
可以二分题目要求的 (min{a_i})，但是判定很麻烦。
我们贪心地想，从左往右扫一遍，遇到小于 (mid) 的 (a_i) 就直接用包含它的 (l,r) 执行操作直到它足够大，但是这个操作对区间内其他元素也有影响，要用树状数组维护。
但是区间的使用是有限制的，考虑取用区间时按照右端点排序，这样可以贡献到更多后面未知元素。同时要弹出右端点在 (i) 之前的区间，用优先队列可以实现这一整个过程。
参考的题解说预先要按照左端点排序，但是事实上与优先队列采用一致的排序方式也不影响。
const int N = 2e5 + 5; const long long INF = 1e18; int T, n, m, k, a; long long A[N], c[N]; struct Segs { int l, r; bool operator < (const Segs &rhs) const { return r < rhs.r; } } seg[N]; inline int lbt(register int x) { return x & -x; } inline void upd(register int x, register int d) { while(x <= n) c[x] += d, x += lbt(x); return; } inline int qry(register int x) { int res = 0; while(x) res += c[x], x -= lbt(x); return res; } inline bool cmp(const Segs &x, const Segs & y) { if(x.l == y.l) return x.r > y.r; return x.l < y.l; } priority_queue<Segs> q; inline void init() { while(!q.empty()) q.pop(); memset(c, 0, sizeof(c)); return; } inline bool chk(int x) { init(); int rec = 1, cnt = 0; for(int i = 1; i <= n; i++) upd(i, A[i] - A[i - 1]); for(int i = 1; i <= n; i++) { while(rec <= m && seg[rec].l <= i) { q.push(seg[rec]); rec++; } while(qry(i) < x && !q.empty()) { Segs t; do { t = q.top(); q.pop(); } while(t.r < i && !q.empty()); cnt++; if(cnt > k || t.r < i) return false; upd(t.l, a); upd(t.r + 1, -a); } if(qry(i) < x) return false; } return true; } void Main() { read(n); read(m); read(k); read(a); long long l = INF, r = 0, mid, ans = 0; for(register int i = 1; i <= n; i++) { read(A[i]); l = min(l, A[i]); r = max(r, A[i]); } for(register int i = 1; i <= m; i++) { read(seg[i].l); read(seg[i].r); } sort(seg + 1, seg + m + 1, cmp); r += k * a; while(l <= r) { mid = (l + r) >> 1; if(chk(mid)) l = mid + 1, ans = mid; else r = mid - 1; } fwr(ans); return putchar('n'), void(); } signed main(){ read(T); while(T--) Main(); return 0; } CF1731D Valiant's New Map
本题有个技巧是二分判定时预先把矩阵变成 01 矩阵，再做二维前缀和找和为 (0) 的正方形就行了。
P2824 [HEOI2016/TJOI2016] 排序
放我做题计划里多久了？忘了
一眼线段树。但是这题实际上是离线的，线段树主要起到辅助二分判定的作用。
正常排序是 (O(nlog n)) 的，显然太慢。本题需要一个更快捷的排序，那就是 01 排序。
01 排序只需要记一下 (1) 的个数，然后区间统一修改就行了。应用到本题，即二分答案 (mid)，然后大于等于 (mid) 的全标记成 (1)，否则标记成 (0)，如果判定后 (mid) 为 (1) 左端点后移，否则右端点前移。线段树上查询和上传修改操作全部都是 (O(log n)) 的，判定复杂度就是 (O(nlog n))，总复杂度 (O(nlog^2 n))。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, q; int a[N], op[N], L[N], R[N]; struct SGT { int l, r, val, lzy; } tr[N << 2]; void pushup(int rt) { tr[rt].val = tr[(rt << 1)].val + tr[(rt << 1 | 1)].val; return; } void rebuild(int l, int r, int rt, int mid) { tr[rt].l = l, tr[rt].r = r, tr[rt].lzy = 0; if(l == r) { if(a[l] >= mid) tr[rt].val = 1; else tr[rt].val = 0; return; } int md = (l + r) >> 1; rebuild(l, md, (rt << 1), mid); rebuild(md + 1, r, (rt << 1 | 1), mid); pushup(rt); return; } void pushdown(int rt) { if(tr[rt].lzy) { tr[rt << 1].lzy = tr[rt << 1 | 1].lzy = tr[rt].lzy; int mid = (tr[rt].l + tr[rt].r) >> 1; if(tr[rt].lzy == 1) tr[(rt << 1)].val = mid - tr[rt].l + 1, tr[(rt << 1 | 1)].val = tr[rt].r - mid; else tr[rt << 1].val = tr[rt << 1 | 1].val = 0; tr[rt].lzy = 0; } return; } int qry(int l, int r, int rt, int ql, int qr) { if(ql <= l && r <= qr) return tr[rt].val; if(ql > r || qr < l) return 0; pushdown(rt); int mid = (l + r) >> 1; return qry(l, mid, rt << 1, ql, qr) + qry(mid + 1, r, rt << 1 | 1, ql, qr); } int check(int l, int r, int rt, int p) { if(l == p && r == p) return tr[rt].val; pushdown(rt); int mid = (l + r) >> 1; if(p <= mid) return check(l, mid, (rt << 1), p); else return check(mid + 1, r, (rt << 1 | 1), p); } void upd(int l, int r, int rt, int ql, int qr, int v) { if(ql <= l && qr >= r) { tr[rt].val = v * (r - l + 1); tr[rt].lzy = v ? 1 : -1; return; } if(ql > r || qr < l) return; pushdown(rt); int mid = (l + r) >> 1; upd(l, mid, (rt << 1), ql, qr, v); upd(mid + 1, r, rt << 1 | 1, ql, qr, v); pushup(rt); } bool chk(int mid) { rebuild(1, n, 1, mid); for(int i = 1; i <= m; i++) { int cnt1 = qry(1, n, 1, L[i], R[i]); if(op[i] == 0) { upd(1, n, 1, R[i] - cnt1 + 1, R[i], 1); upd(1, n, 1, L[i], R[i] - cnt1, 0); } else { upd(1, n, 1, L[i], L[i] + cnt1 - 1, 1); upd(1, n, 1, L[i] + cnt1, R[i], 0); } } return check(1, n, 1, q); } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; } for(int i = 1; i <= m; i++) { cin >> op[i] >> L[i] >> R[i]; } cin >> q; int l = 1, r = n, mid, ans; while(l <= r) { mid = (l + r) >> 1; if(chk(mid)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans; return 0; } ABC136E Max GCD
本文可以在题解区找到。
多好的一道思维题！
蒟蒻觉得大佬们双指针贪心部分讲得有些简略，故写一篇题解来具体说说自己的想法。
首先，我们要发现一个重要的性质：记最终的答案为 (ans)，那么 (ans) 一定整除 (sum_{i=1}^{n} A_i)。因为无论怎么操作序列的和都不变，且最后必须保证 (ans) 是所有 (A_i) 的公约数。
那么，我们记 (sum=sum_{i=1}^{n} A_i)，则 (ans) 一定是 (sum) 的因子。那就需要枚举 (sum) 的因子，合法的最大因子就是 (ans)。
接下来就是判断是否合法。当考察因子 (x) 时，考虑记录每个 (B_i=A_i bmod x)，并将它们从小到大排序，接着进行双指针扫描，贪心地计算所需操作次数 (cnt)，若 (cntle k) 则合法。记左指针为 (l)，右指针为 (r)，具体贪心实现如下：
-
若 (B_l+B_r=x)，那么操作 (B_l) 次 (B_l,B_r) 就可以都变成 (0)，(cnt) 加上 (B_l)，两个指针都向中间靠 (1) 个坐标。
-
若 (B_l+B_r<x)，那么钦定操作 (B_l) 次使得 (B_l) 变成 (0)，则 (B_r) 变成 (B_r+B_l)，(cnt) 加上 (B_l)，左指针向中间靠 (1) 个坐标。
-
若 (B_l+B_r>x)，那么钦定操作 (x-B_r) 次使得 (B_r) 变成 (x)，相当于变成 (0)，则 (B_l) 变成 (B_l-x+B_r)，(cnt) 加上 (x-B_r)，右指针向中间靠 (1) 个坐标。
如果你对后两个操作有疑问，如“为什么要这样钦定”，请代入前提条件“已经将 (B_i) 从小到大排序”。
那么本题就完成了，时间复杂度是 (O(nlog nsqrt {sum}))。但实际上肯定要比这个快，因为 (O(nlog n)) 是检查因数时排序的复杂度。
1.2 贪心
P8898 Feeding the Cows B
注意到有的地方如果种了草，那么它所能影响的范围内均不需要种草。那就考虑在从左往右扫的时候，如果 (i) 没被覆盖，就不断从 (i+k) 往前看能不能种，如果能种就直接跳出。
时间复杂度大概 (O(nlog n))。
P3545 [POI 2012] HUR-Warehouse Store
经典的贪心+堆维护。
最优肯定是全部都满足，但是大概率不可能。考虑能满足就满足，遇到不能满足的就把前面满足的人里买的最多的那个人踢出去（如果踢掉他就能满足当前的人），这样就能保证答案最大化。
用大根堆维护即可，复杂度 (O(nlog n))。
struct node { int id, mon; bool operator < (const node &rhs) const { return mon < rhs.mon; } }; priority_queue<node> q; signed main() { rd(n); for(int i = 1; i <= n; i++) { rd(a[i]); } for(int i = 1; i <= n; i++) { rd(b[i]); } for(int i = 1; i <= n; i++) { sum += a[i]; if(sum < b[i]) { if(!q.empty() && q.top().mon > b[i]) { vis[q.top().id] = 0; sum += q.top().mon; q.pop(); --ans; } } if(sum >= b[i]) { sum -= b[i]; q.push((node){i, b[i]}); vis[i] = 1; ++ans; } } fp(ans); hh(); for(int i = 1; i <= n; i++, kg()) { if(vis[i]) fp(i); } return 0; } P4053 [JSOI2007] 建筑抢修
贪心+堆模型。
限制时间短的建筑肯定更要紧，所以先按照它升序排序。
接下来就是自然的贪心。如果有建筑需要报废，那必然选择报废维修时间最长那个来争取维修更多建筑。
struct Build { int t1, t2; } a[N]; priority_queue<pii>q; bool cmp(Build x, Build y) { return x.t2 < y.t2; } signed main() { rd(n); for(int i = 1; i <= n; i++) { rd(a[i].t1); rd(a[i].t2); } sort(a + 1, a + n + 1, cmp); for(int i = 1; i <= n; i++) { sum += a[i].t1; q.push({a[i].t1, i}); if(sum <= a[i].t2) ans++; else sum -= q.top().first, q.pop(); } fp(ans); return 0; } 1.3 搜索 & 模拟
P12684 叉叉学习魔法
考虑直接 bfs，容易想到记录当前位置、最小步数 (t1) 和最少魔法使用次数 (t2)，用堆维护可以做到 (O(nmlog (nm)))。但是这样会超时倒闭，所以考虑用 01bfs，将 (t1+1) 的新状态加到队尾，(t2+1) 的新状态加到队头，这样相当于线性维护了之前的堆，可以把 (log) 去掉做到 (O(nm))。当然，在此之前 (t1,t2) 没改的状态要从队头取出，否则会破坏单调性。
#include <iostream> #include <deque> #include <vector> using namespace std; const int N = 5005; int n, m, x1, y1, x2, y2; char a[N][N]; bool vis[N][N]; struct node { int x, y, t1, t2; bool operator < (const node &rhs) const { if(t1 != rhs.t1) return t1 > rhs.t1; return t2 > rhs.t2; } }; deque<node> q; vector<node> v1, v2; const int dx1[] = {-1, 1, 0, 0}, dy1[] = {0, 0, -1, 1}; const int dx2[] = {-1, -1, 1, 1}, dy2[] = {-1, 1, -1, 1}; void _01bfs() { q.push_front((node){x1, y1, 0, 0}); while(!q.empty()) { node u = q.front(); while(!q.empty() && u.t1 == q.front().t1 && u.t2 == q.front().t2) { u = q.front(); q.pop_front(); if(u.x == x2 && u.y == y2) { printf("%d %d", u.t1, u.t2); return; } if(vis[u.x][u.y]) continue; vis[u.x][u.y] = 1; for(int i = 0; i < 4; i++) { int nx = u.x + dx1[i], ny = u.y + dy1[i]; if(!nx || !ny || nx == n + 1 || ny == m + 1 || a[nx][ny] == '#') continue; v1.push_back({nx, ny, u.t1 + 1, u.t2}); } for(int i = 0; i < 4; i++) { int nx = u.x + dx2[i], ny = u.y + dy2[i]; if(!nx || !ny || nx == n + 1 || ny == m + 1 || a[nx][ny] == '#') continue; v2.push_back({nx, ny, u.t1, u.t2 + 1}); } } for(auto v : v2) q.push_front(v); for(auto v : v1) q.push_back(v); v1.clear(), v2.clear(); } printf("-1 -1"); return; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", a[i] + 1); for(int j = 1; j <= m; j++) { if(a[i][j] == 'X') x1 = i, y1 = j; else if(a[i][j] == 'W') x2 = i, y2 = j; } } _01bfs(); return 0; } P8817 [CSP-S 2022] 假期计划
布什戈门，说好的折半呢？？？这哪里有啊？
先暴力处理两两之间的连通性，复杂度 (O(n^2))。处理的时候每个点存可以抵达的点中权值最大的三个点。最后算答案的时候直接四重循环更新答案，但是由于我们之前存的是三个可以抵达的最大权值点，所以显然复杂度只有 (O(n^2))。
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2505, M = 20005; inline void rd(int &x) {scanf("%lld", &x);} inline void fp(int &x) {printf("%lld", x);} inline void hh() {putchar('n');} inline void kg() {putchar(' '); } int n, m, k, val[N]; int head[N], totot; int dis[N]; bool to[N][N]; vector<int> g[N]; struct EDGE {int nxt, to; } edge[M]; inline void addedge(int u, int v) { edge[++totot].to = v, edge[totot].nxt = head[u], head[u] = totot; return; } inline bool cmp(int x, int y) { return val[x] > val[y]; } inline void bfs(int x) { for(int i = 1; i <= n; i++) dis[i] = -1; dis[x] = 0; queue<int> q; q.push(x); while(!q.empty()) { int u = q.front(); q.pop(); if(u != x) { to[x][u] = 1; if(x != 1 && to[1][u]) { g[x].push_back(u); sort(g[x].begin(), g[x].end(), cmp); if(g[x].size() > 3) g[x].pop_back(); } } if(dis[u] == k + 1) continue; for(int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].to; if(dis[v] == -1) { dis[v] = dis[u] + 1; q.push(v); } } } } signed main() { rd(n), rd(m), rd(k); for(int i = 2; i <= n; i++) { rd(val[i]); } for(int i = 1; i <= m; i++) { int x, y; rd(x), rd(y); addedge(x, y), addedge(y, x); } for(int i = 1; i <= n; i++) bfs(i); int ans = 0; for(int i = 2; i <= n; i++) { for(int j = 2; j <= n; j++) { if(to[i][j]) { for(int k : g[i]) { for(int l : g[j]) { if(j != k && i != l && k != l) { ans = max(ans, val[i] + val[j] + val[k] + val[l]); } } } } } } fp(ans); return 0; } 
