【ACM】—蓝桥杯大一暑期集训Day1

我会带着你远行 2024-04-17 10:11 83阅读 0赞

> ?欢迎来到本文?  
> ?个人简介：[陈童学哦][Link 1]，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。  
> ?系列专栏：[陈童学的日记][Link 2]  
> ?其他专栏：[C++STL][C_STL]，感兴趣的小伙伴可以看看。  
> ?希望各位→点赞? + 收藏⭐️ + 留言?  
> ⛱️学习应使你快乐！望与诸君共勉！?♂️

![在这里插入图片描述][2ff49277181d4390b3cf6856746b9c7c.png]

#### Day1集训 ####

*  前言
 *  A - 查找
 *  B - 地毯
 *  C - 数楼梯
 *  D - 宇宙总统
 *  E - 高低位交换
 *  F - Worms
 *  总结

## 前言 ##

> 因参加了我校的ACM暑期集训为之后的xcpc等赛事做准备，所以就有了此文哈哈。本文主要复盘做题的过程以及一些感悟，便于复习巩固。辣么现在废话也不多说啦，直接往下看吧哈哈。

## A - 查找 ##

**来源：**[洛谷P2249 【深基13.例1】查找][P2249 _13._1]  
![在这里插入图片描述][897595b9f4ed4ffc8cfe85147de4392b.png]**解题思路**  
本题用暴力搜索是过不了的，因为序列是有序的，所以在对每次需要进行查询的数用`二分查找`即可。

**AC代码**

#include<iostream>
    using namespace std;
    const int N=1000005;
    int n,m,q,a[N];
    int main(){
        
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    		scanf("%d",&a[i]);
    	for(int i=1;i<=m;i++){
        
    		int l=1,r=n;
    		scanf("%d",&q);
    		while(l<r){
        
    			int mid=(l+r)/2;
    			if(a[mid]>=q)
    				r=mid;
    			else
    				l=mid+1;
    		}
    		if(a[l]==q)
    			printf("%d ",l);
    		else
    			printf("-1 ");
    	}
    }

## B - 地毯 ##

**来源：**[洛谷P3397 地毯][P3397]  
![在这里插入图片描述][c952cc09eb2f46f5a68ef58d863db7d3.png]  
![在这里插入图片描述][c8447651599d45459fd1faec10889e53.png]  
![在这里插入图片描述][8a7e531052af4e7da146682d89823d51.png]  
**解题思路**  
这题数据不是很强，暴力也能过，所以我就`暴力`啦…

**AC代码**

#include<iostream>
    using namespace std;
    int n,m,x1,x2,y1,y2;
    int s[1005][1005]={
        0};
    int main(){
        
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;i++){
        
    		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    		for(int j=x1;j<=x2;j++)
    			for(int k=y1;k<=y2;k++)
    				s[j][k]++;
    	}
    	for(int i=1;i<=n;i++){
        
    		for(int j=1;j<=n;j++)
    			printf("%d ",s[i][j]);
    		cout<<endl;
    	} 
    }

## C - 数楼梯 ##

**来源：**[洛谷P1255 数楼梯][P1255]  
![在这里插入图片描述][8de12aeb1eab406abb893d0a8eb72ccc.png]  
**解题思路**  
本题需要使用到`高精度`以及数学知识`斐波那契`（想必大家都知道哈，默认知道哈哈）。因为每次只能走一步或者两步，那么当前所在阶梯的方案数=上一阶梯方案数+上上一阶梯方案数，即**s\[i\]=s\[i−1\]+s\[i−2\]**.。但是因为本题数据较大，所以直接一维数组的话不够用，这样用的是二维来储存。  
**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    int n,s[5005][5005],length;
    void find(int x){
        
    	for(int i=1;i<=length;i++)
    		s[x][i]=s[x-1][i]+s[x-2][i];
    	for(int i=1;i<=length;i++){
        
    		if(s[x][i]>=10){
        
    			s[x][i+1]+=s[x][i]/10;
    			s[x][i]%=10;
    			if(s[x][length+1]>0)
    				length++;
    		}
    	}
    }
    int main(){
        
    	cin>>n;
    	length=1;
    	s[1][1]=1;
    	s[2][1]=2;
    	for(int i=3;i<=n;i++)
    		find(i);
    	//注意逆序输出哈 
    	for(int i=length;i>=1;i--)
    		cout<<s[n][i];
    }

## D - 宇宙总统 ##

**来源：**[洛谷P1781 宇宙总统][P1781]  
![在这里插入图片描述][61326362f51745299cd7e10efe474fea.png]  
**解题思路**  
本题也是道`高精度`的题，用`字符串`就好了

**AC代码**

#include<iostream>
    using namespace std;
    int n,win;
    string s1,s2="";
    int main(){
        
    	cin>>n;
    	for(int i=1;i<=n;i++){
        
    		cin>>s1;
    		int t1=s1.size();
    		int t2=s2.size();
    		if(t1>t2||(t1==t2&&s1>s2)){
        
    			s2=s1;
    			win=i;
    		}
    	}
    	cout<<win<<endl<<s2;
    }

## E - 高低位交换 ##

**来源：**[洛谷P1100 高低位交换][P1100]  
![在这里插入图片描述][46050ddf1650495ea8279c3ddc40259e.png]  
**解题思路**  
本题主要运用到的`位运算`，直接左移16位和右移16位就OK  
**AC代码**

#include<iostream>
    using namespace std;
    unsigned long long n;//无符号类型
    int main(){
        
    	scanf("%u",&n);
    	printf("%u",(n>>16)+(n<<16));
    }

## F - Worms ##

**来源：**[CodeForces-474B. Worms ][CodeForces-474B. Worms]  
![在这里插入图片描述][75b086b70e6a44d596e86e10b805181a.png]  
![在这里插入图片描述][21b84d93a1904d53b49f69350b356601.png]  
**翻译：**  
![在这里插入图片描述][660e66c4919d4bed91e981f9180767cd.png]  
**解题思路**  
本题用`前缀和`以及`二分查找`即可求解  
**AC代码：**

#include<iostream>
    using namespace std;
    const int N=100005;
    int n,a[N],b[N];
    int m,label;
    int main(){
        
    	cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	for(int i=2;i<=n;i++)//前缀和
    		a[i]+=a[i-1];
    	cin>>m;
    	for(int i=1;i<=m;i++){
        
    		cin>>label;
    		int l=1,r=n,mid=(l+r)/2;//二分查找
    		while(l<r){
        
    			if(label<=a[mid]){
        
    				r=mid-1;
    			}else{
        
    				l=mid;
    				cout<<l<<endl;
    			}		
    		}
    	}
    }

## 总结 ##

Day1的题主要考察的是一些基础的算法。  
算法：`二分查找、前缀和、数学、位运算、高精度、暴力搜索`  
感悟：这些算法算是比较基础的，只需多加练习就能熟练掌握  
总结：算法的运用还是比较灵活的，能极大的减小时间复杂度

[Link 1]: https://blog.csdn.net/H1727548?type=blog
[Link 2]: https://blog.csdn.net/h1727548/category_12342877.html?spm=1001.2014.3001.5482
[C_STL]: https://blog.csdn.net/h1727548/category_12319887.html?spm=1001.2014.3001.5482
[2ff49277181d4390b3cf6856746b9c7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/b6a740ddbc0d42639d0a36b7fc52854c.png
[P2249 _13._1]: https://www.luogu.com.cn/problem/P2249
[897595b9f4ed4ffc8cfe85147de4392b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/2cfe27d02e1943718f48e421306e4b85.png
[P3397]: https://www.luogu.com.cn/problem/P3397
[c952cc09eb2f46f5a68ef58d863db7d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/346f0d30501f4f569e85135df3ae61b0.png
[c8447651599d45459fd1faec10889e53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/90a7a83761cb48f0bce222815586b288.png
[8a7e531052af4e7da146682d89823d51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/a26bfff1f1b84369b914b3cd892e5cec.png
[P1255]: https://www.luogu.com.cn/problem/P1255
[8de12aeb1eab406abb893d0a8eb72ccc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/5e91ccdea0a74a49b1ac4a39c81353ca.png
[P1781]: https://www.luogu.com.cn/problem/P1781
[61326362f51745299cd7e10efe474fea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/feb1ddd3f81647a3aeb856204945fd19.png
[P1100]: https://www.luogu.com.cn/problem/P1100
[46050ddf1650495ea8279c3ddc40259e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/878f0c0ed9574f7880bb2f471ad91d8d.png
[CodeForces-474B. Worms]: https://codeforces.com/problemset/problem/474/B
[75b086b70e6a44d596e86e10b805181a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/1c975976a8804638bcbb082cb2bd9ad5.png
[21b84d93a1904d53b49f69350b356601.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/fdedd1a0f92544d9b5a7e8b5abd90478.png
[660e66c4919d4bed91e981f9180767cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/25db145402c94a0eb3d2236e1961e421.png