信息奥赛复盘

发布日期: 2023-05-10

文章字数: 3.6k

阅读时长: 14 分

阅读次数:

【Acwing 周赛复盘】第87场周赛复盘（2023.1.21）

周赛复盘 ✍️

本周个人排名：281/1252（22.4%）

AC情况：2/3

一次伴随着除夕夜鞭炮声、烟花声进行的周赛 🎉

大年三十都有1k多名小伙伴一起打比赛，不得不说 Acwing 的学习氛围真好

这是博主第二次参加的周赛，从排名比来看，相比第一次的 28.7% 略有进步😀

但是不知道为什么这次敲代码时比上次急躁不少，也许是第一次周赛复盘时，看见 TOP5 的大佬都是不到 5 分钟敲完了，实力的差距让自己有了心理压力吧

但是怎么说呢，实力和题量放在那，其实自己再怎么着急也是无济于事的，焦急的心态反而会影响自己的发挥，不如稳下心来，慢慢思考。

希望下次能够摆正心态，同时平常更加努力学习，继续加油 💪

周赛rank图

周赛信息 📚

时间：2023年 1 月 21 日 19：00-20：15

竞赛链接：https://www.acwing.com/activity/content/introduction/2814/

y总直播间：http://live.bilibili.com/21871779

y总录播讲解视频：【AcWing杯 - 第87场周赛讲解】

题目列表 🧑🏻‍💻

题目名称	原题链接	视频讲解	难度
4797. 移动棋子	原题链接	视频链接	简单 🟢
4798. 打怪兽	原题链接	视频链接	中等 🟡
4799. 最远距离	原题链接	视频链接	困难 🔴

题解 🚀

【题目A】移动棋子

【题目描述】

给定一个 $5$ 行 $5$ 列的方格矩阵，其中一个方格中有一个棋子。

现在，我们希望将棋子移动至矩阵的最中心方格中，即将其移动至矩阵的第 $3$ 行第 $3$ 列方格中。

每次移动可以将棋子沿上、下、左、右任一方向移动一格距离，前提是不能移出矩阵。

请你计算，为了将棋子移动至矩阵的最中心方格中，所需要的最少移动次数。

如果棋子一开始就在最中心方格中，则无需移动。·

【输入】

输入共 $5$ 行，每行包含 $5$ 个整数，其中第 $i$ 行第 $j$ 列的整数表示第 $i$ 行第 $j$ 列方格的状态，如果为 $0$，则表示该方格中没有棋子，如果为 $1$，则表示该方格中有棋子。

保证只有一个方格中有棋子。

【输出】

一个整数，表示所需要的最少移动次数。

【数据范围】

所有测试点满足，输入恰好包含 $24$ 个 $0$ 和 $1$ 个 $1$。

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【输入样例3】

【输出样例3】

【原题链接】

https://www.acwing.com/problem/content/4800/

【题目分析】

签到题，归纳起来就是求解两个点 $(x_a,y_a),(x_b,y_b)$ 之间的「曼哈顿距离」，公式：
$$
c = \lvert x_a - x_b\rvert + \lvert y_a - y_b \rvert
$$

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

int x;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; ++j) {
            cin >> x;
            // 当前坐标点值为1，输出其和中心点的距离
            if (x) {
                cout << abs(i - 3) + abs(j - 3) << endl;
                break;
            }
        }
    }

    return 0;
}

【周赛现场 AC 代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 10;
int a[N][N];
 
int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int x, y;
    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 1) {
                x = i;
                y = j;
            }
        }
    }

    cout << abs(x - 3) + abs(y - 3) << endl;

    return 0;
}

【代码总结分析】

刚开始想复杂了，把此题和 有障碍的 BFS、DFS 迷宫题 混为一谈，想着用搜索的方式去求解。写到一半发现没必要，直接用数学方法求解即可。
经过y总讲解，搜索了「曼哈顿距离」的相关内容，发现直接使用该公式即可，说明平常还是需要多积累。

【题目B】打怪兽

【题目描述】

有 $n$ 个怪兽（编号 $1∼n$），其中第 $i$ 个怪兽的防御值为 $a_i$。

你是一个魔法师，初始时拥有 $m$ 点法力值。

当你的法力值大于 $0$ 时，你可以对怪兽发动攻击，每一次攻击具体为：

任意选择 $1∼2$ 个怪兽，并消耗 $x$ 点法力值（$x$ 可以是一个不超过你当前法力值的任意正整数），对每个所选怪兽发动一次伤害为 $x$ 的攻击。
对于受到攻击的怪兽，如果其防御值 小于或等于 $x$，则会被你消灭。否则，它将免疫此次攻击，不受任何影响。

请你确定最大的整数 $k$，满足：通过合理安排攻击，可以将第 $1∼k$ 个怪兽全部消灭。

【输入】

第一行包含整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

【输出】

一个整数，表示最大的整数 $k$。

【数据范围】

前 $3$ 个测试点满足 $1 \le n,m \le 10$。

所有测试点满足 $1 \le n \le 1000$，$1 \le m \le 10^9$，$1 \le ai \le m$。

【输入样例1】

5 7
2 3 5 4 1

【输出样例1】

【输入样例2】

10 10
9 1 1 1 1 1 1 1 1 1

【输出样例2】

【输入样例3】

5 10
3 1 4 2 4

【输出样例3】

【原题链接】

https://www.acwing.com/problem/content/4801/

【题目分析】

二分 + 排序 + 贪心

二分满足条件的 k
临时数组拷贝 a[1]-a[k] ，从大到小进行排序
贪心法分析消灭怪兽的最优方式：把排好序的怪兽 2个2个为一组，每次消灭一组怪兽

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
int a[N], t[N], n, m;

bool check(int mid) {
    // 拷贝数组a到t
    for (int i = 1; i <= mid; i++) t[i] = a[i];
    // t数组从大到小排序
    sort(t + 1, t + mid + 1, greater<int>());

    // 两个数一组，累加每组第一个数
    int sum = 0;
    for (int i = 1; i <= mid; i += 2) {
        sum += t[i];
        // 判断当前sum是否已超出法力值m
        if (sum > m) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 二分寻找k
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << endl;

    return 0;
}

【周赛现场 AC 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1005;
int n, m;
int a[N], b[N];

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

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int km = 1;
    for (int k = 2; k <= n; ++k) {
        // 拷贝a数组前k个元素至b中
        for (int i = 1; i <= k; ++i) {
            b[i] = a[i];
        }
        // 对b数组排序
        sort(b + 1, b + k + 1, cmp);

        // 2个2个累加，判断当前1～k个元素需要的法力值是否 < 拥有法力值
        int j = 1;
        ll sum = 0;
        while (j <= k) {
            sum += b[j];
            j += 2;
        }
        if (sum <= m) km = k;
    }

    cout << km << endl;
    return 0;
}

【代码对比总结】

周赛现场求解 k 时，摊主是从 $1$ 开始枚举，判断当前 k 个数能否满足条件。虽然本题也能通过，但是如果 $n$ 的数据范围很大，该方法就不行了。
经过 y总讲解时，发现 k 具有二段性，可以通过二分的方法快速求解，大大降低时间复杂度，值得借鉴。
sort() 函数从大到小排序，除了自定义 cmp 函数，也可以选择添加 greater<int>() 参数：sort(t,t+n,greater<int>()) 的方式会更加方便。

【题目C】最远距离

【题目描述】

我们规定，如果一个无向连通图满足去掉其中的任意一条边都会使得该图变得不连通，则称该图为 有效无向连通图。

给定一个 $n$ 个点 $m$ 条边的 有效无向连通图，点的编号为 $1∼n$，所有边的长度均为 $1$。

两点之间的距离定义为两点之间的 最短距离。

请你计算，给定图中距离最远的两个点之间的距离。

【输入】

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示点 $a$ 和点 $b$ 之间存在一条无向边。

【输出】

一个整数，表示给定图中距离最远的两个点之间的距离。

【数据范围】

前三个测试点满足 $1 \le n,m \le 10$。

所有测试点满足 $1 \le n,m \le 10^5$，$1 \le a,b \le n$，$a \ne b$。

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【原题链接】

https://www.acwing.com/problem/content/4802/

【题目分析】

本题需要有一定的理论基础（理论内容见「算法基础课——搜索与图论（一）」）

图/树的存储（邻接表）
dfs 求解树的高度/直径
最大值、次最大值的迭代

有了这些基础后，会发现该题描述的「有效无向连通图」，其实就是 「树」 的定义；该问题就是求解树的最长直径。☘️

常用 解题思路 是：

Step1：遍历树的 n 个结点

Step2：求出以 结点 i 为根 的 子树高度最大值 和 次大值，两者之和就是以当前结点 i 为根的直径

Step3：输出 n 个结点的直径最大值

根据该解题思路，编写相应代码，具体见 y总讲解视频：视频链接

【二刷经历】

2023 年 4 月 11 日，摊主想要把这篇文章上传至自己的博客网站，于是再次阅读了这篇复盘，打算检查文章可能存在的错误。

在检查的过程中，摊主突然发现 C 题又不会做了，说明当时还是没有理解透彻，需要回炉重造。😂

回顾一下自己晚上的做题流程：

发现该题描述的数据结构为「树」
书写「邻接表」代码，存储树的结点和边
发现解题策略
- 选择一个结点 u 作为根结点
- 计算 u 的所有子树深度
- 取最大深度和次大深度为最终答案
根据思路书写代码框架
但是在写 dfs 时，发现理不清输入值、返回值、终止条件以及是否往回搜的判断条件

于是又去回顾了y总的讲解视频，以及自己写的代码注释，发现上面的思路其实存在一定问题。

上面的思路其实默认了「一开始选择哪个点作为根结点，得到的子树最大深度和次大深度之和都是一样的」，这是不对的 ❌

比如根结点 u 有 3 棵子树 ch1，ch2，ch3

子树 ch1 的深度为 2
子树 ch3 的深度为 1
子树 ch2 的根结点为 v，v 上又有两棵子树
- 一棵深度为 7
- 另一棵深度为 8

按照上面的思路，最后答案是子树 ch2 的最大深度 8 + ch1 的深度 2 等于 10。

但是显然，正确答案应该是 v 的两棵子树的深度之和，应该为 15 才对。

由此可见，从 u 往下遍历的过程中，ans 应该不断进行比较，即 ans = max(d1+d2,ans)，才能保证最后的答案是正确的。✅

同时还需思考，如何书写代码，才能使搜索从 u 一直往下，而 不会出现往回搜 的情况。

本题 值得反复咀嚼 的一些点：

dfs 的含义究竟是什么？
dfs 的输入值为什么是 int dfs(int u, int fa)，fa 有什么作用？
添加 st[] 数组可以达到 fa 的作用吗？
dfs 的返回值是什么?
dfs 是如何实现深度累加的？
为什么是 ans = max(ans,d1 + d2) 而不是直接 ans = d1 + d2 ？

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
int n, m;
int ans; // 定义全局答案

// 邻接表加边
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 返回结点fa以u为根结点的子树的最大深度
int dfs(int u, int fa) {
    int d1 = 0, d2 = 0;  // d1 表示当前结点子树高度最大值，d2表示当前结点子树高度次大值

    // 遍历当前结点u的所有子树
    for (int i = h[u]; ~i; i = ne[i]) { // 注意此时的i为idx的值，而非结点的值，容易和dfs的参数搞混
        // 由于是无向边，需要不走回路
        int j = e[i];
        if (j == fa) continue;

        // 计算当前子树高度
        int d = dfs(j, u) + 1;  // 不能写成dfs(i,u) + 1 或者 dfs(h[i],u) + 1，很容易出错

        // 更新子树的最大高度和次大高度
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2);
    return d1;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    memset(h, -1, sizeof h); // 邻接表的表头全部置为-1

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);  // 邻接表加边
    }

    dfs(1, -1);  // 从结点值为1的结点开始搜索（这里的1并不是idx=1的意思）

    cout << ans << endl;

    return 0;
}

【周赛现场 AC 代码】

该题现场未AC 😂

【代码对比总结】

周赛现场虽然想出了求解最长直径的思路，但是由于图论/搜索部分的理论内容学习不够扎实充分，导致没能够顺利写出 dfs 的代码，需要在复盘后，认真学习总结。

Rickyの水果摊

https://ricky2333.github.io/2023/05/10/acwing-di-87-chang-zhou-sai-fu-pan/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !

信息奥赛 Acwing C++

CS50 Lab8

CS50 Lab8 - Trivia｜2023 Spring

2023-05-17 CS50

CS50 CS50 Lab Web

CS50 Problem Set7

CS50 Problem Set7｜2023 Spring

2023-05-09 CS50

CS50 SQL CS50 PSet

复盘｜Acwing第87场周赛

【Acwing 周赛复盘】第87场周赛复盘（2023.1.21）

周赛复盘 ✍️

周赛信息 📚

题目列表 🧑🏻‍💻

题解 🚀

【题目A】移动棋子

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【输入样例3】

【输出样例3】

【原题链接】

【题目分析】

【复盘后的优化代码】✅

【周赛现场 AC 代码】

【代码总结分析】

【题目B】打怪兽

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【输入样例3】

【输出样例3】

【原题链接】

【题目分析】

【复盘后的优化代码】✅

【周赛现场 AC 代码】

【代码对比总结】

【题目C】最远距离

【题目描述】

【输入】

【输出】

【数据范围】

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【原题链接】

【题目分析】

【复盘后的优化代码】✅

【周赛现场 AC 代码】

【代码对比总结】

你的赏识是我前进的动力