[数据结构与算法]蓝桥杯题解

1，试题 算法训练 素因子去重

任何大于1的整数要么是素数，要么可以分解成素数的乘积，这样的分解是唯一的也就是说，题中的n，我们可以把它分解成这样的形式：n = pi^k1 * p2^k2 … pn^kn(pi是素数且ki>0)。

思路先设置一个p让p=1；然后我们从2开始循环到n，遇到一个能整除n的数我们就让p乘上这个数，然后再一直用n除这个数，直到n不能被这个数整除为止.

ac代码

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

2，试题 算法训练 小生物的逃逸

如果一个小生物在一个球内部那么这个小生物一定要穿过这个球面，所以我们要知道一个小生物需要穿过几层球面的问题可以转换成小生物在多少给球内部，然后我们通过点到球心的距离和半径的大小关系就可以求出小生物要穿过多少球面了

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N=107;
struct qiu
{
    int x,y,z,r;
}q[N];
struct sw
{
    int x,y,z;
}s[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i].x>>q[i].y>>q[i].z>>q[i].r;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>s[i].x>>s[i].y>>s[i].z;
    }
    for(int i=1;i<=m;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            int x=s[i].x-q[j].x;
            int y=s[i].y-q[j].y;
            int z=s[i].z-q[j].z;
            if(x*x+y*y+z*z<q[j].r*q[j].r)cnt++;
        }
        cout<<cnt<<" ";
    }
}

3.试题 算法训练 找零钱

这个题的话是一个需要加一点贪心思想的模拟题，就是如果收到100块的时候如果我有50块就先找一张50块钱，然后再找一张25，然后其他的就硬模拟就行

ac代码如下

#include<bits/stdc++.h>
using namespace std;
int a1=0,a2=0;
int main()
{
	int n;
	cin>>n;
	int pos=1;
	int x;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(pos==0)continue;
		if(x==25)a1++;
		else if(x==50)
		{
			if(a1>0)
			{
				a2++;
				a1--;
			}
			else 
			pos=0;
		}
		else
		{
			if(a2>0)
			{
				if(a1>0)
				{
					a2--;
					a1--;
				}
				else 
				{
					pos=0;
					continue;
				}
			}
			else if(a2==0) 
			{
				if(a1>=3)a1-=3;
				else 
				{
					pos=0;
					continue;
				}
			}
		}
	}
	if(pos==1)cout<<"YES";
	else cout<<"NO";
}

4，?研究兔子的土豪

这个题没给数据范围，一开始我觉得就斐波那契数列加一个mod操作，然后超时了。后面打了个表看了一下，发现循环到108次之后就会出现两个1，1。就是108是一个循环，每次斐波那契数列超过108之后就会重复之前的斐波那契数列，然后我们只需要求出108给斐波那契数列的值，在输出天数的时候输出n%108天的兔子数量就行

ac代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1007;
const int N=1e8+10;
int dp[N];
int main()
{
    dp[1]=1;
    dp[2]=1;
    dp[0]=0;
    long long n;
    cin>>n;
    for(int i=3;i<=108;i++)
    {
        dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    cout<<dp[n%108];
}

5.子串分值和【第十一届】【省赛】【B组】

只有第一次出现的字符才能对字串产生贡献，我们用一个pre数组记录当前字符上一次出现的位置，这个字符对答案产生的贡献就是（i-pre[s[i]]）*(len-i+1);

ac代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=100007;
int pre[N],v[30]={0};
int main()
{
    string s;
    cin>>s;
    long long ans=0;
    for(int i=0,k=1;i<s.size();k++,i++)
    {
        int x=s[i]-'a';
        ans+=(k-pre[x])*(s.size()-k+1);
        pre[x]=k;
    }
    cout<<ans;
}

6，活雷锋

这个题没什么好说的

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int pos=0;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=5;j++)
        {
            int x;
            cin>>x;
            if(x==16)pos=1;
        }
    }
    if(pos)cout<<"yes";
    else cout<<"no";
}