ACM-蓝桥杯训练第一周
训练 蓝桥 ACM
2023-09-14 09:12:40 时间
🚀write in front🚀
📝个人主页:认真写博客的夏目浅石.CSDN
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏:ACM周训练题目合集.CSDN
💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊
✉️为什么我们不知疲倦,因为我们都在做自己所热爱的事 ♐
前言
本周进行了一些特别基础的练习来巩固知识,写成博客方便我去复习使用。
A - [例题]一维前缀和
思路:基础的前缀和模板题目,会公式即可。详细可以看我写的博客
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,q;
ll sum[100010];
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
ll tmp;
cin>>tmp;
sum[i]=sum[i-1]+tmp;
}
while(q--)
{
ll l,r;
cin>>l>>r;
printf("%lld\n",sum[r]-sum[l-1]);
}
return 0;
}
B - 二分查找
思路:基础的二分模板题目,详细可以看二分模板那篇博客。
#include<iostream>
using namespace std;
#define N 1000010
int a[N],n,m,q;
int main()
{
cin>>n>>m;
for(int i=0;i<n;++i) cin>>a[i];
for(int i=0;i<m;++i)
{
cin>>q;
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]>=q) r=mid;
else l=mid+1;
}
if(a[l]!=q) cout <<"-1"<<" ";
else cout<<l+1<<" ";
}
return 0;
}
C - 一维差分
思路:基础差分题目
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,p,a[5000010];
ll x,y,z,sum,b[5000010],mn=5000010,cnt;
int main()
{
cin>>n>>p;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=0;i<p;i++)
{
cin>>x>>y>>z;
b[x]+=z;
b[y+1]-=z;
}
for(int i=1;i<=n;i++)
{
sum+=b[i];
cnt=sum+a[i];
mn=min(mn,cnt);
}
cout<<mn<<endl;
return 0;
}
D - 快速幂
思路:快速幂算法(全网最详细地带你从零开始一步一步优化)(转载)
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll a,b,m;
int main()
{
cin>>a>>b>>m;
ll result=1;
while(b)
{
if(b%2==0)
{
b/=2;
a=a*a%m;
}
else
{
b-=1;
result=result*a%m;
b/=2;
a=a*a%m;
}
}
cout<<result<<endl;
return 0;
}
E - 质数筛
思路:暴力求素数
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int n;
int a[100010];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int j=0;
for(int i=0;i<n;i++)
{
for(j=2;j*j<=a[i];j++)
{
if(a[i]%j==0) break;
}
if(j>a[i]/j&&a[i]>=2) cout<<a[i]<<" ";
}
return 0;
}
F - 最短路径
思路:最短路的基础模板题目
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int n,m;
int u,v,w;
int g[110][110];
int path[110][110];
const int maxx=99999999;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) g[i][j]=0;
else g[i][j]=maxx;
}
}
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
g[u][v]=g[v][u]=w;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(g[i][j]>g[i][k]+g[k][j])
{
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",g[i][j]);
}
cout<<endl;
}
return 0;
}
G - 结构体排序
思路:我其实我对于结构体题目不是很熟悉,正好借这一个题目学到很多东西,语法题,重要的在于结构体格式
#include<iostream>
#include<algorithm>
using namespace std;
struct Stu
{
int math;
int chinese;
int english;
int sum;
int id;
}stu[350];
int cmp(Stu a,Stu b)
{
if (a.sum==b.sum)
{
if (a.chinese==b.chinese)
return a.id<b.id;
else return a.chinese>b.chinese;
}
else return a.sum>b.sum;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>stu[i].chinese>>stu[i].math>>stu[i].english;
stu[i].id=i;
stu[i].sum=stu[i].chinese+stu[i].math+stu[i].english;
}
sort(stu+1,stu+n+1,cmp);
for(int i=1;i<=5;i++)
{
cout<<stu[i].id<<" "<<stu[i].sum<<endl;
}
return 0;
}
H - sort
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[100010];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
for(int i=0;i<n;i++) cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
I - 二维前缀和
思路:二维前缀和公式: g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]
;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int g[1010][1010];
int T,n,m,x,y;
int main()
{
cin>>T;
while(T--)
{
memset(g,0,sizeof(g));
int res=0;
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
if(i>=x&&j>=y)
{
res=max(g[i][j]-g[i-x][j]-g[i][j-y]+g[i-x][j-y],res);
}
}
}
cout<<res<<endl;
}
return 0;
}
总结
本周复习了基础的模板题目,重在查漏补缺。
复习:前缀和,二维前缀和,差分,二分查找,sort排序,质数筛,结构体排序
学习:最短路问题,快速幂
我需要加强学习的:二维前缀和,结构体排序,质数筛的埃式筛选法。
相关文章
- Java实现 蓝桥杯 算法训练 Multithreading
- Java实现 蓝桥杯VIP 算法训练 数对
- Java实现 蓝桥杯VIP 算法训练 连接字符串
- Java实现 蓝桥杯VIP 算法训练 星际交流
- Java实现 蓝桥杯VIP 算法训练 平方计算
- Java实现 蓝桥杯VIP 算法训练 矩阵加法
- Java实现 蓝桥杯VIP 算法训练 入学考试
- Java实现 蓝桥杯VIP 算法训练 寂寞的数
- Java实现 蓝桥杯VIP 算法训练 明明的随机数
- Java实现 蓝桥杯VIP 算法训练 s01串
- Java实现 蓝桥杯VIP 算法训练 二元函数
- Java实现 蓝桥杯 算法训练 p1103
- Java实现 蓝桥杯 算法训练 最大的算式
- Java实现 蓝桥杯 算法训练 2的次幂表示
- Java实现 蓝桥杯 算法训练 矩阵乘法
- Java实现 蓝桥杯 算法训练 大小写转换
- Java实现 蓝桥杯 算法训练 Torry的困惑(基本型)
- Java实现 蓝桥杯 算法训练 关联矩阵
- DL之pix2pix:基于food_resized数据集利用TF框架的pix2pix模型实现Auto Color黑白图像上色/老照片上色/黑白变彩色技术—训练&测试过程全记录
- ML之DT:基于简单回归问题训练决策树(DIY数据集+三种深度的二元DT性能比较)
- NLP之NB:基于sklearn库利用不同语种数据集训练NB(朴素贝叶斯)算法,对新语种进行语种检测
- DL之DNN:利用MultiLayerNet模型【6*100+ReLU+SGD】对Mnist数据集训练来理解过拟合现象
- 词袋模型 测试数据使用和训练数据一样的词汇表
- 【阿里天池-医学影像报告异常检测】3 机器学习模型训练及集成学习Baseline开源
- 深度学习1 基于h5py使用数据迭代器训练超过内存的数据