跳转至

P3341 [ZJOI2014] 消棋子 题解

模拟赛考了这道小模拟，挺有意思的，来写一发题解。（不过模拟赛写的太屎了

开两个 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
constexpr int N = 1e5 + 5;
int row, column, n, m, answer;
struct coordinate {
    pair<int, int> a, b, c, d;
    // 表示一种颜色中，两个棋子的位置：
    // (a.first, b.first) 和 (c.first, d.first)。
    // .second 存储颜色编号。
};
struct operation {
    pair<int, int> x;
    pair<char, char> d;
};
coordinate coor[N];
operation cont[N];
vector<operation> result;

void init() {
    read(row, column, n);
    for (int i = 1; i <= n; ++i) {
        auto &[a, b, c, d] = coor[i];
        read(a.first, b.first, c.first, d.first);
        a.second = b.second = c.second = d.second = i;
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        auto &[x, d] = cont[i];
        read(x.first, x.second, d.first, d.second);
    }
}

初始化函数。策略是用两个 set 维护行列。

后面会使用 lower_bound 和 upper_bound。为了方便，我们在 set 中顺便处理边界，将边界的颜色标记为 \(0\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
set<pair<int, int>> row_set[N], column_set[N];

void reset() {
    for (int i = 0; i <= row; ++i) {
        row_set[i].clear();
        row_set[i].insert({0, 0});
        row_set[i].insert({N, 0});
    }
    for (int i = 0; i <= column; ++i) {
        column_set[i].clear();
        column_set[i].insert({0, 0});
        column_set[i].insert({N, 0});
    }
    for (int i = 1; i <= n; ++i) {
        auto &[a, b, c, d] = coor[i];
        row_set[a.first].insert(b);
        row_set[c.first].insert(d);
        column_set[b.first].insert(a);
        column_set[d.first].insert(c);
    }
}

get 工具函数，获取坐标 \((x, y)\) 向方向 \(d\) 遇到的第一个棋子坐标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
pair<int, int> get(char d, int x, int y) {
    switch (d) {
    case 'U':
        return *--column_set[y].lower_bound({x, 0});
    case 'D':
        return *column_set[y].upper_bound({x, N});
    case 'L':
        return *--row_set[x].lower_bound({y, 0});
    case 'R':
        return *row_set[x].upper_bound({y, N});
    };
    return {-1, -1};
}

erase 工具函数，删除坐标 \((x, y)\) 向方向 \(d\) 遇到的第一个棋子坐标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void erase(char d, int x, int y) {
    auto r = get(d, x, y);
    if (d == 'U' || d == 'D') {
        column_set[y].erase(r);
        row_set[r.first].erase({y, r.second});
    } else {
        row_set[x].erase(r);
        column_set[r.first].erase({x, r.second});
    }
}

insert 工具函数，注意这个函数不是插入棋子的，而是插入 移除 \(p\) 颜色的棋子 这一操作的。

这里会用到一个队列，每当有棋子消掉我们就把他的颜色入队，后面统计答案要用到。

 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
// 所有方向组合（不考虑顺序）
vector<pair<char, char>> directions{{'U', 'D'}, {'L', 'R'}, {'U', 'L'}, {'U', 'R'}, {'D', 'L'}, {'D', 'R'}};
queue<int> q;
bool exi[N];

void insert(int p) {
    auto add = [&](int p, int x, int y) {
        if (row_set[x].lower_bound({y, 0})->first == y) return;

        pair<int, int> fx, fy;
        for (auto &[a, b] : directions) {
            fx = get(a, x, y);
            fy = get(b, x, y);
            if (fx.second && fx.second == fy.second && fy.second == p && !exi[p]) {
                exi[p] = true;
                q.push(p);
                erase(a, x, y);
                erase(b, x, y);
                result.push_back({{x, y}, {a, b}});
                return;
            }
        }
    };

    auto &[a, b, c, d] = coor[p];
    if (a.first == c.first) {
        add(p, a.first, (b.first + d.first) / 2);
        return;
    }
    if (b.first == d.first) {
        add(p, (a.first + c.first) / 2, b.first);
        return;
    }
    add(p, a.first, d.first);
    add(p, c.first, b.first);
}

询问 1

利用前面的工具函数直接模拟即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void solve_1() {
    pair<int, int> fx = {0, 0}, fy = {0, 0};
    for (int i = 1; i <= m; ++i) {
        auto &[x, d] = cont[i];
        if (row_set[x.first].lower_bound({x.second, 0})->first == x.second) continue;
        fx = get(d.first, x.first, x.second);
        fy = get(d.second, x.first, x.second);
        if (fx.second && fx.second == fy.second) {
            ++answer;
            erase(d.first, x.first, x.second);
            erase(d.second, x.first, x.second);
        }
    }
    // writeln(answer);
    // 洛谷上的输出格式略有不同
    write(answer, ' ');
}

询问 2

利用前面 insert 工具函数，直接删除每个颜色。

但是，这样操作可能会影响到行列中其他棋子。还记得之前的队列吗？现在派上用场了。

 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
vector<char> single_directions{'U', 'D', 'L', 'R'};

void solve_2() {
    auto chk = [&](int x, int y) {
        pair<int, int> f;
        for (auto &d : single_directions) {
            f = get(d, x, y);
            if (f.second)
                ins(f.second);
        }
    };
    result.clear();
    for (int i = 1; i <= n; ++i) { // 先删除每种颜色
        insert(i);
    }
    while (q.size()) { // 再通过队列检查被影响的棋子
        int i = q.front();
        q.pop();
        auto &[a, b, c, d] = coor[i];
        chk(a.first, b.first);
        chk(c.first, d.first);
    }
    writeln(result.size());
    // 洛谷上的输出格式略有不同
    // for (auto &[x, d] : result) {
    //     writeln(x.first, ' ', x.second, ' ', d.first, ' ', d.second);
    // }
}

完整代码

这里只展示了核心代码。

注意这题洛谷不需要输出方案，而在 Loj 上需要。

  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
152
153
154
namespace chess {
constexpr int N = 1e5 + 5;
int row, column, n, m, answer;
queue<int> q;
struct coordinate {
    pair<int, int> a, b, c, d;
} coor[N];
struct operation {
    pair<int, int> x;
    pair<char, char> d;
} cont[N];
vector<operation> result;
set<pair<int, int>> row_set[N], column_set[N];
bool exi[N]; 
// UD, LR, UL, UR, DL, DR
vector<pair<char, char>> directions{{'U', 'D'}, {'L', 'R'}, {'U', 'L'}, {'U', 'R'}, {'D', 'L'}, {'D', 'R'}};
vector<char> single_directions{'U', 'D', 'L', 'R'};

void init() {
    read(row, column, n);
    for (int i = 1; i <= n; ++i) {
        auto &[a, b, c, d] = coor[i];
        read(a.first, b.first, c.first, d.first);
        a.second = b.second = c.second = d.second = i;
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        auto &[x, d] = cont[i];
        read(x.first, x.second, d.first, d.second);
    }
}
void reset() {
    for (int i = 0; i <= row; ++i) {
        row_set[i].clear();
        row_set[i].insert({0, 0});
        row_set[i].insert({N, 0});
    }
    for (int i = 0; i <= column; ++i) {
        column_set[i].clear();
        column_set[i].insert({0, 0});
        column_set[i].insert({N, 0});
    }
    for (int i = 1; i <= n; ++i) {
        auto &[a, b, c, d] = coor[i];
        row_set[a.first].insert(b);
        row_set[c.first].insert(d);
        column_set[b.first].insert(a);
        column_set[d.first].insert(c);
    }
}
pair<int, int> get(char d, int x, int y) {
    switch (d) {
    case 'U':
        return *--column_set[y].lower_bound({x, 0});
    case 'D':
        return *column_set[y].upper_bound({x, N});
    case 'L':
        return *--row_set[x].lower_bound({y, 0});
    case 'R':
        return *row_set[x].upper_bound({y, N});
    };
    return {-1, -1};
}
void erase(char d, int x, int y) {
    auto r = get(d, x, y);
    if (d == 'U' || d == 'D') {
        column_set[y].erase(r);
        row_set[r.first].erase({y, r.second});
    } else {
        row_set[x].erase(r);
        column_set[r.first].erase({x, r.second});
    }
}
void insert(int p) {
    auto add = [&](int p, int x, int y) {
        if (row_set[x].lower_bound({y, 0})->first == y) return;

        pair<int, int> fx, fy;
        for (auto &[a, b] : directions) {
            fx = get(a, x, y);
            fy = get(b, x, y);
            if (fx.second && fx.second == fy.second && fy.second == p && !exi[p]) {
                exi[p] = true;
                q.push(p);
                erase(a, x, y);
                erase(b, x, y);
                result.push_back({{x, y}, {a, b}});
                return;
            }
        }
    };

    auto &[a, b, c, d] = coor[p];
    if (a.first == c.first) {
        add(p, a.first, (b.first + d.first) / 2);
        return;
    }
    if (b.first == d.first) {
        add(p, (a.first + c.first) / 2, b.first);
        return;
    }
    add(p, a.first, d.first);
    add(p, c.first, b.first);
}

void solve_1() {
    pair<int, int> fx = {0, 0}, fy = {0, 0};
    for (int i = 1; i <= m; ++i) {
        auto &[x, d] = cont[i];
        if (row_set[x.first].lower_bound({x.second, 0})->first == x.second) continue;
        fx = get(d.first, x.first, x.second);
        fy = get(d.second, x.first, x.second);
        if (fx.second && fx.second == fy.second) {
            ++answer;
            erase(d.first, x.first, x.second);
            erase(d.second, x.first, x.second);
        }
    }
    // writeln(answer);
    write(answer, ' ');
}
void solve_2() {
    auto chk = [&](int x, int y) {
        pair<int, int> f;
        for (auto &d : single_directions) {
            f = get(d, x, y);
            if (f.second)
                insert(f.second);
        }
    };
    result.clear();
    for (int i = 1; i <= n; ++i) {
        insert(i);
    }
    while (q.size()) {
        int i = q.front();
        q.pop();
        auto &[a, b, c, d] = coor[i];
        chk(a.first, b.first);
        chk(c.first, d.first);
    }
    writeln(result.size());
    // for (auto &[x, d] : result) {
    //     writeln(x.first, ' ', x.second, ' ', d.first, ' ', d.second);
    // }
}
void main() {
    init();
    reset();
    solve_1();
    reset();
    solve_2();
}
} // namespace chess

评论