XCPC 寒假集训班 D2 个人笔记

Coast23
  2025-01-15 20:30:19 2025-01-15 20:30:19 创建   2025-03-31 17:38:37 2025-03-31 17:38:37 更新    5.2k 字  26 分钟  

讲评题

魔法阵

传送门

首先, 可以直接枚举,,,, 然后判断是否满足题目所给条件. 时间复杂度.

注意到题目的条件, 利用这个条件我们可以少枚举一维:

置

则

枚举, 然后和中只要枚举一个就能确定对方,和同理, 这样我们就只需要枚举三个变量, 时间复杂度降低为.

再来看这个奇怪的约束条件:

把代入:

把,换成,, 可以估出的范围:

即:

回到上面这个式子:

哎, 这是个大于号, 不是等于号? 看着很烦?

那就把它变成:

或者:

这些关系用数轴表示更直观:

数轴

看起来, 似乎仍然要枚举,, 四个变量中的一个, 总共3个变量, 才能确定所有数?

并非如此!

注意到这样一个性质:

较小的所确定出的, 在增大的时候也能使成立.

也就是说, 随着的增加, 符合要求的的集合是只增不减的.

这个性质非常重要, 这意味着我们只需要枚举和, 并在枚举的时候累计合法的的数量, 就能够统计和的答案数了.

时间复杂度. 常数比较小, 可以通过此题.

/*
cnt[x]: x的出现次数
ans[x][p] (p = 1,2,3,4): x数作为a,b,c,d的答案数.
*/
for(int k = 1; k * 9 < n; ++k){ // 枚举k. 
    int sum = 0; // 统计合法的a的数量
    for(int d = 9 * k + 2; d <= n; ++d){ // 枚举d
        int a = d - 9 * k - 1, b = a + 2 * k, c = d - k; // 计算a, b, c
        /*
        解释一下为什么a = 9 * k - 1, 因为d+1后, 只有d - 9 * k - 1进入新的解集. 或者说, 一开始我们就令t = 1了.
        */
        sum += cnt[a] * cnt[b]; // 计算合法的X_a 和 X_b数对
        ans[c][3] += sum * cnt[d]; // sum乘上d的个数就是c作为X_c的答案数
        ans[d][4] += sum * cnt[c]; // sum乘上c的个数就是d作为X_d的答案数
    }
}

同理, 较小的所确定出的, 在减小的时候也能使成立.

通过枚举和. 来确定和的答案数. 注意这里是逆序枚举了.

for(int k = 1; k * 9 < n; ++k){
    int sum = 0;
    for(int a = n - 9 * k - 1; a; --a){
        int b = a + 2 * k, d = 9 * k + 1, c = d - k;
        sum += cnt[c] * cnt[d];
        ans[a][1] += sum * cnt[b];
        ans[b][2] += sum * cnt[a];
    }
}

完整代码:

#include <cstdio>
#include <ctype.h>
#define N 50005

int n, m;
int x[N], cnt[N];
int ans[N][5];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) x[i] = read(), ++cnt[x[i]];
    for(int k = 1; k * 9 < n; ++k){
        int sum = 0;
        for(int d = 9 * k + 2; d <= n; ++d){
            int a = d - 9 * k - 1, b = a + 2 * k, c = d - k;
        
            sum += cnt[a] * cnt[b];

            ans[c][3] += sum * cnt[d];
            ans[d][4] += sum * cnt[c]; 
        }
        sum = 0;
        for(int a = n - 9 * k - 1; a; --a){
            int b = a + 2 * k, d = a + 9 * k + 1, c = d - k;
        
            sum += cnt[c] * cnt[d];

            ans[a][1] += sum * cnt[b];
            ans[b][2] += sum * cnt[a];
        }
    }
    for(int i = 1; i <= m; ++i){
        printf("%d %d %d %d\n", ans[x[i]][1], ans[x[i]][2], ans[x[i]][3], ans[x[i]][4]);
    }
    return 0^(0-0)^0;
}

海港

传送门

对于第i艘船, 向前查找所有的船, 找到所有满足的船并统计, 只能做到.

注意到是递增的, 而我们只想要一段长为的到达时间信息, 利用尺取法的思想, 用队列维护一个长为的窗口, 每当有新船只到港时, 做出如下操作:

  • 把和新船只到达时间超过1天的船移除. (队首的船到港最早, 不断取队首判断就行了) 并删掉其国籍信息.
  • 把新船加入队列, 更新国籍信息.
  • 输出当前国籍数量.

问题在于如何维护国籍信息.

首先, 容易想到使用二维数组G[i][j]记录第i艘船第j个人的船籍, 但这需要开G[N][K]这么大的数组, 不可能.

注意到, 我的想法就是直接用一个一维数组x[i]表示全部的第i个人的船籍, 再用一个一维数组idx[i]表示第i艘船的第一个人在x中的位置, 这样, 第i艘船的所有人的船籍就是x[idx[i] ~ idx[i] + k[i] - 1].

然后, 用bucket[i]表示船籍为i的船员数量, cnt表示当前窗口内的国籍数.

当新船加入时, 遍历船上的国籍k, 并将bucket[k] +. 如果加之前bucket[k]为, 说明是新国籍, 令cnt +.

当旧船退出时, 利用idx[i]和x[i]来遍历该艘船上的国籍k, 并将bucket[k] -. 如果减之后bucket[k]为, 说明已无该国人, 令cnt -.

时间复杂度.

具体实现见代码:

#include <queue>
#include <cstdio>
#include <ctype.h>
#define N 300005

int n;
int t[N], k[N];
int idx[N], x[N];
int bucket[N];

std::queue<int> q;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

int main(){
    n = read();
    int pr = 1, cnt = 0;
    for(int i = 1; i <= n; ++i){
        // 读入
        q.push(i); // 入队
        t[i] = read(); // 时间
        k[i] = read(); // 人数
        for(int j = pr; j < pr + k[i]; ++j) x[j] = read(); // 国籍

        // 出队
        while(t[i] - t[q.front()] >= 86400){
            int prr = idx[q.front()];
            for(int j = prr; j < prr + k[q.front()]; ++j){
                --bucket[x[j]];
                if(!bucket[x[j]]) --cnt;
            }
            q.pop();
        }

        // 维护桶
        for(int j = pr; j < pr + k[i]; ++j){
            if(!bucket[x[j]]) ++cnt;
            ++bucket[x[j]];
        }
        // 更新下标
        idx[i] = pr, pr += k[i];
        // 输出数量
        printf("%d\n", cnt);
    }
    return 0;
}

深さ優先探索

传送门

本来不写这道题的, 结果发现这题我有个❌, 有个三年半前Waiting的评测记录.

强迫症, 忍不了, 就把DFS和BFS都写了一遍. 只挂代码, 懒得注释了.

#include <queue>
#include <cstdio>

int n, m, sx, sy, ex, ey;
char map[505][505];
bool vis[505][505];

int move1[4] = {0, 0, 1, -1};
int move2[4] = {1, -1, 0, 0};

bool valid(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m && map[x][y] != '#';
}

void dfs(int x, int y){
    vis[x][y] = 1;
    for(int i = 0; i < 4; ++i){
        int xx = x + move1[i], yy = y + move2[i];
        if(valid(xx, yy) && !vis[xx][yy]) dfs(xx, yy);
    }
}

void bfs(int sx, int sy){
    std::queue<std::pair<int, int> > q;
    q.push({sx, sy});
    while(q.size()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; ++i){
            int xx = x + move1[i], yy = y + move2[i];
            if(valid(xx, yy) && !vis[xx][yy]){
                vis[xx][yy] = 1;
                q.push({xx, yy});
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    char ch = '\n';
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            while(ch == '\n') ch = getchar();
            map[i][j] = ch; ch = getchar();
            if(map[i][j] == 's') sx = i, sy = j;
            if(map[i][j] == 'g') ex = i, ey = j;
        }
    }
//    dfs(sx, sy);
    bfs(sx, sy);
    puts(vis[ex][ey]? "Yes" : "No");
    return 0^(0-0)^0;
}

八皇后 Checker Challenge

传送门

DFS典题, 提供一份AC Code.

#include <bits/stdc++.h>
#define N 25

int n, cnt;
int ans[N];
bool col[N], diag1[N], diag2[N];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

void print(){
    for(int i = 1;i <= n; ++i) printf("%d ", ans[i]);
    putchar('\n'); return;
}

bool check(int r, int c){
    return col[c] or diag1[c + r - 1] or diag2[n - (c - r + 1)];
}

void dfs(int order){ // 第order行, 要放在哪一排
    if(order > n){
        if(cnt < 3) print();
        ++cnt;
        return;
    }
    for(int i = 1; i <= n; ++i){
        if(check(order, i)) continue;
        col[i] = diag1[i + order - 1] = diag2[n - (i - order + 1)] = true;
        ans[order] = i;
        dfs(order + 1);
        col[i] = diag1[i + order - 1] = diag2[n - (i - order + 1)] = false;
    }
}

signed main(){
    n = read();
    dfs(1);
    printf("%d\n", cnt);
}

Labyrinth [CF1063B]

洛谷传送门

CF传送门

一开始我是这么想的:

将每个点的坐标、剩余向左和向右的移动次数设为状态, 然后直接BFS:

WA on test 40:

// https://codeforces.com/contest/1063/problem/B
// WA on test 40

#include <queue>
#include <cstdio>

int n, m, r, c, X, Y;

int ans;
char map[2005][2005];
bool vis[2005][2005];

struct Status{
    int x, y, l, r;
};

bool valid(int x, int y, int l, int r){
    return x >= 0 && x < n && y >= 0 && y < m && l >= 0 && r >= 0 && map[x][y] != '*';
}

void bfs(int x, int y){
    std::queue<Status> q;
    q.push({x, y, X, Y});
    ++ans, vis[x][y] = 1;
    while(q.size()){
        Status cur = q.front(); q.pop();
        // 左
        if(valid(cur.x, cur.y - 1, cur.l - 1, cur.r) && !vis[cur.x][cur.y - 1]){
            ++ans, vis[cur.x][cur.y - 1] = 1;
            q.push({cur.x, cur.y - 1, cur.l - 1, cur.r});
        }
        // 右
        if(valid(cur.x, cur.y + 1, cur.l, cur.r - 1) && !vis[cur.x][cur.y + 1]){
            ++ans, vis[cur.x][cur.y + 1] = 1;
            q.push({cur.x, cur.y + 1, cur.l, cur.r - 1});
        }
        // 上
        if(valid(cur.x - 1, cur.y, cur.l, cur.r) && !vis[cur.x - 1][cur.y]){
            ++ans, vis[cur.x - 1][cur.y] = 1;
            q.push({cur.x - 1, cur.y, cur.l, cur.r});
        }
        // 下
        if(valid(cur.x + 1, cur.y, cur.l, cur.r) && !vis[cur.x + 1][cur.y]){
            ++ans, vis[cur.x + 1][cur.y] = 1;
            q.push({cur.x + 1, cur.y, cur.l, cur.r});
        }
    }
}

int main(){
    scanf("%d%d%d%d%d%d", &n, &m, &r, &c, &X, &Y);
    char ch = '\n';
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            while(ch == '\n') ch = getchar();
            map[i][j] = ch; ch = getchar();
        }
    }
    bfs(r - 1, c - 1); // 记得-1, 因为我这里的map是从(0,0)开始.
    printf("%d\n", ans);
    return 0;
}

于是, 我开始思考为什么这样会WA.

很快我就发现, 仅根据一个点是否被访问过来去除更晚才到达该点的状态是不合理的, 因为有些状态虽然更晚到达该点, 但由于路径的不同, 它可能有更多的剩余向左/向右走的次数, 能走的更远!

那怎么办呢?

我的做法是这样: 想办法让被先访问过的点是更优的, 即剩余向左/向右走的次数更多.
也就是说, 我们每次都优先拓展 向上/向下 移动的状态, 而最后再拓展 向左/向右 移动的状态, 这样就能保证先被访问的点有着最多的剩余左右移动次数.

实现也很简单, 把队列改成双端队列, 每次拓展的时候, 把向上/向下 移动的状态放到队首, 而向左/向右 移动的状态放到队尾, 取队首来拓展即可.

// https://codeforces.com/contest/1063/problem/B
// Accepted

#include <queue>
#include <cstdio>

int n, m, r, c, X, Y;

int ans;
char map[2005][2005];
bool vis[2005][2005];

struct Status{
    int x, y, l, r;
};

bool valid(int x, int y, int l, int r){
    return x >= 0 && x < n && y >= 0 && y < m && l >= 0 && r >= 0 && map[x][y] != '*';
}

void bfs(int x, int y){
    std::deque<Status> q;
    q.push_front({x, y, X, Y});
    ++ans, vis[x][y] = 1;
    while(q.size()){
        Status cur = q.front(); q.pop_front();
        // 左
        if(valid(cur.x, cur.y - 1, cur.l - 1, cur.r) && !vis[cur.x][cur.y - 1]){
            ++ans, vis[cur.x][cur.y - 1] = 1;
            q.push_back({cur.x, cur.y - 1, cur.l - 1, cur.r});
        }
        // 右
        if(valid(cur.x, cur.y + 1, cur.l, cur.r - 1) && !vis[cur.x][cur.y + 1]){
            ++ans, vis[cur.x][cur.y + 1] = 1;
            q.push_back({cur.x, cur.y + 1, cur.l, cur.r - 1});
        }
        // 上
        if(valid(cur.x - 1, cur.y, cur.l, cur.r) && !vis[cur.x - 1][cur.y]){
            ++ans, vis[cur.x - 1][cur.y] = 1;
            q.push_front({cur.x - 1, cur.y, cur.l, cur.r});
        }
        // 下
        if(valid(cur.x + 1, cur.y, cur.l, cur.r) && !vis[cur.x + 1][cur.y]){
            ++ans, vis[cur.x + 1][cur.y] = 1;
            q.push_front({cur.x + 1, cur.y, cur.l, cur.r});
        }
    }
}

int main(){
    scanf("%d%d%d%d%d%d", &n, &m, &r, &c, &X, &Y);
    char ch = '\n';
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            while(ch == '\n') ch = getchar();
            map[i][j] = ch; ch = getchar();
        }
    }
    bfs(r - 1, c - 1); // 记得-1, 因为我这里的map是从(0,0)开始.
    printf("%d\n", ans);
    return 0;
}

[蓝桥杯 2023 省 A] 买瓜

传送门

看了这题, 第一想法就是爆搜, 并尝试写了一下代码.

为了避免除法, 我的做法是, 把乘以, 用 a[i] 表示半个瓜重, a[i] << 1表示整个瓜重, 相当于全都乘以来与除法相抵消.

当然也可以讨论的奇偶性, 但那样写起来非常繁琐.

然后把能想到的剪枝都写上:

  • 当前劈瓜数 > 答案, 剪!
  • 把瓜按重量从小到大排序, 如果劈当前瓜, 总重就比大了, 那选后面的瓜肯定也比大, 剪！
  • 预处理瓜重后缀和. sub[i] 表示第到个瓜的重量和. 显然, 如果把及其后面所有瓜都选上, 总重仍小于, 就没必要再搜了, 剪!

时间复杂度, 喜提pts.

32分代码:

#include <cstdio>
#include <ctype.h>
#include <algorithm>

int n, m, ans = 114514191;
int a[35];
long long sub[35];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(;  isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int min(int a, int b){return a < b? a : b;}

void dfs(int i, long long sum, int cnt){
    /* Args:
        i: 当前要决策的瓜的下标
        sum: 已经选取的瓜的总重
        cnt: 劈过的瓜的数量
    */
//    printf("%d %lld %d %d\n", i, sum, cnt, flag);
    // 注意, 可能 i<n 但 sum 已经等于 m ! 我在这里WA了好几次
    if(i > n || sum == m){
        if(sum == m) ans = min(ans, cnt);
        return;
    }
    if(cnt >= ans) return;
    if(sum + a[i] > m) return;
    if(sum + sub[i] < m) return;
    if(sum + (a[i] << 1) <= m) dfs(i+1, sum + (a[i] << 1), cnt);
    dfs(i+1, sum + a[i], cnt+1);
    dfs(i+1, sum, cnt); // 不选
}

signed main(){
    n = read(); m = read() << 1;
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::stable_sort(&a[1], &a[n+1]);
    for(int i = n; i >= 1; --i) sub[i] = sub[i+1] + (a[i] << 1); // 后缀和
    if(sub[1] < m){puts("-1"); return 0;}
    dfs(1, 0, 0);
    printf("%d\n", ans != 114514191? ans : -1);
    return 0;
}

但我不死心, 想再挣扎一下, 找找玄学优化方法.

很快就想到了, 原来是按瓜重从小到大选, 总重逼近的速度非常慢. 如果按瓜重从大到小选,逼近的速度就会快很多.

稍作修改, 再次提交, 没想到这代码跑的飞快,就过了, 吊打标答折半搜索…

果然暴力出奇迹.

AC Code:

#include <cstdio>
#include <ctype.h>
#include <algorithm>

int n, m, ans = 114514191;
int a[35];
long long sub[35];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(;  isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

bool cmp(int a, int b){return a > b;}

int min(int a, int b){return a < b? a : b;}

void dfs(int i, long long sum, int cnt){
    /* Args:
        i: 当前要决策的瓜的下标
        sum: 已经选取的瓜的总重
        cnt: 劈过的瓜的数量
    */
//    printf("%d %lld %d %d\n", i, sum, cnt, flag);
    // 注意, 可能 i<n 但 sum 已经等于 m ! 我在这里WA了好几次
    if(i > n || sum == m){
        if(sum == m) ans = min(ans, cnt);
        return;
    }
    if(cnt >= ans) return;
    if(sum + sub[i] < m) return;

    if(sum + (a[i] << 1) <= m) dfs(i+1, sum + (a[i] << 1), cnt);
    if(sum + a[i] <= m) dfs(i+1, sum + a[i], cnt+1);
    dfs(i+1, sum, cnt); // 不选
}

signed main(){
    n = read(); m = read() << 1;
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::stable_sort(&a[1], &a[n+1], cmp); // 优先选重量大的, 更快逼近答案
    for(int i = n; i >= 1; --i) sub[i] = sub[i+1] + (a[i] << 1); // 后缀和
    if(sub[1] < m){puts("-1"); return 0;}
    dfs(1, 0, 0);
    printf("%d\n", ans != 114514191? ans : -1);
    return 0;
}

训练题

D - Anji’s Binary Tree

洛谷传送门

CF传送门

我用DFS做的.

dfs(int u, int step): u表示当前结点, step表示修改次数.

  • 如果u没有左右儿子, 结束递归, 用step更新答案.
  • 如果u有左儿子, 就dfs(Lson[u], step + (s[u] != 'L'))
  • 如果u有右儿子, 就dfs(Rson[u], step + (s[u] != 'R'))

这要把整颗树都搜一遍, 跑起来应该比BFS慢. 但反正时间复杂度都是, 能轻松通过本题就行.

AC Code:

#include <cstdio>
#include <ctype.h>

#define N 300005

int T, n, ans;

char s[N];
int Lson[N];
int Rson[N];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

int min(int a, int b){return a < b? a : b;}

void dfs(int u, int step){
    if(Lson[u] == 0 && Rson[u] == 0){
        ans = min(ans, step);
        return;
    }
    if(Lson[u]){
        if(s[u] == 'L') dfs(Lson[u], step);
        else dfs(Lson[u], step + 1);
    }
    if(Rson[u]){
        if(s[u] == 'R') dfs(Rson[u], step);
        else dfs(Rson[u], step + 1);
    }
}

void solve(){
    n = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ++i) Lson[i] = read(), Rson[i] = read();
    ans = 114514191;
    dfs(1, 0);
    printf("%d\n", ans);
}

int main(){
    T = read();
    while(T--) solve();
    return 0^(0-0)^0;
}

E - Grid and Magnet

洛谷传送门

一开始以为是遍历整张图, 求最大连通块的大小, 写上去喜提WA 36.0 / 52.0.

这是WA了的代码:

#include <cstdio>
#include <ctype.h>

#define N 1005

int n, m, ans = 1, cnt;
char map[N][N];
bool vis[N][N];

int move1[4] = {0, 0, 1, -1};
int move2[4] = {1, -1, 0, 0};

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

inline int max(int a, int b){return a > b? a : b;}

bool valid(int x, int y){
    // 判断(x, y)是否在地图内且上下左右没有磁铁.
    return x > 0 && x <= n && y > 0 && y <= m &&
           map[x-1][y] != '#' && map[x+1][y] != '#' &&
           map[x][y-1] != '#' && map[x][y+1] != '#';
}

void dfs(int x, int y){
    ++cnt;
//    printf("(%d, %d)\n", x, y);
    for(int i = 0; i < 4; ++i){
        int xx = x + move1[i], yy = y + move2[i];
        if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
        if(valid(x, y) && !vis[xx][yy]){
            vis[xx][yy] = 1;
            dfs(xx, yy);
        }
    }
}

int main(){
    n = read(), m = read(); char ch = '\n';
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            while(ch == '\n') ch = getchar();
            map[i][j] = ch; ch = getchar();
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!vis[i][j] && map[i][j] == '.' && valid(i, j)){
                cnt = 0, vis[i][j] = 1;
                dfs(i, j);
            //    printf("cnt: %d\n", cnt);
                ans = max(ans, cnt);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

稍加分析一下就知道不对了.

比如, 先从A点开始扫描, A点最远能走到B点, 也就是B的周围有磁铁, 这个过程已经把B视为和A连通的块了, 且B也被标记为已访问.

那么, 下次从C点开始扫描时, 可能C点最远也能走到B点. 但由于B点已经被标记为已访问, 它不会被计入C可以到访的点中.

那要怎么修呢?

有个很暴力的做法, 就是以所有点为起点进行扫描 (每次扫描前都重置vis数组), 统计从每个点出发能到达的点的数量. 时间复杂度. 大概率通过不了.

但实际上, 我们不需要把所有点都当起点跑DFS, 如果一个点已经被访问过了, 有两种情况:

  1. 这个点周围没有磁铁, 那么它所能走过的点就是它所属的连通块. 这个之前已经求解过了.
  2. 这个点周围有磁铁. 那么它肯定只能作为终点存在.

也就是说, 我们只需要以未被访问过的点为起点来DFS, 且遍历过程中可以访问 以其它点为起点 所到访过 的点. 这样就没问题了.

时间复杂度应该也是. 实际上, 此题和普通的找连通块题的区别在于块与块之间可以共享边界.

感觉我赛时的代码实现不是很好, 当时给它当成染色来做了. 但无所谓, 能AC就行.

AC Code:

#include <cstdio>
#include <ctype.h>

#define N 1005

int n, m, ans = 1, cnt, num;
char map[N][N];
int vis[N][N];

int move1[4] = {0, 0, 1, -1};
int move2[4] = {1, -1, 0, 0};

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

inline int max(int a, int b){return a > b? a : b;}

bool valid(int x, int y){
    // 判断(x, y)是否在地图内且上下左右没有磁铁.
    return x > 0 && x <= n && y > 0 && y <= m &&
           map[x-1][y] != '#' && map[x+1][y] != '#' &&
           map[x][y-1] != '#' && map[x][y+1] != '#';
}

void dfs(int x, int y){
    ++cnt;
    vis[x][y] = num;
    if(!valid(x, y)) return;
    for(int i = 0; i < 4; ++i){
        int xx = x + move1[i], yy = y + move2[i];
        if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
        if(vis[xx][yy] != vis[x][y]) dfs(xx, yy);
    }
}

int main(){
    n = read(), m = read(); char ch = '\n';
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            while(ch == '\n') ch = getchar();
            map[i][j] = ch; ch = getchar();
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!vis[i][j] && map[i][j] == '.'){
                cnt = 0, vis[i][j] = ++num;
                dfs(i, j);
            //    printf("cnt: %d\n", cnt);
                ans = max(ans, cnt);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

F - Mah-jong

QOJ传送门

咕咕咕…

  • 标题: XCPC 寒假集训班 D2 个人笔记
  • 作者: Coast23
  • 创建于 : 2025-01-15 20:30:19
  • 更新于 : 2025-03-31 17:38:37
  • 链接: https://coast23.github.io/2025/01/15/XCPC-寒假集训班-D2-个人笔记/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
XCPC 寒假集训班 D2 个人笔记
  1. 讲评题
    1. 魔法阵
    2. 海港
    3. 深さ優先探索
    4. 八皇后 Checker Challenge
    5. Labyrinth [CF1063B]
    6. [蓝桥杯 2023 省 A] 买瓜
  2. 训练题
    1. D - Anji’s Binary Tree
    2. E - Grid and Magnet
    3. F - Mah-jong