【Acwing 周赛复盘】第86场周赛复盘

周赛复盘 ✍️

本周个人排名678/2358

AC情况2/3

这是博主参加的第一次周赛深刻体会到了世界的参差 😂

看到排名 TOP3 的大佬都是不到 5 分钟内就 AK 了真是恐怖如斯ORZ

对比下来自己做满 75 分钟并且只 AC 了 2 题真是弱爆了。。。

希望未来也能继续努力紧跟大佬们的步伐继续加油 💪

周赛信息 📚

时间2023年1月14日1900-2015

竞赛链接https://www.acwing.com/activity/content/2794/

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

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

题目列表 🧑🏻‍💻

题目名称	原题链接	难度
4794. 健身	原题链接	简单 🟢
4795. 安全区域	原题链接	中等 🟡
4796. 删除序列	原题链接	困难 🔴

题解 🚀

【题目A】健身

【题目描述】

李华一共要进行 $n$ 组健身训练。

其中第 $i$ 组训练的时长为 $a_i$。

李华只做三种运动胸部chest运动、二头肌biceps运动、背部back运动。

而且三种运动是循环训练的也就是说他第一组训练是胸部运动第二组训练是二头肌运动第三组训练是背部运动第四组训练是胸部运动第五组训练是二头肌运动…以此类推直到做完第 $n$ 组训练。

请你计算他做哪种运动的 时长 最长。

【输入】

第一行包含整数 $n$。

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

【输出】

共一行如果训练时长最长的运动为

• 胸部运动则输出 chest。
• 二头肌运动则输出 biceps。
• 背部运动则输出 back。

数据保证训练时长最长的运动是唯一的。

【数据范围】

前 $3$ 个测试点满足 $1\le n\le 7$。
所有测试点满足 $1\le n\le 20$$1\le a_i\le 25$。

【输入样例1】

2
2 8

【输出样例1】

biceps

【输入样例2】

3
5 1 10

【输出样例2】

back

【输入样例3】

7
3 3 2 7 9 6 8

【输出样例3】

chest

【原题链接】

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

---

【题目分析】

签到题简单模拟即可。但是现场编写的代码有很多可以改进和优化的地方见下面「代码对比总结」部分

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

int s[3];

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

    int n;
    cin >> n;

    int x;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        // 下面的写法避免了多个if
        s[i % 3] += x;  // s[1]存储chest、s[2]存储biceps、s[0]存储back
    }

    // 找到最大值下标
    int k = 0;
    for (int i = 1; i <= 2; ++i) {
        if (s[i] > s[k])
            k = i;
    }
  
    // 输出结果
    if (k == 1) cout << "chest" << endl;
    else if (k == 2) cout << "biceps" << endl;
    else cout << "back" << endl;
    
    return 0;
}

【周赛现场 AC 代码】

#include<bits/stdc++.h>

using namespace std;

int n, tmp;
int chest,biceps,back;

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> tmp;
        if (i % 3 == 1) {
            chest += tmp;
        } else if (i % 3 == 2) {
            biceps += tmp;
        } else {
            back += tmp;
        }
    }
//    cout << chest << " " << biceps << " " << back << endl;

    if (chest > biceps) {
        if (chest > back) {
            cout << "chest" << endl;
        } else {
            cout << "back" << endl;
        }
    } else {
        if (biceps > back) {
            cout << "biceps" << endl;
        } else {
            cout << "back" << endl;
        }
    }

    return 0;
}

【代码总结分析】

• s[i%3] += x 的思路值得借鉴省去了多个 if 判断
• 寻找最大值下标的方式值得借鉴优化了直接比较的多 if 判断

---

【题目B】安全区域

【题目描述】

给定一个 $n\times n$ 的方格棋盘和 $m$ 个国际象棋中的车。

对于一个方格如果该方格满足以下两个条件中的至少一个则该方格会被车攻击到

• 该方格内有车。
• 至少有一个车与该方格位于同一行或同一列。

现在我们要将 $m$ 个车逐个放入到棋盘中其中第 $i$ 个车放到棋盘的第 $x_i$ 行第 $y_i$ 列的方格中。

车的编号从 $1$ 到 $m$行/列的编号从 $1$ 到 $n$。

保证任意两个车不会放到同一个方格中。

对于 $1\le i\le m$请你计算将前 $i$ 个车放入到棋盘中后有多少个方格不会被车攻击到。

【输入】

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

接下来 $m$ 行其中第 $i$ 行包含两个整数 $x_i,y_i$表示第 $i$ 个车放到棋盘的第 $x_i$ 行第 $y_i$ 列的方格中。

【输出】

共 1 行其中第 $i$ 行输出将前 $i$ 个车放入到棋盘中后不会被车攻击到的方格数量。

【数据范围】

前 33 个测试点满足 $1\le m\le 3$。
所有测试点满足 $1\le n\le 10^5$$1\le m\le min(10^5,n^2)$$1\le x_i,y_i\le n$。

【输入样例1】

3 3
1 1
3 1
2 2

【输出样例1】

4 2 0

【输入样例2】

5 2
1 5
5 1

【输出样例2】

16 9

【输入样例3】

100000 1
300 400

【输出样例3】

9999800001

【原题链接】

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

---

【题目分析】

思维题需要通过 数学推导 的方式得到未被攻击的方格数数量为$(n-c)\ast (n-r)$其中 $c,r$ 为被攻击的列数、行数

🍉 PS本题数据范围较大需要使用 long long 类型不然会报错。在公式前强制转换即可(ll)(n-c)*(n-r)

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
int n, m, x, y;
int a[N], b[N];

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

    cin >> n >> m;
    int row = 0, col = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y;
      
      	// 统计当前被攻击的行数、列数
        if (!a[x]) a[x] = 1, row++;
        if (!b[y]) b[y] = 1, col++;

        // 求剩余个数的公式该形式容易推导和记忆
        cout << (ll) (n - row) * (n - col) << " ";
    }

    return 0;
}

【周赛现场 AC 代码】

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];
int n, m, x, y;
ll ans[N];

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

    cin >> n >> m;
    ll sum = (ll) n * n;

    int row = 0, col = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y;
        if (!a[x]) a[x] = 1, row++;
        if (!b[y]) b[y] = 1, col++;
        cout << (ll) sum - (ll) row * n - (ll) col * (n - row) << " ";
    }

    return 0;
}

【代码对比总结】

• 推导的公式可以写成 $(n-c)\ast (n-r)$ 这样更加 简洁且容易记忆 的形式。
• 在使用 (ll) 的 强制转换 时需要注意 哪些项会爆 int。本次周赛敲代码时由于没有考虑该问题以为在最前面加上 (ll) 就能整体转换导致 (ll) sum - row * n - col * (n - row) 这样 爆int 的错误没能被及时发现极大的影响了 AC 时间和心态

---

【题目C】删除序列

【题目描述】

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots ,a_n$。

你可以进行任意次删除操作。

每次删除操作分为两步

1. 选择序列中的一个元素不妨设其元素值为 $x$并将这 **一个 **元素删除这可以给你加 $x$ 分。
2. 将 所有 的 元素值 为 $x-1$ 和 $x+1$ 的元素如果有的话从序列中删除这不会给你带来任何分数。

请计算通过删除操作你可以获得的最大得分。

【输入】

第一行包含整数 $n$。

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

【输出】

一个整数表示可以获得的最大得分。

【数据范围】

前 $6$ 个测试点满足 $1\le n\le 10$。

所有测试点满足 $1\le n\le 10^5$$1\le a_i\le 10^5$。

【输入样例1】

2
1 2

【输出样例1】

2

【输入样例2】

3
1 2 3

【输出样例2】

4

【输入样例3】

9
1 2 1 3 2 2 2 2 3

【输出样例3】

10

【原题链接】

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

---

【题目分析】

动态规划题需要平时积累详细讲解见 y总讲解录像链接

【复盘后的优化代码】✅

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
typedef long long ll;

ll s[N], dp[N];
int n, x;

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        s[x] += x;  // s数组类似于"桶"这里的"桶"直接存储总和
    }

    // 动态规划
    for (int i = 1; i <= N - 1; ++i) {
        // 状态转移方程
        dp[i] = max(dp[i - 1], dp[(max(0, i - 2))] + s[i]);
    }

    cout << dp[N - 1] << endl;

    return 0;
}

【周赛现场 AC 代码】

该题现场未AC 😂

【代码对比总结】

• 周赛现场没能看出本题为动态规划题导致蛮力模拟一直解不出来。说明需要 多做题多积累。

---