Acwing——第86场周赛

题目链接

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

题目描述

4794. 健身

李华一共要进行 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 201\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

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

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

代码

#include<iostream>
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\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$ 列的方格中。

输出格式

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

数据范围

• 前 3 个测试点满足 $1\le m\le 3$。
• 所有测试点满足 $1\le n\le 1051\le m\le min(10^5,n2)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

分析用 $r$ 表示车占用的行数用 $c$ 表示车占用的列数。最终剩下的方格数量为$(n-r)\ast (n-c)$。

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

代码

#include<iostream>
#include<algorithm>
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. 删除序列

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

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

每次删除操作分为两步

选择序列中的一个元素不妨设其元素值为 $x$并将这一个元素删除这可以给你加 $x$ 分。
将所有的元素值为 $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

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

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

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

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

代码

#include<iostream>
#include<algorithm>
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<<max(f[len][0],f[len][1])<<endl;
    return 0;
}