关于我想了好久才想出这题咋做这档事 - 6

发表于 更新于 分类于
ABC070D, CF609E, CF1301E, CF1527D, UVA1707, POJ3419, HDU3183 题解

#0.0 写在前面

自从某天之后，题解都是单篇发了，于是“关于我想了好久才想出这题咋做这档事”这个标题就算是荒废了，正巧最近发现暑假在 ZR 学的东西，回来补的题，由于疏于整理，根本记不住，就想着写博客总结一下，于是就让这个标题借尸还魂重获新生了。

#Prob. 1 ABC070D Transit Tree Path

Time Limit: 2s | Memory Limit: 256MB

#题意简述

给出一棵有 \(n(n\leq10^5)\) 个结点的树和指定节点 \(K\)，给出 \(q(q\leq10^5)\) 个询问，求结点 \(x_i\) 过结点 \(K\) 到节点 \(y_i\) 的最短距离。

#大体思路

直接以 \(K\) 为根，\(O(n)\) 处理出 \(K\) 到任意一个点的距离，询问时直接回答距离和即可。

#Code

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
const int N = 100010;
const int INF = 0x3fffffff;

struct Edge {int u, v, nxt; ll w;} e[N << 1];

ll n, q, k, cnt(1), head[N], lg2[N], d[N];

inline void add(int u, int v, ll w) {
    e[cnt].u = u, e[cnt].v = v, e[cnt].w = w;
    e[cnt].nxt = head[u], head[u] = cnt ++;
}

void dfs(int x, int fa) {
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].v != fa) {
          d[e[i].v] = d[x] + e[i].w;
          dfs(e[i].v, x);
      }
}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++ i)
      lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i < n; ++ i) {
        int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
        add(u, v, w); add(v, u, w);
    }
    scanf("%lld%lld", &q, &k); dfs(k, 0);
    while (q --) {
        int a, b; scanf("%d%d", &a, &b);
        printf("%lld\n", d[a] + d[b]);
    }
    return 0;
}

#Prob. 2 CF609E Minimum spanning tree for each edge

Time Limit: 2s | Memory Limit: 256MB

#题意简述

给你 \(n(n\leq2\cdot10^5)\) 个点，\(m(m\leq2\cdot10^5)\) 条边，如果对于一个最小生成树中要求必须包括第 \(i(1\leq i\leq m)\) 条边，那么最小生成树的权值总和最小是多少。

#大体思路

直接考虑 Kruscal 生成树的构造方法，每次都是将两个连通块用两者之间边权最小的边相连，那么我们考虑对于第 \(i\) 条边 \(u\to v\)，如果要把它包含进生成树，那么此时树上一定有且仅有一个包含 \(u,v\) 的环，于是一定要删掉最小生成树上 \(u\) 到 \(v\) 的路径上的边权最大的边。

我们可以 \(O(m\log m)\) 求出最小生成树，然后 \(O(n\log n)\) 倍增处理 \(x\) 到 \(2^k\) 级祖先的路径上的最大值，枚举每条边 \(O(\log n)\) 回答即可。

#Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
const int N = 400010;
const int INF = 0x3fffffff;

struct Edge {
    int u, v, w, id, nxt;

    inline bool operator < (const Edge b) const {
        return w < b.w;
    }
};
Edge e[N], ue[N];

int n, m, head[N], cnt = 1, fa[N], vis[N], dep[N];
int inmst[N], sum, f[N][30], g[N][30], lg2[N], lt, ans[N];

template <typename T>
inline T Max(const T a, const T b) {
    return a > b ? a : b;
}

inline void add(int u, int v, int w, int id) {
    e[cnt].u = u, e[cnt].v = v, e[cnt].w = w;
    e[cnt].id = id, e[cnt].nxt = head[u], head[u] = cnt ++;

    e[cnt].u = v, e[cnt].v = u, e[cnt].w = w;
    e[cnt].id = id, e[cnt].nxt = head[v], head[v] = cnt ++;
}

inline int find(int x) {
    while (x != fa[x])
      x = fa[x] = fa[fa[x]];
    return x;
}

inline void kruskal() {
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    sort(ue + 1, ue + m + 1);
    for (int i = 1; i <= m; ++ i) {
        int af = find(ue[i].u);
        int bf = find(ue[i].v);
        if (af != bf) {
            add(ue[i].u, ue[i].v, ue[i].w, ue[i].id);
            sum += ue[i].w, fa[af] = bf, inmst[ue[i].id] = true;
        }
    }
}

inline void get_log() {
    lg2[1] = 0;
    for (int i = 2; i <= n; ++ i)
      lg2[i] = lg2[i >> 1] + 1;
}

inline void doubly() {
    queue <int> q; q.push(1); vis[1] = 1, dep[1] = 1;
    while (q.size()) {
        int now = q.front(); q.pop();
        for (int i = head[now]; i; i = e[i].nxt) {
            if (vis[e[i].v]) continue;
            int y = e[i].v; vis[e[i].v] = 1;
            f[y][0] = now, g[y][0] = e[i].w, dep[y] = dep[now] + 1;
            for (int j = 1; j <= lt; j ++) {
                f[y][j] = f[f[y][j - 1]][j - 1];
                g[y][j] = Max(g[y][j - 1], g[f[y][j - 1]][j - 1]);
            }
            q.push(y);
        }
    }
}

inline int query(int x, int y) {
    int res = 0;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = lt; i >= 0; i --)
      if (dep[f[x][i]] >= dep[y])
        res = Max(res, g[x][i]), x = f[x][i];
    if (x == y) return res;
    for (int i = lt; i >= 0; -- i)
      if (f[x][i] != f[y][i]) {
          res = Max(res, Max(g[x][i], g[y][i]));
          x = f[x][i], y = f[y][i];
      }
    res = Max(res, Max(g[x][0], g[y][0]));
    return res;
}

signed main(){
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; ++ i) {
        scanf("%lld%lld%lld", &ue[i].u, &ue[i].v, &ue[i].w);
        ue[i].id = i;
    }
    kruskal(); get_log(); lt = lg2[n]; doubly();
    for (int i = 1; i <= m; ++ i)
      if (inmst[ue[i].id]) ans[ue[i].id] = sum;
      else ans[ue[i].id] = sum - query(ue[i].u, ue[i].v) + ue[i].w;
    for (int i = 1; i <= m; ++ i) printf("%lld\n", ans[i]);
    return 0;
}

#Prob. 3 CF1301E Nanosoft

Time Limit: 2s | Memory Limit: 512MB

#题意简述

给你一个 \(n\times m(n,m\leq500)\) 的只包含四种颜色的网格。

\(q(q\leq3\times10^5)\) 次询问，每次问一个矩阵中所包含的形如以下格式的 Logo 的最大面积。

#大体思路

我们要求一个区间内的最大/最小值，不带修，首先可以考虑用 st 表。

我们先定一个基准点，这里本人选择了红色区域的右下角作为基准点，首先需要处理出以每个基准点为中心的位置最大范围的合法矩形的半径，这个可以通过对四种颜色分别做二维前缀和+二分答案进行预处理。

之后就是令人《神清气爽》的二维 st 表，当然本质上与一维并没有太多的区别，我们指定一维的优先级高于另一维，当优先级高的一维大小大于 \(1\) 时就二分这一维，否则二分另一维，显然这样是可以得到正确的答案的。

然后我们就可以二分答案最大的半径，然后就可以判定这个区间内的最大半径是不是大于当前的半径，于是就解决了这个问题。

这份代码写于 2021.7.18，当我于 2021.11.1 写本篇博客时，突然意识到我们完全可以直接得到这个区间的最大值，为什么要再二分一次呢？不能理解QnQ

#Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
const int N = 510;
const int INF = 0x3fffffff;

template <typename T> inline T Max(const T a, const T b) {return a > b ? a : b;}

template <typename T> inline T Min(const T a, const T b) {return a < b ? a : b;}

int n, m, q, mp[N][N], sum[5][N][N], t[N][N];
int lg2[N], st[N][N][10][10], ln, lm;

inline bool pre_check(int x, int y, int p) {
    int res[5] = {0};
    res[1] = sum[1][x][y] - sum[1][x - p][y] - sum[1][x][y - p] + sum[1][x - p][y - p];
    res[2] = sum[2][x][y + p] - sum[2][x][y] - sum[2][x - p][y + p] + sum[2][x - p][y];
    res[3] = sum[3][x + p][y + p] - sum[3][x][y + p] - sum[3][x + p][y] + sum[3][x][y];
    res[4] = sum[4][x + p][y] - sum[4][x][y] - sum[4][x + p][y - p] + sum[4][x][y - p];
    if (res[1] == p * p && res[2] == p * p && res[3] == p * p && res[4] == p * p)
      return true;
    else return false;
}

inline void get_st() {
    ln = lg2[n], lm = lg2[m];
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j)
        st[i][j][0][0] = t[i][j];
    for (int i = 0; i <= ln; ++ i)
      for (int j = 0; j <= lm; ++ j) {
          if (!i && !j) continue;
          for (int x = 1; x + (1 << i) - 1 <= n; ++ x)
            for (int y = 1; y + (1 << j) - 1 <= m; ++ y) {
                if (i) {
                    st[x][y][i][j] = Max(st[x][y][i - 1][j], st[x + (1 << (i - 1))][y][i - 1][j]);
                } else {
                    st[x][y][i][j] = Max(st[x][y][i][j - 1], st[x][y + (1 << (j - 1))][i][j - 1]);
                }
            }
      }
}

inline bool check(int r1, int c1, int r2, int c2, int p) {
    r1 += p - 1, c1 += p - 1, r2 -= p, c2 -= p;
    int k1 = lg2[r2 - r1 + 1], k2 = lg2[c2 - c1 + 1];
    int res1 = st[r1][c1][k1][k2];
    int res2 = st[r1][c2 - (1 << k2) + 1][k1][k2];
    int res3 = st[r2 - (1 << k1) + 1][c1][k1][k2];
    int res4 = st[r2 - (1 << k1) + 1][c2 - (1 << k2) + 1][k1][k2];
    int res = Max(Max(res1, res2), Max(res3, res4));
    if (res >= p) return true; else return false;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    lg2[1] = 0;
    for (int i = 2; i <= Max(n, m); ++ i)
      lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
          char c; cin >> c;
          if (c == 'R') mp[i][j] = 1;
          else if (c == 'G') mp[i][j] = 2;
          else if (c == 'B') mp[i][j] = 3;
          else mp[i][j] = 4;
      }
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
          sum[1][i][j] = sum[1][i][j - 1] + sum[1][i - 1][j] - sum[1][i - 1][j - 1] + (mp[i][j] == 1);
          sum[2][i][j] = sum[2][i][j - 1] + sum[2][i - 1][j] - sum[2][i - 1][j - 1] + (mp[i][j] == 2);
          sum[3][i][j] = sum[3][i][j - 1] + sum[3][i - 1][j] - sum[3][i - 1][j - 1] + (mp[i][j] == 3);
          sum[4][i][j] = sum[4][i][j - 1] + sum[4][i - 1][j] - sum[4][i - 1][j - 1] + (mp[i][j] == 4);
      }
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        int l = 0, res = 0;
        int r = Min(Min(i, j), Min(n - i, m - j));
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (pre_check(i, j, mid))
              res = mid, l = mid + 1;
            else r = mid - 1;
        }
        t[i][j] = res;
      }
    get_st();
    while (q --) {
        int r1, c1, r2, c2, l = 0, res = 0;
        scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
        int r = Min((r2 - r1 + 1) >> 1, (c2 - c1 + 1) >> 1);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(r1, c1, r2, c2, mid))
              res = mid, l = mid + 1;
            else r = mid - 1;
        }
        printf("%d\n", 4 * res * res);
    }
    return 0;
}

#Prob. 4 CF1527D MEX Tree

#Prob. 5 UVA1707 Surveillance

#题意简述

给定一个长度为 \(n(n\leq10^6\)) 的环，有 \(k(k\leq 10^6)\) 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。

#大体思路

遇到环上问题，我们先不考虑环，先考虑链。如果是链的话，我们直接预处理出把每个位置覆盖住的线段最右端点是哪个位置，然后贪心就可以了。这个做法 \(O(n)\).

我们考虑断环为链，复制一段接在尾端，如果我们直接枚举左端点暴力做的话是 \(O(n^2)\) ，考虑用倍增优化这个过程，预处理出走 \(2^i\) 步能走到的位置，就可以做了。时间复杂度 \(O(n\log n)\).

#Code

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
51
52
53
54
55
56
57
58
59
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 3000010;
const int INF = 0x3fffffff;

template <typename T>
inline T Max(const T a, const T b) {
    return a > b ? a : b;
}

template <typename T>
inline T Min(const T a, const T b) {
    return a < b ? a : b;
}

int n, k, lg[N], mr[N], nxt[N], xtr[N][30], ans;

inline void clear() {
    ans = INF;
    mset(mr, 0); mset(nxt, 0); mset(xtr, 0);
}

int main() {
    for (int i = 2; i <= 2e6; ++ i) lg[i] = lg[i >> 1] + 1;
    while (scanf("%d%d", &n, &k) != EOF) {
        clear();
        for (int i = 1; i <= k; ++ i) {
            int l, r; scanf("%d%d", &l, &r);
            if (r < l) {r += n;} mr[l] = Max(mr[l], r);
        }
        int maxr = 0;
        for (int i = 1; i <= n << 1; ++ i) {
            if (mr[i]) {
                if (nxt[i - 1] != INF)
                  nxt[i] = Max(nxt[i - 1], mr[i]);
                else nxt[i] = mr[i];
                maxr = Max(maxr, mr[i]);
            } else if (maxr >= i) nxt[i] = nxt[i - 1];
            else nxt[i] = INF;
            xtr[i][0] = nxt[i] + 1;
        }
        for (int i = 1; i <= lg[n << 1]; ++ i) {
            for (int j = 1; j <= n << 1; ++ j) {
                if (xtr[j][i - 1] >= INF) xtr[j][i] = INF;
                else xtr[j][i] = xtr[xtr[j][i - 1]][i - 1];
            }
        }
        for (int i = 1; i <= n; ++ i) {
            int now = i, res = 0;
            for (int j = lg[n << 1]; j >= 0; -- j)
              if (xtr[now][j] < i + n)
                res += (1 << j), now = xtr[now][j];
            if (xtr[now][0] <= INF) ans = Min(ans, res);
        }
        if (ans != INF) printf("%d\n", ans + 1);
        else printf("impossible\n");
    }
    return 0;
}

#Prob. 6 POJ3419 Difference Is Beautiful

#Prob. 7 HDU3183 A Magic Lamp

Time Limit: 2s | Memory Limit: 32MB

#题意简述

给定一个有 \(n(n\leq1000)\) 位的数，你可以删掉其中的任意 \(m(m\leq1000)\) 位，剩余的数位向左合并，要求得到的新数最小。

#大体思路

转化一下题意，我们也就是要找到 \(n-m\) 位最小的数作为答案，我们从高位到低位进行贪心，显然第一位可以选的区间是 \([1,n-(n-m-1)]\)，我们肯定要选这个区间内最小的数位，设这个数位为 \(x_1\)，之后每一位依次类推，可选区间应当是 \([x_1, n-(n-m-2)],[x_2,n-(n-m-3)]\dots\)，于是我们可以用 st 表提前处理，做到 \(O(1)\) 回答，时间复杂度为 \(O(n\log n)\).

#Code

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
const int N = 100010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, m, mn[10][N], lg[N]; char s[N], ans[N];

inline int MIN(int x, int y) {return s[x] <= s[y] ? x : y;}

inline int query(int l, int r) {
    int k = lg[r - l + 1];
    return MIN(mn[k][l], mn[k][r - (1 << k) + 1]);
}

int main() {
    for (int i = 2; i <= 1000; ++ i) lg[i] = lg[i >> 1] + 1;
    while (~scanf("%s%d", s + 1, &m)) {
        n = strlen(s + 1);
        for (int i = 1; i <= n; ++ i) mn[0][i] = i;
        for (int i = 1; i <= lg[n]; ++ i)
          for (int j = 1; j + (1 << i) - 1 <= n; ++ j)
            mn[i][j] = MIN(mn[i - 1][j], mn[i - 1][j + (1 << i - 1)]);
        int pos = 1, apos = 1, st = 1;
        for (int i = n - m - 1; ~i; -- i) {
            pos = query(pos, n - i);
            ans[apos] = s[pos ++], apos ++;
        }
        for (st = 1; st < apos && ans[st] == '0'; ++ st) ;
        if (st >= apos) {puts("0"); continue;}
        for (int i = st; i < apos; ++ i) putchar(ans[i]); puts("");
    }
    return 0;
}