【AcWing周赛】AcWing第86场周赛
目录
<一>AcWing 4794. 健身
一、题目
1、原题链接
2、题目描述
二、解题报告
1、思路分析
2、时间复杂度
3、代码详解
<二>AcWing 4795. 安全区域
一、题目
1、原题链接
2、题目描述
二、解题报告
1、思路分析
2、时间复杂度
3、代码详解
<三>AcWing 4796. 删除序列
一、题目
1、原题链接
2、题目描述
二、解题报告
1、思路分析
2、时间复杂度
3、代码详解
<一>AcWing 4794. 健身
一、题目
1、原题链接
4794. 健身 - AcWing题库
2、题目描述
李华一共要进行 n 组健身训练。
其中，第 i 组训练的时长为 ai。
李华只做三种运动：胸部（
chest）运动、二头肌（biceps）运动、背部（back）运动。而且，三种运动是循环训练的，也就是说他第一组训练是胸部运动，第二组训练是二头肌运动，第三组训练是背部运动，第四组训练是胸部运动，第五组训练是二头肌运动......以此类推直到做完第 n 组训练。
请你计算，他做哪种运动的时长最长。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
共一行，如果训练时长最长的运动为：
- 胸部运动，则输出
chest。- 二头肌运动，则输出
biceps。- 背部运动，则输出
back。数据保证训练时长最长的运动是唯一的。
数据范围
前 3 个测试点满足 1≤n≤7。
所有测试点满足 1≤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
二、解题报告
1、思路分析
根据题意进行模拟即可，对n取模3来判断当前做哪种运动，分别统计运动时长，按要求输出结果，即为所求。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
int a[25];
int num[3];
int main()
{ int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
num[i%3]+=a[i];
}
int max=0;
int index=0;
for(int i=0;i<3;i++){
if(num[i]>max){
max=num[i];
index=i;
}
}
if(index==0){
cout<<"chest";
}
if(index==1){
cout<<"biceps";
}
if(index==2){
cout<<"back";
}
return 0;
}<二>AcWing 4795. 安全区域
一、题目
1、原题链接
4795. 安全区域 - AcWing题库
2、题目描述
给定一个 n×n 的方格棋盘和 m 个国际象棋中的车。
对于一个方格，如果该方格满足以下两个条件中的至少一个，则该方格会被车攻击到：
- 该方格内有车。
- 至少有一个车与该方格位于同一行或同一列。
现在，我们要将 m 个车逐个放入到棋盘中，其中第 i 个车放到棋盘的第 xi 行第 yi 列的方格中。
车的编号从 1 到 m，行/列的编号从 1 到 n。
保证任意两个车不会放到同一个方格中。
对于 1≤i≤m，请你计算，将前 i 个车放入到棋盘中后，有多少个方格不会被车攻击到。
输入格式
第一行包含两个整数 n,m。
接下来 m行，其中第 i 行包含两个整数 xi,yi，表示第 i 个车放到棋盘的第 xi 行第 yi 列的方格中。
输出格式
在 1 行内输出 m 个数，其中第 i 个数表示将前 i 个车放入到棋盘中后，不会被车攻击到的方格数量。
数据范围
前 3 个测试点满足 1≤m≤3。
所有测试点满足 1≤n≤10^5，1≤m≤min(10^5,n^2)，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
二、解题报告
1、思路分析
我的思路
1）本想建立一个10^5×10^5大小的二维矩阵再进行下面操作，但是直接超范围了，若开成整型数组需要4*10^5*10^5/1024/1024MB≈40000MB，所以无法实现，于是我就建立了两个数组，分别表示x轴方向和y轴方向，并且建立两个bool类型数组来判断x，y坐标是否是车点，如果都是，则说明这个点就是车点，否则说明这一行或这一列有车。
2）直接模拟即可，我是从总体中剔除被攻击到的方格，得到的就是不会被攻击到的方格。
3）TLE，最终只过了4个数据点。
思路来源：AcWing 4795. 安全区域（AcWing杯 - 周赛） - AcWing
y总yyds
y总思路
1）直接统计有总共多少行上有车，多少列上有车，假设有r行上有车，c列上也有车，则不能被攻击到的方格个数满足(n-r)*(n-c)[将这r行和c列都移到矩阵最上方和最左方，剩下的格子总数就是(n-r)*(n-c)]。
2）每加入一个车，统计当前多少行有车，多少列有车，然后根据公式输出结果，即为所求。
2、时间复杂度
我的思路的时间复杂度为O(n^2)
y总思路的时间复杂度为O(n)
3、代码详解
我的思路的代码
#include <iostream>
using namespace std;
long long dx[100010];
long long dy[100010];
bool isx[100010];
bool isy[100010];
long long x[100010];
long long y[100010];
long long M[100010];
int main()
{ long long n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
long long ans=n*n;
cin>>x[i]>>y[i];
dx[x[i]]=1;
dy[y[i]]=1;
isx[x[i]]=1;
isy[y[i]]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dx[i]==1&&dy[i]==1||isx[i]==1||isy[j]==1){
ans--;
}
}
}
M[i]=ans;
}
for(int i=0;i<m;i++){
cout<<M[i]<<" ";
}
return 0;
}y总思路的代码
#include <iostream>
using namespace std;
bool r[100010],c[100010];
int main()
{ int n,m;
cin>>n>>m;
int x,y;
int rnum=0,cnum=0;
for(int i=0;i<m;i++){
cin>>x>>y;
if(!r[x]) r[x]=1,rnum++;
if(!c[y]) c[y]=1,cnum++;
cout<<(long long)(n-rnum)*(n-cnum)<<" ";
}
return 0;
}<三>AcWing 4796. 删除序列
一、题目
1、原题链接
4796. 删除序列 - AcWing题库
2、题目描述
给定一个长度为 n 的正整数序列 a1,a2,…,an。
你可以进行任意次删除操作。
每次删除操作分为两步：
- 选择序列中的一个元素（不妨设其元素值为 x），并将这一个元素删除，这可以给你加 x 分。
- 将所有的元素值为 x−1 和 x+1 的元素（如果有的话）从序列中删除，这不会给你带来任何分数。
请计算，通过删除操作，你可以获得的最大得分。
输入格式
第一行包含整数 n。
第二行包含 n 个正整数 a1,a2,…,an。
输出格式
一个整数，表示可以获得的最大得分。
数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10^5，1≤ai≤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
二、解题报告
思路来源：AcWing 4796. 删除序列（AcWing杯 - 周赛） - AcWing
y总yyds
1、思路分析
1）dp[i]代表从数字1，2，3...一直到数字i的序列通过删除操作可以获得的最大得分（无论这个范围内某个数字是否出现过）。a[i]代表删除数字i后的得分，也就是数字i的出现次数乘数字i的价值（针对本题数字i的价值就是i的数值）。
2）dp[i]可以有两种情况递推出来，第一种情况是不删除数字i，从数字i-1开始删，第二种情况是删除数字i，下一个元素从数字i-2开始删。所以dp[i]=max(dp[i-1],dp[i-2]+a[i])。
3）dp[1]代表只有1个数字1，所以dp[1]的最大得分就是删除数字1，所以dp[1]初始化为a[1]，即删除数字1的得分。
4）我们要求的是从数字1一直到数字10^5的序列的最大得分（因为给出的数字范围是1≤ai≤10^5，即输入的数字可能为这个范围内的任何一个数），所以输出dp[100000]，即为所求。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
using namespace std;
long long dp[100010];
long long a[100010];//代表删除每个数后可以获得的得分
int main()
{ int n;
cin>>n;
long long t;
for(int i=1;i<=n;i++){
cin>>t;
//若数字重复出现，得分累加
a[t]+=t;
}
//序列长度为1，删除数字1，得分最大
dp[1]=a[1];
for(int i=2;i<=100010;i++){
//遍历所有可能出现的数字
dp[i]=max(dp[i-1],dp[i-2]+a[i]);
}
cout<<dp[100000];
return 0;
}