牛客练习赛79部分题题解

前三题蛮简单，第4题不会了。
这里放上前4题的题解。

A 炼金术师

题目大意：
给一块无限长的画布，共有n次机会，每次可以从画布左端涂上一种长度为a[i]的颜色，第i次选择的颜色为为i。后涂的颜色会覆盖先涂的颜色。问给出n次的长度，一共可以产生多少种颜色。

思路：
由于后涂的覆盖先涂的，因此我们可以倒着处理。从后往前遍历每次的长度，因此我们只需要维护一个最大值maxi表示当前的最大涂色长度，若当前的长度a[i]>maxi说明后面的涂色没能完全覆盖本次的涂色，因此我们就更新maxi，并且让答案+1

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000040];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int maxi=0;
    int ans=0;
    for(int i=n;i>=1;i--){
        if(a[i]>maxi){
            ans++;
            maxi=a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

B 刀工对决

题目大意：
给出两条鱼长度分别为a和b。
现在又两种菜刀，使用第一种菜刀会让长度变为原来的3/5，使用第二种菜刀会让长度变为原来的1/3。
问最少多少次能让两条鱼长度相同，如果不可能相同输出-1.

思路：
由于第二种菜刀是除以3的操作，所以实际上是对数字进行除以5和除以3的操作。
显然我们把a和b都尽量的除5和3，最后如果相同那么说明肯定可以做到，否则就是不可能相同。
那要让操作次数尽量少，感觉可以用bfs去试试。
我这里是分别记录下两个数除以5和3的次数，假设是x1,y1和x2,y2。
那么这里x1和x2中肯定有多除的，我们只需要令abs(x1-x2)就是从a到b需要除以5的次数，同理我们计算abs(y1-y2)为除以3的次数，两个加起来就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b;
    cin>>n;
    int flag=0;
    long long ans=0;
    while(n--){
        cin>>a>>b;
        if(flag)continue;
        int x,y;
        x=y=0;
        while(a%5==0)a/=5,a*=3,x++;
        while(a%3==0)a/=3,x++;
        while(b%5==0)b/=5,b*=3,y++;
        while(b%3==0)b/=3,y++;
        if(a==b){
            ans+=abs(x-y);
        }
        else flag=1;
    }
    if(flag==0)
    cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}

C 小G的GCD

思路：
根据题目意思，我们可以写个暴力找一下规律。
发现符合斐波那契数列的增长，那么就简单了。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll x,ll y){
    if(!y)return 1ll;
    return gcd(y,x%y)+1ll;
}
ll maxgcd(ll n){
    ll ans=0ll;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            ans=max(ans,gcd(i,j));
        }
    }
    return ans;
}
int main()
{
    ll n;
    cin>>n;
    ll a,b,c;
    a=0,b=1;
    c=a+b;
    int ans=1;
    while(c<=n){
        a=b,b=c,c=a+b;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

-D 回文字D

题目大意：
给一个字符串，问最少分k段，让k段都满足是回文字D串。
回文字D串满足如下要求之一即可：
① len<D
② len>=D ，并且字符串中的任意长度为D的子串都是回文串。

思路：
本题不会做，参考了一个大佬的题解。
看题解的时候发现自己忽略了len>=D的时候要求里面所有长度为D的子串都是回文串的限制。
这个限制其实很严格，那么可以用贪心做。
我们可以枚举长度为D的子串：
如果这个子串不是回文串，我们把前面D-1个字符分成一段；
如果这个子串是回文串，那么我们再往后看一个字符s[i]，看看加入这个字符能否满足回文字D串，由于[i-1+D-1,i-1]已经是回文串了，那么我们只需要判断[i-D+1,i]是否为回文串就好了。如果满足，那么我们继续往后看。当不满足的时候，我们把前面的分成一段。
上面判断回文串我们可以哈希预处理，然后O(1)查询。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,D;
string s;
unsigned long long lh[10000040],rh[10000040],p[10000040];
int base=233;
int main()
{
    cin>>n>>D;
    cin>>s;
    p[0]=1;
    for(int i=0;i<s.length();i++){
        int x=s[i];
        lh[i+1]=lh[i]*base+x;
        p[i+1]=p[i]*base;
    }
    for(int i=s.length()-1;i>=0;i--){
        int x=s[i];
        rh[i+1]=rh[i+2]*base+x;
    }
    int ans=0;
    int l,r;
    for(int i=1;i<=n;i=r+1){
        l=i;
        r=l+D-2;   //先看到D-1个
        while(r+1<=n&&lh[r+1]-lh[l-1]*p[r+1-l+1]==rh[l]-rh[r+1+1]*p[r+1-l+1])r++,l++;
        //while枚举从第D个开始
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}