Glucoco
0%

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 1442 - 形成两个异或相等数组的三元组数目

记 \(S_i\) 为 \(x_0\) 到 \(x_i\) 的 \(\rm xor\) 和。

如果 \(S_i = S_j\)，那么说明 \([i - 1, j]\) 区间的 \(\rm xor\) 和为 \(0\)，这个区间对答案的贡献为 \(j - i - 1\)。

假设 \(S\) 序列中值为 \(t\) 的数字的位置组成了序列 \(p_0, p_2, p_3, ..., p_{n - 1}\)

那么 \(t\) 对应的这个序列对答案的贡献是：

\[ \begin{aligned} & \sum_{i = 0}^{n - 1} \sum_{j = 0}^{i - 1} p_i - p_j - 1 \\ = & \sum_{i = 0}^{n - 1} \left[ \sum_{j = 0}^{i - 1} p_i - \sum_{j = 0}^{i - 1} p_j - \sum_{j = 0}^{i - 1} 1 \right] \\ = & \sum_{i = 0}^{n - 1} \left[ i \times p_i - \sum_{j = 0}^{i - 1} p_j - i \right] \end{aligned} \]

其中 \(\sum_{j = 0}^{i - 1} p_j\) 可以在线性的时间内预处理出来，或者对 \(i\) 枚举的时候直接算。

于是上面这个算式就可以在线性时间内算出来。

对每个 \(t\)，都算这个式子。

时间 / 空间都是 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<int, vector<int>> h;
    int countTriplets(vector<int>& arr) {
        h[0].push_back(-1);
        int cur_xor_sum = 0, i = 0;
        for (const auto &x: arr) {
            cur_xor_sum ^= x;
            h[cur_xor_sum].push_back(i);
            ++i;
        }

        int ans = 0;
        for (const auto &[k, v]: h) {
            int n = v.size(), pre = 0;
            for (int i = 0; i < n; ++i) {
                ans += i * v[i] - pre - i;
                pre += v[i];
            }
        }

        return ans;
    }
};

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 1825 - 求出 MK 平均值（第 236 场周赛第四题）

思路

我们需要动态维护一个长度为 \(m\) 的容器，当容器的长度超过 \(m\) 时，根据先进先出的原则对元素进行淘汰。这一点很自然想到使用队列。

我们要对容器中的元素统计第 \(k + 1\) 个到第 \(m - k\) 个的和，这显然是一个区间询问，我们需要选择一种数据结构，于是看怎么修改。这里之后添加和淘汰需要用到修改操作，是单点修改（加 / 减），于是我们可以用树状数组来解决这个问题。

我们定义两个树状数组：\(\rm cnt\) 和 \(\rm sum\)，\(\rm cnt\) 用来维护元素个数的前缀和，\(\rm sum\) 用来维护元素的前缀和。当我们需要获得第 \(k\) 个元素的时候，可以现在 \(\rm cnt\) 中二分第 \(k\) 个元素是什么，然后用 \(\rm sum\) 来统计答案。

代码

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
using LL = long long;

const int MAX_N = int(1E5) + 5;

struct BinaryIndexedTree {
    LL c[MAX_N];
    int maxPos;
    
    BinaryIndexedTree() {}
    BinaryIndexedTree(int maxPos) {
        this->maxPos = maxPos;
        for (int i = 0; i <= maxPos; ++i) c[i] = 0;
    }

    inline int lowbit(const int &u) {
        return u & (-u);
    }

    void add(int pos, int k) {
        while (pos <= maxPos) {
            c[pos] += k; pos += lowbit(pos);
        }
    }

    LL sum(int pos) {
        LL ret = 0;
        while (pos >= 1) {
            ret += c[pos]; pos -= lowbit(pos);
        }
        return ret;
    }
};

class MKAverage {
public:
    BinaryIndexedTree cnt, sum;
    int node_tot, m, k;
    queue<int> q;
    
    MKAverage(int m_, int k_) {
        cnt = BinaryIndexedTree(1E5);
        sum = BinaryIndexedTree(1E5);
        node_tot = 0;
        m = m_;
        k = k_;
    }
    
    void addElement(int num) {
        cnt.add(num, 1);
        sum.add(num, num);
        q.push(num);
        ++node_tot;

        if (node_tot > m) {
            auto f = q.front();
            q.pop();
            cnt.add(f, -1);
            sum.add(f, -f);
            --node_tot;
        }
    }
    
    // 第 p 个元素在 BIT 中的 index
    int pre_index(int p) {
        int l = 1, r = 1E5;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (cnt.sum(mid) < p) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        
        return l;
    } 
    
    int calculateMKAverage() {
        if (node_tot < m) {
            return -1;
        }
        
        int l = pre_index(k);
        int r = pre_index(node_tot - k);
        
        if (l == r) {
            return l;
        }
        
        LL ans = sum.sum(r - 1) - sum.sum(l);
        ans += 1LL * l * (cnt.sum(l) - k);
        ans += 1LL * r * (node_tot - k - cnt.sum(r - 1));
        ans = (ans / (node_tot - 2 * k));
        
        return ans;
    }
};

复杂度

记询问次数为 \(q\)，\(\rm num\) 和 \(m\) 的最大值都是 \(n\)（即本题的 \(10^5\)）。

  • 时间复杂度：\(O(q \times (\log n)^2)\)。\((\log n)^2\) 表示在树状数组上二分的复杂度。
  • 空间复杂度：\(O(q + n)\)。

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 329 - 矩阵中的最长递增路径

思路

类似 计蒜客 42397 - Digital Path（ICPC 2019 南京现场赛 C 题）。

如果相邻的 \(x < y\)，建一条从 \(x\) 的坐标到 \(y\) 的坐标的有向边，对图进行拓扑排序，然后按照拓扑顺序来 DP。

定义 \(f(x, y)\) 是以 \((x, y)\) 结尾的满足条件的最长路径。

转移方程：

\[f(x, y) = \max(f(x, y), f(x_p, y_p) + 1)\]

当且仅当 \((x_p, y_p)\) 到 \((x, y)\) 有边的时候发生转移。

所有的点都可以初始化 \(f(x, y) = 1\)。

代码

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
struct Coordinate {
    int x, y;
};

class Solution {
public:
    static constexpr int dx[] = {0, 0, -1, 1};
    static constexpr int dy[] = {-1, 1, 0, 0};
    static constexpr int MAX_N = 200 + 5;

    vector<vector<int>> a, in_deg, f;
    int n, m;
    Coordinate s[MAX_N * MAX_N];

    bool is_valid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    void get_topological_order() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                for (int dir = 0; dir < 4; ++dir) {
                    int nx = i + dx[dir], ny = j + dy[dir];
                    if (is_valid(nx, ny) && a[i][j] < a[nx][ny]) {
                        ++in_deg[nx][ny];
                    }
                }
            }
        }

        queue<Coordinate> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (in_deg[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        int s_ptr = 0;
        while (!q.empty()) {
            auto frt = q.front();
            q.pop();
            s[s_ptr++] = frt;

            for (int dir = 0; dir < 4; ++dir) {
                int nx = frt.x + dx[dir], ny = frt.y + dy[dir];
                if (is_valid(nx, ny) && a[frt.x][frt.y] < a[nx][ny] && (--in_deg[nx][ny]) == 0) {
                    q.push({nx, ny});
                }
            }
        }
    }

    int longestIncreasingPath(vector<vector<int>>& a_) {
        a = a_;
        n = a.size();
        m = a[0].size();
        in_deg = vector<vector<int>>(n, vector<int>(m, 0));
        f = vector<vector<int>>(n, vector<int>(m, 0));

        get_topological_order();

        int tot = n * m, ans = 0;
        for (int i = 0; i < tot; ++i) {
            f[s[i].x][s[i].y] = 1;
            for (int dir = 0; dir < 4; ++dir) {
                int pre_x = s[i].x + dx[dir], pre_y = s[i].y + dy[dir];
                if (is_valid(pre_x, pre_y) && a[pre_x][pre_y] < a[s[i].x][s[i].y]) {
                    f[s[i].x][s[i].y] = max(f[s[i].x][s[i].y], f[pre_x][pre_y] + 1);
                }
            }
            ans = max(ans, f[s[i].x][s[i].y]);
        }

        return ans;
    }
};

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2019 南京现场赛 C 题: Digital Path

思路

我们需要在相邻的 \(x\) 和 \(x + 1\) 之间建一条有向边。

定义 \(f(x, y, r)\) 为从一个入度为 \(0\) 的点开始，以坐标 \((x, y)\) 结尾，距离长度 \(4\) 还差长度 \(r\) 的最长路。

  • 当长度 \(L\) 小于 \(4\) 时，\(r = 4 - L\)
  • 否则 \(r = 0\)

定义好了这个状态，我们就可以做动态规划了。

对于 \(r \in \{0, 1, 2, 3\}\)：

\[f(x, y, r) = f(x_p, y_p, r + 1) + f(x, y, r)\]

其中 \((x_p, y_p)\) 是 \((x, y)\) 的前置节点（如果有从 \((x_p, y_p)\) 到 \((x, y)\) 的边的话）。

对于 \(r = 0\) 时还有：

\[f(x, y, 0) = f(x_p, y_p, 0) + f(x, y, 0)\]

对于所有入度为 \(0\) 的节点有：

\[f(x, y, 3) = 1\]

为了避免重复计算，我们需要对整张图进行拓扑排序，然后在所有出度为 \(0\) 的点处统计答案。

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>

using namespace std;

struct Status {
    int x, y;
};

const int P = int(1E9) + 7;
const int MAX_N = 1000 + 5;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {-1, 1, 0, 0};

// opt(x, y, r)
// x, y: coordinate
// r: how far is it from 4
int n, m, a[MAX_N][MAX_N], in_deg[MAX_N][MAX_N], opt[MAX_N][MAX_N][4], ans;
char tag[MAX_N][MAX_N];
Status sorted[MAX_N * MAX_N];

bool is_valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void calculate_in_deg() {
    // edge: x -> x + 1
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                int nx = i + dx[k], ny = j + dy[k];
                if (is_valid(nx, ny) && a[nx][ny] + 1 == a[i][j]) {
                    ++in_deg[i][j];
                } 
            }
        }
    }
}

queue<Status> q;
void topological_sort() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (in_deg[i][j] == 0) {
                q.push({i, j});
                tag[i][j] = 'S';
            }
        }
    }

    int sorted_ptr = 0;
    while (!q.empty()) {
        auto f = q.front();
        q.pop();
        sorted[sorted_ptr++] = f;

        int nex_cnt = 0;
        for (int i = 0; i < 4; ++i) {
            int nx = f.x + dx[i], ny = f.y + dy[i];
            if (is_valid(nx, ny) && a[nx][ny] == a[f.x][f.y] + 1) {
                ++nex_cnt;
            }
            if (is_valid(nx, ny) && a[nx][ny] == a[f.x][f.y] + 1 && (--in_deg[nx][ny]) == 0) {
                q.push({nx, ny});
            }
        }

        if (nex_cnt == 0) {
            tag[f.x][f.y] = 'T';
        }
    }
}

void calculate() {
    int tot = n * m;
    for (int i = 0; i < tot; ++i) {
        int x = sorted[i].x, y = sorted[i].y;
        
        if (tag[x][y] == 'S') {
            opt[x][y][3] = 1;
            continue;
        }

        for (int k = 0; k < 4; ++k) {
            int pre_x = x + dx[k], pre_y = y + dy[k];
            if (is_valid(pre_x, pre_y) && a[pre_x][pre_y] + 1 == a[x][y]) {
                for (int r = 2; r >= 0; --r) {
                    opt[x][y][r] = (opt[pre_x][pre_y][r + 1] + opt[x][y][r]) % P;
                }
                opt[x][y][0] = (opt[pre_x][pre_y][0] + opt[x][y][0]) % P;
            }
        }

        if (tag[x][y] == 'T') {
            ans = (ans + opt[x][y][0]) % P;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }

    calculate_in_deg();

    topological_sort();

    calculate();

    printf("%d\n", ans);

    return 0;
}

复杂度

  • 时间复杂度：\(O(n \times m)\)。
  • 空间复杂度：\(O(n \times m)\)。

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode LCP 31 - 变换的迷宫（LCCUP 21 春季赛第 4 题）

思路

题目表示我们可以使用两个权利各一次：

  • 永久性改变
  • 暂时性改变

也就是说在第 \(i\) 个时刻，如果小力位于 \((x, y)\)，此时有四种情况：

  • 未使用「永久性改变」，未使用「暂时性改变」
  • 未使用「永久性改变」，已使用「暂时性改变」
  • 已使用「永久性改变」，未使用「暂时性改变」
  • 已使用「永久性改变」，已使用「暂时性改变」

我们可以用这几个常量来表示这四种情况（与上面一一对应）：

1
2
3
4
5
const int
    NONE_USED = 0,
    ONLY_TEMP = 1,
    ONLY_PERM = 2,
    TEMP_PERM = 3;

我们可以根据当前时刻 \(i\)、当前坐标 \((x, y)\)，以及当前的权利使用情况（即上面四种，记这个量为 \(\rm s\)，\(s \in \{ 0, 1, 2, 3 \}\)），这几个量作为状态，来递推结果，方法有点类似「分层图最短路」的思想。

设 \(f(i, x, y, s)\) 表示从 \(0\) 时刻、\((0, 0)\) 点、未使用任何权利，到当前时刻为 \(i\)，在坐标 \((x, y)\)，权利使用情况为 \(s\) 的最小时间。

类似于单源最短路径算法，我们把 \(f(0, 0, 0, {\rm NONE\_USED})\) 初始化为 \(0\)，剩下的所有状态对应的 \(f\) 设置为 \(+\infty\)，然后把二元组 \(((i, x, y, s), f(i, x, y, s))\) 扔进队列，开始做 BFS。在拓展新的状态时：

  • 新状态的 \(i\) 用旧状态的 \(i\) 加 \(1\) 得到，表示从 \(i\) 时刻转移到 \(i + 1\) 时刻
  • 新状态的 \((x', y')\) 用旧状态的 \((x, y)\) 分别叠加这五个增量：
    • \((0, 0)\)
    • \((0, 1)\)
    • \((0, -1)\)
    • \((1, 0)\)
    • \((-1, 0)\)

下面我们来对新状态的 \(s\) 进行讨论。

  • 当地图上 \({\rm mazes}(i, x, y)\) 是 .，即可行时，对 \((i, x, y, s)\) 和 \((i + 1, x', y', s)\) 做一次松弛，即如果 \(f(i, x, y, s) + 1 < f(i + 1, x', y', s)\)，就令 \(f(i + 1, x', y', s) = f(i, x, y, s) + 1\)，然后把二元组 \(((i + 1, x', y', s), f(i + 1, x', y', s))\) 加入队列。
  • 当地图上 \({\rm mazes}(i, x, y)\) 是 #，即不可行时，要对 \(s\) 进行分类：
    • 如果 \(s = {\rm ONLY\_TEMP}\)，即未使用「永久性改变」，已使用「暂时性改变」，我们需要使用一次「永久性改变」来「打通」这个位置，那么 \(s\) 将由 \({\rm ONLY\_TEMP}\) 变成 \({\rm TEMP\_PERM}\)，即我们要在 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm TEMP\_PERM})\) 之间做一次松弛
    • 如果 \(s = {\rm ONLY\_PERM}\)，这个时候要判断是对哪个点使用了「永久性改变」
      • 如果正好是当前 \((x', y')\)，那么我们可以直接松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', s)\)
      • 如果并不是当前 \((x', y')\)，我们需要使用一次「临时性改变」，即需要松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm TEMP\_PERM})\)
      • 此时我们发现，我们需要一个重要的新信息，即如果小力已经使用了「永久性改变」，我们需要知道他使用在哪个位置，这个信息在前文的讨论中是没有记录下来的。把它记录下来的办法有很多种，在这里我们可以把 \(f(i, x, y, s)\) 从一个数扩展成一个结构体，这个结构体里记录三个量 \((d, x_p, y_p)\)，其中整数 \(d\) 就是我们之前定义的 \(f\) 的值，\((x_p, y_p)\) 表示小力在 \((x_p, y_p)\) 处使用了「永久性改变」。这个「扩展」也许不是一开始就想到的，是我们在慢慢形成思路的过程中想到的。如果我们决定使用「永久性改变」，这里的 \((x_p, y_p)\) 也要随之更新。
    • 如果 \(s = {\rm NONE\_USED }\)，我们既可以选择使用一次「临时性改变」，也可以选择使用一次「永久性改变」
      • 如果选择「临时性改变」，则松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm ONLY\_TEMP})\)
      • 如果选择「永久性改变」，则松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm ONLY\_PERM})\)
    • 如果 \(s = {\rm TEMP\_PERM }\)，则两次权利都已经使用，没有办法走到这个点

最后，如果在任意一个时刻 \(i\)，任意一种 \(s\) 的情况下，终点的 \(f\) 的值不是 \(+\infty\)，说明终点是可达的。

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using LL = long long;

const int dx[] = {0, 0, 1, -1, 0};
const int dy[] = {1, -1, 0, 0, 0};
const int
    NONE_USED = 0,
    ONLY_TEMP = 1,
    ONLY_PERM = 2,
    TEMP_PERM = 3;

struct StatusValue {
    LL d;
    int px, py;
    StatusValue(LL d, int px, int py) {
        this->d = d;
        this->px = px;
        this->py = py;
    }

    StatusValue() {}
} f[100 + 1][50 + 1][50 + 1][4];

struct Status {
    int i, x, y, sc;
    StatusValue v;

    Status(int i, int x, int y, int sc, StatusValue v) {
        this->i = i;
        this->x = x;
        this->y = y;
        this->v = v;
        this->sc = sc;
    }
};

class Solution {
public:
    vector<vector<string>> mazes;
    int layers, r, c;

    bool escapeMaze(vector<vector<string>>& mazes_) {
        mazes = mazes_;
        layers = mazes.size();
        r = mazes[0].size();
        c = mazes[0][0].size();

        queue<Status> q;

        for (int i = 0; i < layers; ++i) {
            for (int x = 0; x < r; ++x) {
                for (int y = 0; y < c; ++y) {
                    for (int sc = 0; sc < 4; ++sc) {
                        f[i][x][y][sc] = StatusValue(INT_MAX, -1, -1);
                    }
                }
            }
        }

        f[0][0][0][NONE_USED] = StatusValue(0, -1, -1);
        q.push(Status(0, 0, 0, NONE_USED, f[0][0][0][NONE_USED]));

        while (!q.empty()) {
            auto frt = q.front();
            q.pop();

            int c_layer = frt.i, c_x = frt.x, c_y = frt.y, c_sc = frt.sc;
            auto c_opt = frt.v;

            int nex_layer = c_layer + 1;
            if (!(nex_layer < layers)) {
                continue;
            }

            for (int dir = 0; dir < 5; ++dir) {
                int nx = c_x + dx[dir];
                int ny = c_y + dy[dir];

                if (!(nx >= 0 && nx < r && ny >= 0 && ny < c)) {
                    continue;
                }

                // can go
                if (mazes[nex_layer][nx][ny] == '.') {
                    if (c_opt.d + 1 < f[nex_layer][nx][ny][c_sc].d) {
                        f[nex_layer][nx][ny][c_sc] = c_opt;
                        f[nex_layer][nx][ny][c_sc].d = c_opt.d + 1;
                        q.push(Status(nex_layer, nx, ny, c_sc, f[nex_layer][nx][ny][c_sc]));
                    }
                    continue;
                }
                

                // cannot go
                // 1. ONLY_TEMP
                if (c_sc == ONLY_TEMP) {
                    if (c_opt.d + 1 < f[nex_layer][nx][ny][TEMP_PERM].d) {
                        f[nex_layer][nx][ny][TEMP_PERM].d = c_opt.d + 1;
                        f[nex_layer][nx][ny][TEMP_PERM].px = nx;
                        f[nex_layer][nx][ny][TEMP_PERM].py = ny;
                        q.push(Status(nex_layer, nx, ny, TEMP_PERM, f[nex_layer][nx][ny][TEMP_PERM]));
                    }
                }
                

                // 2. ONLY_PERM
                if (c_sc == ONLY_PERM) {
                    if (c_opt.px == nx && c_opt.py == ny) {
                        if (c_opt.d + 1 < f[nex_layer][nx][ny][c_sc].d) {
                            f[nex_layer][nx][ny][c_sc] = c_opt;
                            f[nex_layer][nx][ny][c_sc].d = c_opt.d + 1;
                            q.push(Status(nex_layer, nx, ny, c_sc, f[nex_layer][nx][ny][c_sc]));
                        }
                    } else {
                        if (c_opt.d + 1 < f[nex_layer][nx][ny][TEMP_PERM].d) {
                            f[nex_layer][nx][ny][TEMP_PERM] = c_opt;
                            f[nex_layer][nx][ny][TEMP_PERM].d = c_opt.d + 1;
                            q.push(Status(nex_layer, nx, ny, TEMP_PERM, f[nex_layer][nx][ny][TEMP_PERM]));
                        }
                    }
                }

                // 3. NONE_USED
                if (c_sc == NONE_USED) {
                    if (c_opt.d + 1 < f[nex_layer][nx][ny][ONLY_PERM].d) {
                        f[nex_layer][nx][ny][ONLY_PERM].d = c_opt.d + 1;
                        f[nex_layer][nx][ny][ONLY_PERM].px = nx;
                        f[nex_layer][nx][ny][ONLY_PERM].py = ny;
                        q.push(Status(nex_layer, nx, ny, ONLY_PERM, f[nex_layer][nx][ny][ONLY_PERM]));
                    }

                    if (c_opt.d + 1 < f[nex_layer][nx][ny][ONLY_TEMP].d) {
                        f[nex_layer][nx][ny][ONLY_TEMP] = c_opt;
                        f[nex_layer][nx][ny][ONLY_TEMP].d = c_opt.d + 1;
                        q.push(Status(nex_layer, nx, ny, ONLY_TEMP, f[nex_layer][nx][ny][ONLY_TEMP]));
                    }
                }
            }

        }

        for (int i = 0; i < layers; ++i) {
            for (int sc = 0; sc < 4; ++sc) {
                if (f[i][r - 1][c - 1][sc].d != INT_MAX) {
                    return true;
                }
            }
        }

        return false;
    }
};

复杂度

  • 时间复杂度：\(O(t \times n \times m \times 4) = O(t \times n \times m)\)，其中 \(t\) 代表时刻总数。
  • 空间复杂度：\(O(t \times n \times m)\)。

类似的题目

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 1815. 得到新鲜甜甜圈的最多组数（第 49 场双周赛第 4 题）

方法一：模拟退火

前置知识

模拟退火例题和模板：计蒜客 A2141 - Country Meow

思路

在这里我们可以把 group 数组看作状态，每次随机选取两个位置进行交换看成增量。

代码

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
class Solution {
public:
    vector<int> groups;
    int batchSize, ans, n;

    int calculate() {
        int cur = 0, cur_ans = 0;
        for (int i = 0; i < n; ++i) {
            if (cur == 0) {
                cur_ans++;
            }

            cur += groups[i];
            cur %= batchSize;
        }

        ans = max(ans, cur_ans);

        return cur_ans;
    }

    void simulated_anneling() {
        random_shuffle(groups.begin(), groups.end());

        for (double t = 1e6; t > 1e-5; t *= 0.98) {
            int a = rand() % n, b = rand() % n;
            int pre = calculate();
            swap(groups[a], groups[b]);
            int aft = calculate();
            int delta = pre - aft;

            if (!(exp(-delta / t) > (double)rand() / RAND_MAX)) {
                swap(groups[a], groups[b]);
            }
        }
    }

    int maxHappyGroups(int batchSize_, vector<int>& groups_) {
        groups = groups_;
        batchSize = batchSize_;
        ans = 0;
        n = groups.size();

        srand(time(0));
        for (int i = 0; i < 30; ++i) {
            simulated_anneling();
        }

        return ans;
    }
};

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2018 南京现场赛 D 题 - Country Meow

思路

最小球覆盖问题，可以用模拟退火做。

昨天补 LC 第 49 场双周赛的时候看学会了模拟退火，于是翻出这道题。

模拟退火的框架是这样的：

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
int ans;

void score() {
    // ...
    // 计算分数

    // [!IMPORTANT] 在每次计算分数的时候更新最优解
    ans = max(ans, current_score);
}

void simulated_anneling() {
    // 随机取一个状态作为初始状态
    // 这个 Status 可能是 int，可能是坐标，etc.
    Status s = rand_status();

    // t 表示「温度」，应当介于 t_init 和 t_term 之间
    // rate 是一个接近 1 且小于 1 的数
    // rate 越接近 1，计算答案的过程就越平缓，但是相对也越慢
    double t_init = 1e6, t_term = 1e-5, rate = 0.98;
    for (double t = t_init; t > t_term; t *= rate) {
        // 随机一个增量
        // [!IMPORTANT] 这个增量是和 t 相关的
        // 例如 int d = t * ((double)rand() / RAND_MAX * 2 - 1)
        // 它意味着如果温度高，变化就快一些，温度低变化就慢一些
        // 这个有点类似于梯度下降
        Status d = rand_delta(t);

        // 计算增量前和增量后的分数
        int pre_score = score(s);
        int aft_score = score(s + d);

        // [!IMPORTANT]
        // 假设 aft_score > pre_score 表示增量后更优
        // 1. 如果 score_delta > 0，表示 s + d 更优，那么 s + d 直接被 s 接受
        //    即 s <- s + d
        // 2. 否则，让 s + d 以一定的概率被 s 接受
        int score_delta = aft_score - pre_score;
        if (exp(-score_delta / t) > (double)rand() / RAND_MAX) {
            s = s + d;
        }
    }
}

int main() {
    // ...
    // 输入数据

    // 单次模拟退火找到的很可能是局部最优解
    // 所以要多做几次
    int repeat_time = 50;
    for (int i = 0; i < repeat_time; ++i) {
        simulated_anneling();
    }

    // ...
    // 输出答案

    return 0;
}
  • WA 时候可以尝试增加 rate 或者 repeate_time，或者缩小 t 的范围
  • TLE 时可以尝试缩小 rate 或者 repeate_time，或者增大 t 的范围

在这一题中，我们把点的三维坐标作为状态，score 计算的就是当前点距离最远点的距离。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100 + 5;

int n;
double ans;

struct Coordinate {
    double x, y, z;
} c[MAX_N], mn, mx;

double dist(Coordinate a, Coordinate b) {
    return sqrt(
        (a.x - b.x) * (a.x - b.x) + 
        (a.y - b.y) * (a.y - b.y) + 
        (a.z - b.z) * (a.z - b.z));
}

double calculate(Coordinate r) {
    double far_dis = 0;
    for (int i = 0; i < n; ++i) {
        far_dis = max(far_dis, dist(r, c[i]));
    }

    ans = min(ans, far_dis);
    return far_dis;
}

void silumated_anneling() {
    Coordinate cur = { 
        rand() % (int(2e5) + 1) - 1e5,
        rand() % (int(2e5) + 1) - 1e5,
        rand() % (int(2e5) + 1) - 1e5,
    };

    for (double t = 1e6; t > 1e-6; t *= 0.99) {
        Coordinate nex = { 
            cur.x + t * ((double)rand() / RAND_MAX * 2 - 1),
            cur.y + t * ((double)rand() / RAND_MAX * 2 - 1),
            cur.z + t * ((double)rand() / RAND_MAX * 2 - 1),
        };
        
        double cur_dis = calculate(cur);
        double nex_dis = calculate(nex);
        double delta = nex_dis - cur_dis;
        if (exp(-delta / t) > (double)rand() / RAND_MAX) {
            cur = nex;
        }
    }
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%lf%lf%lf", &c[i].x, &c[i].y, &c[i].z);
    }

    srand(time(0));
    ans = INT_MAX;

    for (int i = 0; i < 100; ++i) {
        silumated_anneling();
    }

    printf("%.10f\n", ans);

    return 0;
}

发表于 更新于 分类于 阅读次数：

比赛链接：Kickstart 2021 Round A

K-Goodness String

统计 \(S_i \neq S_{N-i+1}\) 的个数记为 \(C\)，目标分数为 \(K\)，故至少要改 \(|C - K|\)。

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;

const int MAX_N = 200000 + 5;

int T, N, K;
char s[MAX_N];

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &N, &K);
        getchar();
        scanf("%s", s);

        int cnt = 0;
        for (int i = 0; i < N / 2; ++i) {
            if (s[i] != s[N - i - 1]) {
                ++cnt;
            }
        }

        printf("Case #%d: %d\n", cs, abs(cnt - K));
    }

    return 0;
}

L Shaped Plots

统计每个格子四个方向连续的 \(1\) 的个数。对于每个格子形成的 \(L\) 有四种情况：

  • \(L\) 的尖角朝右上
  • \(L\) 的尖角朝右下
  • \(L\) 的尖角朝左上
  • \(L\) 的尖角朝左下

对于每种情况，记长边为 \(l\)，短边为 \(s\)。

  • 如果在长边上构造 \(L\) 的长边，短边上构造 \(L\) 的短边，那么这个点的贡献是 \[ \max \{ \min \{ \lfloor \frac{l}{2} \rfloor , s \} - 1, 0 \} \]
  • 如果在短边上构造 \(L\) 的长边，长边上构造 \(L\) 的短边，那么这个点的贡献是 \[ \max \{ \lfloor \frac{s}{2} \rfloor, 0 \} \]
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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000 + 5;

int T, R, C;
int cell[MAX_N][MAX_N];
int LR[MAX_N][MAX_N], RL[MAX_N][MAX_N], UD[MAX_N][MAX_N], DU[MAX_N][MAX_N];

void calculate_lr() {
    for (int i = 0; i < R; ++i) {
        LR[i][0] = cell[i][0];
        for (int j = 1; j < C; ++j) {
            LR[i][j] = cell[i][j] ? LR[i][j - 1] + cell[i][j] : 0;
        }
    }
}

void calculate_rl() {
    for (int i = 0; i < R; ++i) {
        RL[i][C - 1] = cell[i][C - 1];
        for (int j = C - 2; j >= 0; --j) {
            RL[i][j] = cell[i][j] ? RL[i][j + 1] + cell[i][j] : 0;
        }
    }
}

void calculate_ud() {
    for (int j = 0; j < C; ++j) {
        UD[0][j] = cell[0][j];
        for (int i = 1; i < R; ++i) {
            UD[i][j] = cell[i][j] ? UD[i - 1][j] + cell[i][j] : 0;
        }
    }
}

void calculate_du() {
    for (int j = 0; j < C; ++j) {
        DU[R - 1][j] = cell[R - 1][j];
        for (int i = R - 2; i >= 0; --i) {
            DU[i][j] = cell[i][j] ? DU[i + 1][j] + cell[i][j] : 0;
        }
    }
}

long long grid_contribute(int x, int y) {
    long long contribute = 0;
    int l = max(x, y), s = min(x, y);

    contribute += max(min(l / 2, s) - 1, 0);
    contribute += max(s / 2 - 1, 0);

    return contribute;
}

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &R, &C);
        
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                scanf("%d", &cell[i][j]);
            }
        }

        calculate_lr();
        calculate_rl();
        calculate_du();
        calculate_ud();

        long long ans = 0;
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                ans += grid_contribute(LR[i][j], UD[i][j]);
                ans += grid_contribute(LR[i][j], DU[i][j]);
                ans += grid_contribute(RL[i][j], UD[i][j]);
                ans += grid_contribute(RL[i][j], DU[i][j]);
            }
        }

        printf("Case #%d: %lld\n", cs, ans);
    }

    return 0;
}

Rabbit House

用大根堆维护所有位置的高度，从最高的开始出堆，每个出堆的元素拓展周围的四个元素：

  • 如果已经满足高度差小于等于 \(1\)，则不管
  • 如果不满足的，则把新元素的高度改成老元素 \(-1\)，并把高度的改变量计入贡献

在这个过程中，元素的高度可能会发生改变，要判断从堆中取出的元素是否是有效元素，需要看这个元素的高度和实际高度是否相等。如果不想等，说明这个值是无效的，应该舍弃。

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300 + 5;

int T, R, C;
int grid[MAX_N][MAX_N];

struct Position {
    int x, y, g;

    friend bool operator < (const Position &u, const Position &v) {
        return u.g < v.g;
    }
};

priority_queue<Position> q;

int check_position(int x, int y, int v) {
    
    if (!(x >= 0 && x < R && y >= 0 && y < C)) {
        return 0;
    }
    // printf("(x = %d, y = %d, v = %d)\n", x, y, v);

    int contribution = 0;

    // v >= grid[x][y]
    if (v - grid[x][y] > 1) {
        contribution += (v - grid[x][y] - 1);
        grid[x][y] = v - 1;
        q.push({x, y, grid[x][y]});
    }

    return contribution;
}

int main() {
    scanf("%d", &T);
    
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &R, &C);

        while (!q.empty()) {
            q.pop();
        }

        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                scanf("%d", &grid[i][j]);
                q.push({i, j, grid[i][j]});
            }
        }

        long long ans = 0;

        while (!q.empty()) {
            auto f = q.top();
            q.pop();

            if (f.g != grid[f.x][f.y]) {
                continue;
            }

            ans += check_position(f.x - 1, f.y, f.g);
            ans += check_position(f.x + 1, f.y, f.g);
            ans += check_position(f.x, f.y + 1, f.g);
            ans += check_position(f.x, f.y - 1, f.g);
        }

        printf("Case #%d: %lld\n", cs, ans);
    }

    return 0;
}

Checksum

把行号和列号看作节点，如果 \(A(i, j) = -1\) 就在 \(i\) 和 \(j\) 之间建边，权为 \(B(i, j)\)。因此，如果某一个点只有一条边，说明该行 / 列只有一个元素未知，可以直接推断出来。如果某个点没有边，说明该行 / 列没有未知元素。我们知道「可推断」的前提条件是该行 / 列只有一个元素是未知的，我们可以先通过「推断」删除图中所有度为 \(1\) 的节点，接着又多了一批新的度为 \(1\) 的节点。因此如果一直这么删下去，可以把整张图删完，就说明所有的未知点都可以通过推断得到，但是有可能删不完——因为可能存在环。只有图是一棵树的时候，才能删完，即可以推断得到所有点。因此我们要把图中删去一些边，使得剩下的边变成一棵树，我们要让删除的边的权的总和最小。

记所有边的权值和为 \(t\)，图的最大生成树为 \(m\)，则删除边的最小权值和为 \(t - m\)。

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500 + 5;

int T, N, _;
int A[MAX_N][MAX_N], B[MAX_N][MAX_N];

struct Edge {
    int from, to, v;

    friend bool operator < (const Edge &u, const Edge &v) {
        return u.v > v.v;
    }
};

vector<Edge> edges;

struct DisjointSet {
    // r + c => MAX_N * 2
    int f[MAX_N * 2];

    void init(int n) {
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
    }

    int find(int u) {
        return f[u] == u ? u : f[u] = find(f[u]);
    }

    void merge(int u, int v) {
        f[find(u)] = find(v);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }
} d;

int main() {
    scanf("%d", &T);

    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d", &N);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                scanf("%d", &A[i][j]);
            }
        }

        for (int i= 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                scanf("%d", &B[i][j]);
            }
        }

        for (int i = 0; i < 2 * N; ++i) {
            scanf("%d", &_);
        }

        long long tot = 0;
        edges.clear();
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == -1) {
                    edges.push_back({i, j + N, B[i][j]});
                    tot += B[i][j];
                }
            }
        }

        // MAXIMUM spanning tree
        d.init(2 * N + 5);
        long long mst = 0;
        sort(edges.begin(), edges.end());
        for (const Edge &e: edges) {
            if (!d.same(e.from, e.to)) {
                mst += e.v;
                d.merge(e.from, e.to);
            }
        }

        printf("Case #%d: %lld\n", cs, tot - mst);
    }

    return 0;
}

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 面试题 17.19 - 消失的两个数字

这个题还蛮有意思的，题目限定了时间复杂度要\(O(n)\)，空间复杂度要\(O(1)\)，主要是空间限制。

对于 \(O(n)\) 的时间复杂度很容易想到哈希表，可是这需要额外的空间，即空间复杂度也是 \(O(n)\) 的。如何在不增加额外空间的前提下建立哈希表呢？我们知道所有的数都小 \(3\times 10^4\)，所以只需要在原数组上打标记就可以了，即读到一个实际值为 \(x\) 的数字，就在 \(x\) 的下标的那个数字上加上一个大于 \(3\times 10^4\) 的数字，或者把一个用不到的二进制位置 \(1\)。

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
class Solution {
public:
    static constexpr int flag = int(1e5);

    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int s = nums.size();
        for (int i = 1; i <= 3; ++i) {
            nums.push_back(0);
        }
        for (int i = 0; i < s; ++i) {
            if (nums[i] < flag) {
                nums[nums[i]] += flag;
            } else {
                nums[nums[i] - flag] += flag;
            }
        }
        vector <int> ret;
        for (int i = 1; i <= n; ++i) {
            if (nums[i] < flag) {
                ret.push_back(i);
            }
        }
        return ret;
    }
};

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 面试题12 - 矩阵中的路径

DFS匹配，注意找到答案就跳出，渐进时间复杂度 $ O(nm|s|^2) $。

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
class Solution {
public:
    int n, m;
    vector <vector <char>> a;
    vector <vector <bool>> vis;
    string s;
    bool status;

    static constexpr int dx[4] = {-1, 0, 1, 0};
    static constexpr int dy[4] = {0, 1, 0, -1};

    void dfs(int x, int y, int p) {
        if (status == true) return;
        if (p == s.size() - 1 && a[x][y] == s[p]) {
            status = true;
            return;
        }
        if (a[x][y] != s[p]) {
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= m - 1) || vis[nx][ny]) { 
                continue;
            }
            vis[nx][ny] = 1;
            dfs(nx, ny, p + 1);
            vis[nx][ny] = 0;
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board.at(0).size();
        a = board;
        s = word;
        vis.resize(n);
        for (auto &v: vis) v.resize(m);
        status = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                vis[i][j] = 1;
                dfs(i, j, 0);
                vis[i][j] = 0;
                if (status == true) {
                    return true;
                }
            }
        }
        return false;
    }
};