题目链接

4794. 健身
4795. 安全区域
4796. 删除序列

题目描述

4794. 健身

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

其中，第 i 组训练的时长为 aia_iai​。

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

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

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

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

输出格式

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

胸部运动，则输出 chest。
二头肌运动，则输出 biceps。
背部运动，则输出 back。
数据保证训练时长最长的运动是唯一的。

数据范围

• 前 3 个测试点满足 1≤n≤71≤n≤71≤n≤7。
• 所有测试点满足 1≤n≤20，1≤ai≤251≤n≤20，1≤a_i≤251≤n≤20，1≤ai​≤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

分析：我们在遍历的过程中用 a , b , c 分别记录三个运动的训练时长，最后判断哪一种运动时长最长并返回相应的部门即可。

• 时间复杂度：O(n)O(n)O(n)

代码：

#include
using namespace std;int main(){int n;cin>>n;int a = 0,b = 0,c = 0;for(int i = 1;i <= n;i++){int x;cin>>x;if(i % 3 == 1) a += x;else if(i % 3 == 2) b += x;else if(i % 3 == 0) c += x;}int ma = max(a,max(b,c));if(ma == a) puts("chest");else if(ma == b) puts("biceps");else if(ma == c) puts("back");return 0;
}

4795. 安全区域

给定一个 n×nn×nn×n 的方格棋盘和 mmm 个国际象棋中的车。

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

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

现在，我们要将 m 个车逐个放入到棋盘中，其中第 iii 个车放到棋盘的第 xix_ixi​ 行第 yiy_iyi​ 列的方格中。

车的编号从 1 到 mmm，行/列的编号从 1 到 nnn。

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

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

输入格式

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

接下来 mmm 行，其中第 iii 行包含两个整数 xi,yi，x_i,y_i，xi​,yi​，表示第 iii 个车放到棋盘的第 xix_ixi​ 行第 yiy_iyi​ 列的方格中。

输出格式

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

数据范围

• 前 3 个测试点满足 1≤m≤31≤m≤31≤m≤3。
• 所有测试点满足 1≤n≤105，1≤m≤min(105,n2)，1≤xi,yi≤n1≤n≤105，1≤m≤min(10^5,n2)，1≤x_i,y_i≤n1≤n≤105，1≤m≤min(105,n2)，1≤xi​,yi​≤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

分析：用 rrr 表示车占用的行数，用 ccc 表示车占用的列数。最终剩下的方格数量为：(n−r)∗(n−c)(n - r) * (n - c)(n−r)∗(n−c)。

• 时间复杂度:O(n)O(n)O(n)

代码：

#include
#include
using namespace std;
using LL = long long;const int N = 1e5+10;//分别记录占用的行，占用的列
int row[N],col[N];int n,m;int main(){int n,m;cin>>n>>m;int r = 0,c = 0;for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);if(row[x] == 0){r++;row[x] = 1;}if(col[y] == 0){c++;col[y] = 1;}// * 1LL 将其转换为 long long 防止溢出cout<<(n-r) * 1LL * (n-c)<<" ";}return 0;
}

4796. 删除序列

给定一个长度为 nnn 的正整数序列 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

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

每次删除操作分为两步：

选择序列中的一个元素（不妨设其元素值为 xxx），并将这一个元素删除，这可以给你加 xxx 分。
将所有的元素值为 x−1x−1x−1 和 x+1x+1x+1 的元素（如果有的话）从序列中删除，这不会给你带来任何分数。
请计算，通过删除操作，你可以获得的最大得分。

输入格式

第一行包含整数 nnn。

第二行包含 nnn 个正整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

输出格式

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

数据范围

• 前 6 个测试点满足 1≤n≤101≤n≤101≤n≤10。
• 所有测试点满足 1≤n≤105，1≤ai≤1051≤n≤10^5，1≤a_i≤10^51≤n≤105，1≤ai​≤105。

输入样例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

在解答本题之前，可以先试着做下这道题：Leetcode.198 打家劫舍。本题就是在这道题的基础之上做了一些拓展。

分析：
我们可以用一个数组 aaa，记录相同元素的和。例如：输入出现了 3 次 5，那么 a[5]=15a[5] = 15a[5]=15。接着我们就可以将问题转换为打家劫舍这道题。
我们选择了a[i]a[i]a[i]，就不能再选 a[i−1]a[i-1]a[i−1] 和 a[i+1]a[i+1]a[i+1]。问要如何选，才能使总的值最大。
注意：由于数据范围比较大，可能会爆int，我们需要将其转为 long long（Java转为 long）。

具体的分析可以看这篇题解：状态机DP

• 时间复杂度：O(n)O(n)O(n)

代码：

#include
#include
using namespace std;
using LL = long long;const int N = 1e5+10;
LL a[N];
LL f[N][2];int main(){int n;cin>>n;int len = 0;for(int i = 1;i <= n;i++){int x;scanf("%d",&x);a[x] += x;len = max(len,x);}for(int i = 1;i <= len;i++){f[i][0] = max(f[i-1][0],f[i-1][1]);f[i][1] = f[i-1][0] + a[i];}cout<