盖房子
/(n/times n/) 的矩形中选出一个边长为 /(k/times k/) 的子矩阵，使得中位数最小
中位数定义为子矩阵中第 /(/lfloor/dfrac{k^2}{2}/rfloor+1/) 大的数，/(n/le 800/)
比较显然的二分，二分答案 /(mid/) 。另 /(b_{i,j}=[a_{i,j}>mid]/) ，作二维前缀和
如果 /(b/) 存在子矩阵使得 /(s/le/lfloor/dfrac{k^2}{2}/rfloor/) ，则 /(mid/) 可行且可以缩小，反之需要增大，/(O(n^2/log n^2)/)
#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 805; int n, K, a[N][N], s[N][N], t[N * N], le, L, R, mid, res; inline bool chk(int val) { memset(s, 0, sizeof(s)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] > val); for (int i = K, x, y, t; i <= n; i++) for (int j = K; j <= n; j++) { x = i - K + 1, y = j - K + 1; t = s[i][j] - s[x - 1][j] - s[i][y - 1] + s[x - 1][y - 1]; if (t <= K * K / 2) return true; } return false; } int main() { scanf("%d%d", &n, &K); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]), t[++le] = a[i][j]; sort(t + 1, t + le + 1); le = unique(t + 1, t + le + 1) - t - 1; L = 1, R = le; while (L <= R) { mid = L + R >> 1; if (chk(t[mid])) res = mid, R = mid - 1; else L = mid + 1; } printf("%d", t[res]); } 移动棋子
/((2n+1)/times(2n+1)/) 的棋盘，行、列的编号都为 /(0,1,/cdots,2n/) ，棋盘上有 /(m/) 个棋子。
在 /((0,n)/) 开始移动。设当前在 /((i,j)/)
- 若 /((i+1,j)/) 没有棋子且没有出界，可以移动到 /((i+1,j)/)
- 若 /((i+1,j-1)/) 没有棋子且没有出界，可以移动到 /((i+1,j-1)/)
- 若 /((i+1,j+1)/) 没有棋子且没有出界，可以移动到 /((i+1,j+1)/)
求能到达第 /(2n/) 行的位置的数量，/(n/le 10^9,m/le 2/times 10^5/)
最终的答案可以转换为起点最后能否到达一些纵坐标。（一直往下走即可）
用 set 维护，排序后依次处理，设当前棋子在 /((x,y)/)
- /(y-1/) 或 /(y+1/) 能到，且 /(y/) 不能到，则需要加入
set - /(y-1/) 和 /(y+1/) 都不能到，且之前 /(y/) 能到，则需要从
set中删除
答案为最终集合大小，/(O(m/log m)/)
注意同一行需要同时处理，暂存一下即可
#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 4e5 + 5; int n, m, res, b[N], c[N], t1, t2; struct P { int x, y; } a[N]; set<int> s; inline int f(int x) { return s.find(x) != s.end(); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d", &a[i].x, &a[i].y); sort(a + 1, a + m + 1, [](P A, P B) { return A.x ^ B.x ? A.x < B.x : A.y < B.y; }); s.insert(n); for (int i = 1, y; i <= m + 1; i++) { if (a[i].x ^ a[i - 1].x) { while (t1) s.insert(b[t1--]); while (t2) s.erase(c[t2--]); } if (i > m) break; y = a[i].y; if ((f(y - 1) || f(y + 1)) && !f(y)) b[++t1] = y; if ((!f(y - 1) && !f(y + 1)) && f(y)) c[++t2] = y; } res = s.size(); printf("%d", res); } 清理花园
/(n/) 个数 /(a_i/) ，初始可以删除最多 /(K/) 个数
一次操作为选出最大的 /(a_i/) ，删除所有大于 /(/frac{max}{2}/) 的数。
求最小化操作次数的前提下，最少删除数的个数，/(n/le 2/times 10^5/)
排序，设 /(f_{i,j}/) 为前 /(i/) 个用了 /(j/) 次操作最少删除，其中 /(1/le j/le/log_2 a/)
则 /(f_{i,j}=/min(f_{i-1,j}+1,f_{k,j-1})/) ，/(k/) 表示高度不超过 /(/frac{a_i}{2}/) 的数的编号
转移为 /(O(1)/) ，状态数 /(O(n/log n)/) ，总 /(O(n/log n)/)
#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5, INF = 0x3f3f3f3f; int n, K, a[N], f[N][35], mx; int main() { scanf("%d%d", &n, &K); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); memset(f, 0x3f, sizeof(f)); f[0][0] = 0; for (int i = 1, k; i <= n; i++) { k = upper_bound(a + 1, a + n + 1, a[i] / 2) - a - 1; mx = log2(a[i]) + 1; f[i][0] = f[i - 1][0] + 1; for (int j = 1; j <= mx; j++) f[i][j] = min(f[i - 1][j] + 1, f[k][j - 1]); } for (int i = 0; i <= mx; i++) if (f[n][i] < INF && f[n][i] <= K) return printf("%d %d", i, f[n][i]), 0; } 疫情延迟
/(n/) 点 /(m/) 边的有向图，一条边为 /((u,v,w,k)/) ，其中 /(k/) 表示这一条边的年龄
要求删除一些边，使的从 1 到 /(n/) 的最短路 /(dis/ge T/) ，求删除边的最大年龄最小
/(n,m/le 10^5/)
又是二分，二分删除的最大年龄，则所有 /(k>mid/) 的边都可以走，算最短路
若 /(dis/ge T/) 则 /(mid/) 可行且可以更小，否则需要增大，/(O(n/log n/log m)/)
#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5, INF = 0x3f3f3f3f; int n, m, T, lst[N], Ecnt, L, R, b[N], le, mid, res, dis[N], vis[N]; struct Ed { int to, nxt, qz, cs; } e[N]; inline void Ae(int fr, int go, int vl, int k) { e[++Ecnt] = (Ed){ go, lst[fr], vl, k }, lst[fr] = Ecnt; } struct P { int x, d; bool operator < (P A) const { return d > A.d; } }; priority_queue<P> Q; inline bool chk(int val) { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[1] = 0; Q.push((P){ 1, 0 }); while (!Q.empty()) { int u = Q.top().x; Q.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = lst[u], v; i; i = e[i].nxt) if (dis[u] + e[i].qz < dis[v = e[i].to] && e[i].cs > val) dis[v] = dis[u] + e[i].qz, Q.push((P){ v, dis[v] }); } return dis[n] >= T; } int main() { scanf("%d%d%d", &n, &m, &T); for (int i = 1, u, v, w, k; i <= m; i++) scanf("%d%d%d%d", &u, &v, &w, &k), Ae(u, v, w, k), b[++le] = k; if (chk(0)) return printf("-1 %d", dis[n]), 0; sort(b + 1, b + le + 1); le = unique(b + 1, b + le + 1) - b - 1; L = 1, R = le, res = b[le] + 1; while (L <= R) { mid = L + R >> 1; if (chk(b[mid])) res = min(res, b[mid]), R = mid - 1; else L = mid + 1; } printf("%d", res); } 总结
- 二分不要打挂，注意
check - 注意情况考虑全
- /(n/) 在 /(10^5/) 级也不要放弃
DP
