[数据结构与算法]牛客练习赛79(题解报告）

?题目链接牛客练习赛79_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

目录

A-炼金术师?

题目：?

思路分析：

代码实现：

B-刀工对决

题目：????????

思路分析：

代码实现：

???????

A-炼金术师?

题目：

思路分析：

根据染色覆盖规律

我们要找的就是整个序列的最大峰值的递减个数（先找到一个最大的峰点然后在他之后的第二大 在第二大点后面找第三到的峰点 依次寻找 最后统计个数

这个过程我们可以拿栈来实现！

听不懂的话看代码就行！?

代码实现：

const int MAX=2e6;
int a[MAX];
int main(){
    int n;
    n=read();
    stack<int>st;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(st.size()&&a[i]>st.top()){
            st.pop();
        }
        st.push(a[i]);
    }
    cout<<st.size();
}

B-刀工对决

题目：???????

思路分析：

我们可以把ab都分解为一个3和5的某幂次

代码实现：

int main()
{
    int n;
    cin>>n;
    ll ans=0;
    bool flag=true;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        int cnta=0;
        int cntb=0;
        while(a%5==0)
        {
            a/=5;
            a*=3;
            cnta++;
        }
        while(b%5==0)
        {
            b/=5;
            b*=3;
            cntb++;
        }
        ans+=abs(cnta-cntb);
        cnta=0;
        cntb=0;
        while(a%3==0)
        {
            a/=3;
            cnta++;
        }
        while(b%3==0)
        {
            b/=3;
            cntb++;
        }
        ans+=abs(cntb-cnta);
        if(a!=b) flag=false;
    }
    if(flag) cout<<ans<<endl;
    else cout<<"-1"<<endl;
    return 0;
}