2023年寒假算法训练营周赛Round 3
P5724 【深基4.习5】求极差 / 最大跨度值
题意
给出 n 和 n 个整数 a i，求这n 个整数中的极差是什么。极差的意思是一组数中的最大值减去最小值的差。
思路
- 运用最大值减去最小值
坑点
- 无
算法一：
实现步骤
- 将最大值减去最小值
代码
#include<bits/stdc++.h>
using namespace std;
int a[100001];//将在a数组里
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
cout<<a[n]-a[1];//a[n]为最大值，-a[1] 为最小值
return 0;
}
总结
一道很简单的基础题
题目名字
题意
设有一个
N×M方格的棋盘(1≤N≤100,1≤M≤100)求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。
思路
- 找规律
坑点
- 不注意正方形以及长方形的区分
算法一
实现步骤
1.小写为正方形个数，大写为长方形加上正方形个数
代码
#include<iostream>
#include<cmath> //头文件
int n,m,sum,N,M,SUM; //定义，小写的是求正方形个数的 ，大写的是求正方形+长方形个数的
int main()
{
cin>>n>>m; //读入棋盘的长和宽
//输入
for(int i=1; i<=min(n,m); i++) //枚举边长，记住min(n,m)，因为正方形只能由小的那条边作为边长，记住，这个min函数是在cmath库里调用的
sum+=(n-i+1)*(m-i+1); //套公式（n-边长+1）*（m-边长+1）
//求正方形，知识点：1.正方形只能由小的那条边作为边长 2.对于不同边长的正方形就有（棋盘边长-枚举变长+1）条边
for(int i=1; i<=n; i++)
N+=i; //求一条长的和，累加1~n
for(int i=1; i<=m; i++)
M+=i; //求一条宽的和，累加1~m
SUM=N*M-sum; //根据（1~n的和）*（1~m的和）-正方形的个数算出长方形个数
//求长方形，知识点：公式的推导
cout<<sum<<" "<<SUM; //输出正方形个数和长方形个数
//输出
return 0;
}
总结
数学奥数问题
P3397 地毯
题意
在n*n的方格内铺m个地毯，在得知地毯所涉及的坐标后，求每一个坐标上被覆盖到的地毯数
思路
1.记住最大值减去最小值
坑点
- 图容易看错
算法一
实现步骤
- 由样例来进行推导
代码
#include<cstdio>
#include<iostream>
using namespace std;
int cf[2000][2000];
int main()
{
int n,m;
int x1,y1,x2,y2;
scanf("%d%d",&n,&m);
while(m--)//循环的另一种方式（m==0时，会自动跳出，所以循环m遍）.
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=x1;i<=x2;i++)//每一行进行差分，时间复杂度O(N)
{
cf[i][y1]++;
cf[i][y2+1]--;//差分
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cf[i][j]+=cf[i][j-1];//复原，利用A[I]-A[I-1]=B[I]，可以推得B[I]+A[I-1]=A[I]（因为B[I-1]已被复原为A[I-1]，所以得到此递推公式）
printf("%d ",cf[i][j]);//复原后输出
}
printf("\n");//换行
}
return 0;
}
算法二
实现步骤
- 定义二维数组
- 利用for循环计算每个坐标点上存在的地毯数
代码
using namespace std;
int a[1010][1010];
int main()
{
int n,m;
cin>>n>>m;
int x1,y1,x2,y2; //定义左上方与右下方的坐标点
for (int i=1;i<=m;i++)
{
cin>>x1>>y1>>x2>>y2;
for (int j=x1;j<=x2;j++)
{
for(int k=y1;k<=y2;k++)
{
a[j][k]++;
}
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
P2021 faebdc玩扑克
题意
zky 有 n 个扑克牌，编号从 11 到 n，zky 把它排成一个序列，每次把最上方的扑克牌放在牌堆底，然后把下一张扑克牌拿出来输出，最终输出的序列恰好是从 11 到 n，faebdc 问你原序列是什么，因为 faebdc 神犇早已在 O(1)的时间得出结果，如果你在1 s内答不出来，faebdc会吃了你。
思路
1.运用了约瑟夫问题
算法一
stl，链表
实现步骤
- 首先，在做此题之前，我们需要了解到的一点是：不管一张牌上面写的数字是几，只要牌的总量不变，牌的位置不变，最终这张牌到达的位置总是不变的
- 我们需要求的一个关键数组是每个位置的同学（牌）换座位（洗牌）之后被换到了哪个位置。
代码
#include <bits/stdc++.h>
using namespace std;
int a[1000001];
int n;
int b(int x)
{
int t;
t=x+1;
if (t>n)
{
t-=n;
}
}
int main(){
int i,j,s=0;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
for (j=1;j<=2;j++)
{
s++;
if (s>n)
{
s-=n;
}
while (a[s]!=0)
{
s++;
if (s>n)
{
s-=n;
}
}
}
a[s]=i;
}
for (i=1;i<=n;i++)
printf("%d ",a[i]);//每个数之间要空一格
return 0;
}