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

桃扇骨 2024-04-17 10:12 123阅读 0赞

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

![在这里插入图片描述][997ce8f7ca7c454492e7e0d0febbee7c.png]

#### Day5集训 ####

*  前言
 *  A - 关于gcd
 *   *  解题思路
     *  示例代码
 *  B - gcd区间
 *   *  解题思路
     *  示例代码
 *  C - Cipher Shifer
 *   *  解题思路
     *  示例代码
 *  D - 质数筛
 *   *  解题思路
     *  示例代码
 *  E - 完全平方数
 *   *  解题思路
     *  示例代码
 *  F - Vika and Her Friends
 *   *  解题思路
     *  示例代码
 *  总结

## 前言 ##

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

## A - 关于gcd ##

**来源：**[洛谷P4549 【模板】裴蜀定理][P4549]  
算法标签：`数学、最大公约数、gcd不定方程`  
![在这里插入图片描述][2bc136ee1e1c4c3fa464bedcb5e9c49c.png]

### 解题思路 ###

这题要用到`裴蜀定理(或称贝祖定理)`，那么这个勾八定理是干啥的，怎么用呢？它其实就是二元一次方程ax+by=c存在整数解时c应为a、b的最小公约数。但是这里要注意将负数变为正后再求。

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int n,a,res;
    int gcd(int x,int y)
    {
        
    	return !y?x:gcd(y,x%y); 辗转相除法求最大公约数
    }
    int main()
    {
        
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>a;
    		a=a>0?a:-a;
    		res=gcd(res,a);
    	}
    	cout<<res;
    }

## B - gcd区间 ##

**来源：**[洛谷P1890 gcd区间][P1890 gcd]  
算法标签：`数学`  
![在这里插入图片描述][16c03cbde0de475fb00c36c0424a4bdc.png]

### 解题思路 ###

这题就是求所给区间的最大公约数，我看有`大佬用线段树`做的（但是我不会哈哈），我用动规思想做的

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll a,b,k[1005][1005],d,p;
    int main()
    {
        
    	cin>>a>>b;
    	for(int i=1;i<=a;i++)
    		cin>>k[i][i];
    	for(int i=a-1;i>=1;i--)
    		for(int j=i+1;j<=a;j++)
    			k[i][j]=__gcd(k[i][i],k[i+1][j]);
    	for(int i=1;i<=b;i++)
    	{
        
    		cin>>d>>p;
    		cout<<k[d][p]<<endl;
    	}		
    
    }

## C - Cipher Shifer ##

**来源：**[CodeforcesA. Cipher Shifer][]  
![在这里插入图片描述][a66e7789333848bc8b5e514d97a4d972.png_pic_center]  
![在这里插入图片描述][3f7cb6d9c4b74e19af0a6a1aa1251633.png]

![在这里插入图片描述][90a5ea798a704165a18e783979dc14d2.png]

### 解题思路 ###

遍历字符串并更新字符即可

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	int t,n;
    	cin>>t;
    	for(int i=0;i<t;i++)
    	{
        
    		cin>>n;
    		char c[110],b;
    		cin>>c;
    		b=c[0];
    		for(int j=1;j<n;j++)
    		{
        
    			if(b==c[j])
    			{
        
    				cout<<c[j];
    				j++;
    				b=c[j];
    			}
    		}
    		if(i!=t-1)
    			cout<<endl;
    	}
    }

## D - 质数筛 ##

**来源：**[洛谷P5736 【深基7.例2】质数筛][P5736 _7._2]  
![在这里插入图片描述][c8b173d1ee9b49ae90118b1b910470e3.png]

### 解题思路 ###

这题其实写个判断素数的函数就OK了，对啦，质数就是素数哦！

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    bool judge(int x)
    {
        
    	if(x<=1)
    		return false;
    	for(int i=2;i<=sqrt(x);i++)
    	{
        
    		if(x%i==0)
    			return false;
    	}
    	return true;
    }
    int main()
    {
        
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>m;
    		if(judge(m))
    			cout<<m<<" ";
    	}
    }

## E - 完全平方数 ##

**来源：**[洛谷P8754 \[蓝桥杯 2021 省 AB2\] 完全平方数][P8754 _ 2021 _ AB2_]  
算法标签：`数论、素数判断、质数、筛法`  
![在这里插入图片描述][487357b2422d47b6a9b96797a0b8aa82.png]

### 解题思路 ###

完全平方数想必大家都听过撒，而完全平方数有一个性质：`完全平方数的质因子的指数一定为偶数。`  
什么意思呢？如：`36=2^2 x 3^2= 6^2`

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n,x=1;
    int main()
    {
        
    	cin>>n;
    	for(ll i=2;i*i<=n;i++)
    	{
        
    		int cnt=0;
    		while(n%i==0)
    			cnt++,n/=i;
    		if(cnt%2==1)
    			x*=i;
    	}
    	x*=n;
    	cout<<x;
    }

## F - Vika and Her Friends ##

**来源：**[CodeforcesA. Vika and Her Friends][]  
![在这里插入图片描述][c6b5438fd2a44b05980128b24cfce216.png]  
![在这里插入图片描述][b33fbeecae6c4de985c2d1324acdb3f2.png]  
![在这里插入图片描述][c5476230cdef45b898acd3c1801f2321.png]

### 解题思路 ###

如果距离为奇数，那么就抓不住Vika，只有为偶数时才能抓住（我也不知道怎么说啦）

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int t;
    int n,m,k;
    int x,y,a,b,flag;
    int main()
    {
        	
    	cin>>t;
    	while(t--)
    	{
        
    		flag=0;
    		cin>>n>>m>>k>>x>>y;
    		for(int i=0;i<k;i++)
    		{
        
    			cin>>a>>b;
    			if((abs(x-a)+abs(y-b))%2==0)
    				flag=1;
    		}
    		if(flag)
    			printf("NO\n");
    		else
    			printf("YES\n");
    	}
    }

## 总结 ##

ADay5的题主要是数论的题。  
算法：`数论、最大公约数`  
感悟：想要学好算法，数学还是不能落下的呀（手动哭脸）  
总结：数论的题偏数学里的解题思路

[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
[997ce8f7ca7c454492e7e0d0febbee7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/91449e48e29f4317b17998f7b15a6217.png
[P4549]: https://www.luogu.com.cn/problem/P4549
[2bc136ee1e1c4c3fa464bedcb5e9c49c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/95408876fc964ce58f1fc32d488ea262.png
[P1890 gcd]: https://www.luogu.com.cn/problem/P1890
[16c03cbde0de475fb00c36c0424a4bdc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/94407285532749cda4e4115fdade95b4.png
[CodeforcesA. Cipher Shifer]: https://www.luogu.com.cn/problem/CF1840A
[a66e7789333848bc8b5e514d97a4d972.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4695d74877b04cf19bb6816488ba3eb9.png
[3f7cb6d9c4b74e19af0a6a1aa1251633.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/0f3e58027b624238b95054b0f6643fae.png
[90a5ea798a704165a18e783979dc14d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/239da3669f324d8d8ad0255bfc56b6f0.png
[P5736 _7._2]: https://www.luogu.com.cn/problem/P5736
[c8b173d1ee9b49ae90118b1b910470e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/42f756e5b9104f86a27b26a495f99d30.png
[P8754 _ 2021 _ AB2_]: https://www.luogu.com.cn/problem/P8754
[487357b2422d47b6a9b96797a0b8aa82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6ae42c8da533436f88d4f07cabe19255.png
[CodeforcesA. Vika and Her Friends]: https://codeforces.com/problemset/problem/1848/A
[c6b5438fd2a44b05980128b24cfce216.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/14e1548444dd4f8faf582da609c09293.png
[b33fbeecae6c4de985c2d1324acdb3f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/5c532109ca1f4f46a4a60e81dd898b93.png
[c5476230cdef45b898acd3c1801f2321.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/697dedc3505b4900ae3345a095cb2909.png