202206007 模拟赛 总结

盖房子

n×nn×n 的矩形中选出一个边长为 k×kk×k 的子矩阵，使得中位数最小

中位数定义为子矩阵中第 ⌊k22⌋+1⌊k22⌋+1 大的数，n≤800n≤800

比较显然的二分，二分答案 midmid 。另 bi,j=[ai,j>mid]bi,j=[ai,j>mid] ，作二维前缀和

如果 bb 存在子矩阵使得 s≤⌊k22⌋s≤⌊k22⌋ ，则 midmid 可行且可以缩小，反之需要增大，O(n2logn2)O(n2logn2)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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)×(2n+1)(2n+1)×(2n+1) 的棋盘，行、列的编号都为 0,1,⋯,2n0,1,⋯,2n ，棋盘上有 mm 个棋子。

在 (0,n)(0,n) 开始移动。设当前在 (i,j)(i,j)

• 若 (i+1,j)(i+1,j) 没有棋子且没有出界，可以移动到 (i+1,j)(i+1,j)
• 若 (i+1,j−1)(i+1,j−1) 没有棋子且没有出界，可以移动到 (i+1,j−1)(i+1,j−1)
• 若 (i+1,j+1)(i+1,j+1) 没有棋子且没有出界，可以移动到 (i+1,j+1)(i+1,j+1)

求能到达第 2n2n 行的位置的数量，n≤109,m≤2×105n≤109,m≤2×105

最终的答案可以转换为起点最后能否到达一些纵坐标。（一直往下走即可）

用 set 维护，排序后依次处理，设当前棋子在 (x,y)

• y−1 或 y+1 能到，且 y 不能到，则需要加入 set
• y−1 和 y+1 都不能到，且之前 y 能到，则需要从 set 中删除

答案为最终集合大小，O(mlogm)

注意同一行需要同时处理，暂存一下即可

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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 个数 ai ，初始可以删除最多 K 个数

一次操作为选出最大的 ai ，删除所有大于 max2 的数。

求最小化操作次数的前提下，最少删除数的个数，n≤2×105

排序，设 fi,j 为前 i 个用了 j 次操作最少删除，其中 1≤j≤log2a

则 fi,j=min(fi−1,j+1,fk,j−1) ，k 表示高度不超过 ai2 的数的编号

转移为 O(1) ，状态数 O(nlogn) ，总 O(nlogn)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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≥T ，求删除边的最大年龄最小

n,m≤105

又是二分，二分删除的最大年龄，则所有 k>mid 的边都可以走，算最短路

若 dis≥T 则 mid 可行且可以更小，否则需要增大，O(nlognlogm)

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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 在 105 级也不要放弃 DP