小花生

study & life record.

第36次CCF_CSP认证

发表于 分类于 ，

VP，练习。

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

void solve(){
    int n, k; cin >> n >> k;
    while(k--){
        int x, y; cin >> x >> y;
        string s; cin >> s;
        for(auto &i : s){
            if(i == 'f'){
                y = min(n, y + 1);
            }
            else if(i == 'b'){
                y = max(1, y - 1);
            }
            else if(i == 'l'){
                x = max(1, x - 1);
            }
            else {
                x = min(n, x + 1);
            }
        }
        cout << x << ' ' << y << '\n';
    }

}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

2. 梦境巡查

为了顺利完成巡查，需要满足的条件有：

  • $w-a_0\ge 0$
  • $w+b_1-(a_0+a_1)\ge0$
  • $\cdots$
  • $w+\sum\limits_{i=1}^{n}b_i-\sum\limits_{i=0}^na_i\ge0$

即：对于任意的 $k\in[0,n]$ ，都有 $w\ge\sum\limits_{i=0}^ka_i-\sum\limits_{i=1}^{k}b_i$

$w$ 最小时，有 $w=\max\limits_{0\le k\le n}\left(\sum\limits_{i=0}^ka_i-\sum\limits_{i=1}^{k}b_i\right)$。

维护住 $c_k=\sum\limits_{i=0}^ka_i-\sum\limits_{i=1}^{k}b_i$，现在考虑让 $b_i$ 依次变为 $0$。

  • 不难发现。令 $b_i=0$ 时，$c_i, c_{i+1},\cdots,c_n$ 都会增大 $b_i$。
  • 此时的全局最大值，只需提前维护住 $c$ 数组中每个位置的前缀最大值和后缀最大值，计算 $\max(premax[i - 1]，sufmax[i] + b_i)$ 即可。
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
#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>a(n + 1);
    for(int i = 0; i <= n; i++) cin >> a[i];
    vector<int>b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];

    vector<int>c(n + 1);
    c[0] = a[0];
    for(int i = 1; i <= n; i++){
        c[i] = c[i - 1] + a[i] - b[i];
    }	

    vector<int>pre(n + 1), suf(n + 1);
    pre[0] = c[0];
    for(int i = 1; i <= n; i++){
        pre[i] = max(pre[i - 1], c[i]);
    }
    suf[n] = c[n];
    for(int i = n - 1; i >= 0; i--){
        suf[i] = max(suf[i + 1], c[i]);
    }

    for(int i = 1; i <= n; i++){
        cout << max(pre[i - 1], suf[i] + b[i]) << ' ';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

3. 缓存模拟

大模拟，按题意自行梳理流程。

唯一关键的是数据结构的选择。我们需要维护每一个组，满足：

  1. 组中的数据按照使用的时间先后排序。
  2. 对于每一个数据，我们需要能快速判断，组中是否存在该数据。（即判断是否命中）
  3. 需要能快速找到数据在组中的位置，并将其提到队首。（更新最后使用时间）
  4. 需要能快速弹出队末的元素（替换）。

那么用 set 维护每一个组，并重载比较方式即可。

详细流程可以见代码，非常清晰。

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

// 记录编号为 idx 的点被读写的最后时间
unordered_map<int, int>t;
// 记录编号为 idx 的点是否被修改
unordered_map<int, bool>cg;

struct cmpbytime {
    bool operator()(const int &a, const int &b) const {
        return t[a] < t[b];
    }
};

void solve(){
    int n, N, q; cin >> n >> N >> q;

    // 按 被读写的最后时间 排序
    vector<set<int, cmpbytime>>Q(N);

    for(int k = 1; k <= q; k++){
        int o, a; cin >> o >> a;
        int p = (a / n) % N; // 组数

        // 在第 p 组内找数据 a
        auto u = Q[p].find(a);

        // 找到了
        if(u != Q[p].end()){
            // 更新时间, 调整 set
            int v = *u;
            Q[p].erase(u);
            t[v] = k;
            Q[p].emplace(v);

            // 如果是写入, 带上修改标记
            if(o == 1) cg[v] = 1;
        }
        // 没找到
        else{
            // 如果 p 组满了, 先弹出最早使用的一个
            if(Q[p].size() == n){
                int v = *Q[p].begin();
                // 如果被修改过, 写内存
                if(cg[v]) {
                    cout << "1 " << v << '\n';
                    cg[v] = 0;
                }
                Q[p].erase(v);
            }

            // 再加入新数据
            cout << "0 " << a << '\n'; // 读内存
            t[a] = k;
            Q[p].emplace(a);

            // 如果是写入, 带上修改标记
            if(o == 1) cg[a] = 1;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

4. 跳房子

这题似乎解法非常丰富，这里考虑了一些从最短路方向思考的解法。

为描述方便，我们称一次跳跃的目标位置为 “一次落地点”，接着后退 a[i] 格，落点称为 “二次落地点”。

首先考虑一个显然的 $O(n^2)$ 的解法：将每一个点与所有 “二次落地点” 建边。那么 $n$ 个点，最多 $n(n-1)$ 条（单向）边，直接 BFS 求最短路即可。

不难发现，这个解法的瓶颈在于边数是 $O(n^2)$ 的，如果我们能减少连边，就能解决这个问题了。

优化思路一：set 维护 “一次落地点”

不难发现，BFS 过程中，已经成为 “一次落地点” 的点是没有再次成为 “一次落地点” 的必要的，我们用一个 set 维护所有还没有成为 “一次落地点” 的点。我们每次跳跃只从 set 中选取 “一次落地点” 来跳；每当一个点成为了 “一次落地点”，我们就将其从 set 中删去。这样，我们连边就不会超过 $n$ 条。

时间复杂度 $O(n\log n)$，瓶颈在 set 的删点。（感觉是最清爽也最高效的优化思路了）

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;

constexpr int inf = 1e9;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int>a(n + 1), k(n + 1);
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++) k[i] = read();

    set<int>st;
    for(int i = 2; i <= n; i++) st.emplace(i);

    queue<int>Q;
    vector<int>dist(n + 1, inf);
    Q.emplace(1);
    dist[1] = 0;
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();

        vector<int>del;
        for(auto it = st.lower_bound(u + 1); it != st.end() && *it <= min(n, u + k[u]); it++){
            del.emplace_back(*it);
            int v = *it - a[*it];
            if(dist[v] == inf) {
                dist[v] = dist[u] + 1;
                Q.emplace(v);
            }
        }

        for(auto &i : del) st.erase(i);
    }
    if(dist[n] == inf){
        cout << -1 << '\n';
    }
    else{		
        cout << dist[n] << '\n';
    }
}

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    solve();
    return 0;
}

优化思路二：分块优化建边

注意这一份并不能通过所有测试数据。

可以利用分块优化连边，将边数降到 $O(n\sqrt n)$ 级别。

具体做法为，为每个 $\sqrt n$ 的分块新建一个父节点，当某个点需要连的边包含完整分块时，直接连接这些分块的父节点（边权为0）。

最后，执行 01BFS 即可。总时间复杂度 $O(n\sqrt n)$ ，讲题嘉宾说该思路能过，但这份 TLE 了（懂的教教）。

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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

constexpr int inf = 1e9;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int>a(n), k(n);
    for(int i = 0; i < n; i++) a[i] = read();
    for(int i = 0; i < n; i++) k[i] = read();

    int bs = sqrt(n);
    int bn = (n + bs - 1) / bs;

    vector<vector<PII>>adj(n + bn);

    for(int i = 0; i < bn; i++){
        for(int j = i * bs; j < min(n, (i + 1) * bs); j++){
            adj[n + i].emplace_back(1, j);
        }
    }

    for(int i = 0; i < n; i++){
        int bl = (i + 1) / bs, br = min(n - 1, i + k[i]) / bs;
        
        if(bl == br){
            for(int j = i + 1; j <= min(n - 1, i + k[i]); j++){
                adj[i].emplace_back(1, j);
            }
        }
        else{
            for(int j = bl + 1; j < br; j++){
                adj[i].emplace_back(0, n + j);
            }
            for(int j = i + 1; j / bs == bl; j++){
                adj[i].emplace_back(1, j);
            }			
            for(int j = min(n - 1, i + k[i]); j / bs == br; j--){
                adj[i].emplace_back(1, j);
            }
        }
    }

    deque<int>Q;
    vector<int>dist(n + bn, inf);
    Q.emplace_back(0);
    dist[0] = 0;
    while(!Q.empty()){

        int u = Q.front();
        Q.pop_front();

        for(auto &[w, j] : adj[u]){
            int v = w ? j - a[j] : j;
            if(dist[v] == inf){
                dist[v] = dist[u] + w;
                if(w == 1){
                    Q.emplace_back(v);
                }
                else{
                    Q.emplace_front(v);
                }

                if(v == n - 1){
                    cout << dist[v];
                    return;
                }

            }
        }
    }
    cout << -1;
}

signed main(){
    solve();
    return 0;
}

优化思路三：线段树优化建边

边数优化到 $O(n\log n)$，总复杂度 $O(n\log 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
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
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

constexpr int inf = 1e9;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct SegNode {
    int l, r;
    int left, right;
};

vector<SegNode> seg_tree;
int n;

// 构建线段树，返回当前节点编号
int build(int l, int r, vector<vector<PII>>& adj) {
    if (l > r) return -1;
    int id = n++;
    seg_tree.push_back({l, r, -1, -1});
    if (l == r) {
        // 叶子节点连接到实际节点l，边权1
        adj[id].emplace_back(1, l);
        return id;
    }
    int mid = (l + r) >> 1;
    int left = build(l, mid, adj);
    int right_child = build(mid+1, r, adj);
    seg_tree[id - n].left = left;
    seg_tree[id - n].right = right_child;
    // 添加边权0到左右子节点
    if (left != -1)
        adj[id].emplace_back(0, left);
    if (right_child != -1)
        adj[id].emplace_back(0, right_child);
    return id;
}

// 查询覆盖区间[l, r]的所有线段树节点
void query(int u, int l, int r, vector<int>& res) {
    const SegNode& node = seg_tree[u - n];
    if (node.r < l || node.l > r) return;
    if (l <= node.l && node.r <= r) {
        res.push_back(u);
        return;
    }
    if (node.left != -1) query(node.left, l, r, res);
    if (node.right != -1) query(node.right, l, r, res);
}

void solve() {
    int n = read();
    vector<int> a(n), k(n);
    for (int i = 0; i < n; ++i) a[i] = read();
    for (int i = 0; i < n; ++i) k[i] = read();

    // 初始化线段树
    seg_tree.clear();
    int max_seg_size = 4 * n;
    vector<vector<PII>> adj(n + max_seg_size);
    int root = build(0, n - 1, adj);

    // 建立每个点i的边
    for (int i = 0; i < n; ++i) {
        int L = i + 1;
        int R = i + k[i];
        if (L >= n) continue;
        R = min(R, n-1);
        if (L > R) continue;
        vector<int> nodes;
        query(root, L, R, nodes);
        for (int u : nodes) {
            adj[i].emplace_back(0, u);
        }
    }

    // 0-1 BFS
    vector<int> dist(n + max_seg_size, inf);
    deque<int> q;
    dist[0] = 0;
    q.push_back(0);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        if (u == n-1) {
            cout << dist[u] << endl;
            return;
        }
        for (auto& [w, v] : adj[u]) {
            int target = (w == 1) ? (v - a[v]) : v;
            if (dist[target] > dist[u] + w) {
                dist[target] = dist[u] + w;
                if (w == 0) {
                    q.push_front(target);
                } else {
                    q.push_back(target);
                }
            }
        }
    }

    cout << -1 << endl;
}

signed main() {
    solve();
    return 0;
}