比赛链接

A题

给定两个整数$a$，$b$，寻找一个数$m$使得$m >= min(a, b) \wedge a \equiv b(\bmod m)$，易知隐含条件$m<=lcm(a, b)$，根据根据题目描述$a,b<=1000 \rightarrow lcm(a,b)<1e6$，枚举即可。

1
2
3
4
5
6
7
8
9
10
void solve() {
    int a, b;
    cin >> a >> b;
    for (int i = std::min(a, b); ; i++) {
        if (i % a == i % b) {
            cout << i << '\n';
            return;
        }
    }
}

B题

一个长度为$n$的位串，为了使其不出现连续$m$个0，可以选择一次修改连续$k$个数字变为1，求最小的修改次数。

贪心，遍历时遇到长度为$m$的0串修改即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    int ans = 0, p = 0, len = 0;
    while (p < n) {
        if (s[p] == '0') {
            len++;
            if (len == m) {
                ans++;
                len = 0;
                p += k;
                continue;
            }
        } else {
            len = 0;
        }
        p++;
    }
    cout << ans << '\n';
}

C题

找到所有可以逃脱的位置：先从四条边开始寻找指向外围的区域，标记并入队，之后从这些区域开始搜索，如果有指向它们的格子，则该格子也标记为可逃脱并入队。

搜索完成后，再遍历一遍迷宫，如果某一个格子四周都是可逃脱，那么该格子也标记为可逃脱，否则该格子一定不可逃脱。

这里主要是证明如果该格子四周有一个没有标记为可逃脱的格子时，该格子一定无法逃脱：

把未确定的格子看作若干个连通块（?可以直接放入，因为它可以当作任何方向，一定有办法纳入连通块中），可以确保的是这个连通块的四周一定不指向可逃脱区域（因为它是由未确定的格子组成的），那么它内部所有的点也无法到达可逃脱区域。

这个方法也可以很好的判断一些特殊情况，如：都是?的迷宫，或者只有单行或单列的迷宫。

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
void solve() {
    const int N = 1001;
    const string dir_obj = "DLUR";
    static char a[N][N];
    static bool vis[N][N];
    static const int dx[] = { -1, 0, 1, 0},
                            dy[] = {0, 1, 0, -1};

    memset(vis, false, sizeof vis);
    std::queue<PII> q;
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            if (i == 0 && a[i][j] == 'U' || i == n - 1 && a[i][j] == 'D') {
                vis[i][j] = true;
                q.push({i, j});
                cnt++;
            } else if (j == 0 && a[i][j] == 'L' || j == m - 1 && a[i][j] == 'R') {
                vis[i][j] = true;
                q.push({i, j});
                cnt++;
            }
        }
    }
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = u.fi + dx[i], y = u.se + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y]) continue;
            if (a[x][y] == dir_obj[i]) {
                vis[x][y] = true;
                q.push({x, y});
                cnt++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j]) {
                bool flag = true;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    if (!vis[x][y]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cnt++;
                    vis[i][j] = true;
                }
            }
        }
    }
    cout << m * n - cnt << '\n';
}

D题

数量差为1的两个柱子，将数量较多的一个，取下一片之后放到数量较少的柱子上，可简单看作两个柱子发生交换。

完成排列的条件是：$0_{maxindex}<1_{minindex} \wedge 1_{maxindex}<2_{minindex}$

我们使用一个大根堆记录0的下标，一个std::set记录1的下标，一个小根堆记录2的下标，循环判断若当前0的最大下标$>$1的最小下标，则交换它们两个数，表现为弹出0下标的最大值和1下标的最小值，再分别插入到1的下标集合和0的下标集合中，1和2的交换同理，当循环中发现满足终止条件时则退出循环。

关键在于如何确定最大k次操作对于该方法是足够的，样例过了我们可以先交一发试试，发现过了，太棒了，由于该题k值给的很模糊，并且一个很有暗示性的Minimizing the number of moves is not required，我们无法确切的确定该方法的可行性，但我们的贪心思想每次将一对发生交换的数字分别移动到它们目前可行位置的边界处（最大值和最小值），过掉该题是非常有可能的。

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
void solve() {
    int n;
    cin >> n;
    int cnt1 = 0, cnt2 = 0;
    std::priority_queue<int> q0;
    std::priority_queue<int, std::vector<int>, std::greater<>> q2;
    std::set<int> q1;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (num == 1) {
            cnt1++;
            q1.insert(i);
        } else if (num == 2) {
            cnt2++;
            q2.push(i);
        } else {
            q0.push(i);
        }
    }
    int cnt = 0;
    std::vector<PII> ans;
    while (true) {
        bool flag = true;
        if (!q0.empty() && !q1.empty() && q0.top() > *q1.begin()) {
            cnt++;
            flag = false;
            int d0 = q0.top();
            q0.pop();
            int d1 = *q1.begin();
            q1.erase(q1.begin());
            ans.push_back({d1 + 1, d0 + 1});
            q0.push(d1);
            q1.insert(d0);
        }
        if (!q1.empty() && !q2.empty() && q2.top() < *std::prev(q1.end())) {
            cnt++;
            flag = false;
            int d1 = *std::prev(q1.end());
            q1.erase(std::prev(q1.end()));
            int d2 = q2.top();
            q2.pop();
            ans.push_back({d2 + 1, d1 + 1});
            q1.insert(d2);
            q2.push(d1);
        }
        if (flag) {
            break;
        }
    }
    cout << cnt << '\n';
    for (int i = 0; i < cnt; i++) {
        cout << ans[i].fi << ' ' << ans[i].se << '\n';
    }
}