Codeforces Round #565 (Div. 3) （ A B C）解题报告-蒲公英云

Codeforces Round #565 (Div. 3) （ A B C）解题报告

你的名字 2022-01-20 11:29 281阅读 0赞

A. Divide it!

题意：给你一个n，如果n可以被2整除，乘上1/2; 如果n可以被3整除，乘上2/3;如果n可以被5整除，乘上4/5; 问最小多少步处理n可以到1。

思路：
首先判断n可不可以变成1，然后从减少最多的开始操作，直到n=1结束。

AC代码：

#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
const int eps=1e-8;
int main()
{
    ios::sync_with_stdio(false);
    ll n; 
    cin>>n;
    while(n--)
    {
        ll a;
        cin>>a;
        ll ans=a;
        ll num1;
        while(ans%2==0)    
            ans/=2;
        while(ans%3==0)    
            ans/=3;
        while(ans%5==0)    
            ans/=5;
        //cout<<ans<<endl;
        if(a==1)
            cout<<"0"<<endl;
        else if(ans>1)
            cout<<"-1"<<endl;
        else
        {
            ll sum=0;
            for(int i=1;i<10000000000;i++)
            {
                if(a%2==0)
                {
                    sum++;
                    a=a/2;
                }
                else if(a%3==0)
                {
                    sum++;
                    a=a/3*2;
                }
                else if(a%5==0)
                {
                    sum++;
                    a=a/5*4;
                }
                if(a==1)
                    break;
            }
            cout<<sum<<endl;
        }
    } 
    return 0;
 }

B. Merge it!~

题意：给你有一个数列，可以合并任意两个，问你最后有多少个数可以被3整除。

思路：输入的时候先把3的倍数找出来，然后遍历一边数组，统计一下所有数对3取余的个数为也就是取余完1的个数，2的个数，0的个数，只需考虑1和2的个数，3是1+2得来的所以去min（1的个数，2的个数），然后3还可以被3个1和3个2得来，再用剩下1和2的个数除以3，所有的加起来就是答案。

AC代码：

#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
const int eps=1e-8;
ll a[mmax],book[mmax];
int main()
{
    ios::sync_with_stdio(false);
    ll t; 
    cin>>t;
    while(t--)
    {
        memset(book,0,sizeof(book));
        ll n;
        cin>>n;
        ll sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(a[i]%3==0)
                sum++;
        }
        for(int i=0;i<n;i++)
        {
            book[a[i]%3]++;
        }
        ll ans=min(book[1],book[2]);
        book[1]-=ans;
        book[2]-=ans;
        ll ans1=book[1]/3;
        ll ans2=book[2]/3;
        cout<<sum+ans+ans1+ans2<<endl;
    }
    return 0;
 }

C. Lose it!~

题意：有一个完美数组 4 8 15 16 23 42 ，任意给你一个数组，问删除多少个才是完美数组（符合完美数组的条件我就不说了，题目里有）。

思路：（greedy）
其实就是问你数组里最多有多少个完美数组（完美数组的个数和顺序不能颠倒），
最后用数组长度 - 完美数组的个数*6 就是答案。
首先怎么看4 8 15 16 23 42 的顺序的，想一个，每个数参照前一个数永远是最优的(我自己总结的)，第一个4不用看，8是根据4的，15是根据8的…，for循环遍历一边数组，如果是4，4的个数增加1，如果是8，看8的个数是不是小于4，如果是，说明8正好可以用一个4来构成一个完美数组，如果不是，说明前面没有4来跟8构成完美数组的前两位，以此类推，一直遍历到最后，最后42的个数就是整个数组里面完美数组的个数。

AC代码：

#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
const int eps=1e-8;
ll a[mmax],book[mmax];
int main()
{
    ios::sync_with_stdio(false);
    ll n;
    while(cin>>n)
    {
        memset(book,0,sizeof(book));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]==4)
                book[4]++;
            else if(a[i]==8)
            {
                if(book[8]<book[4])
                    book[8]++;
            }
            else if(a[i]==15)
            {
                if(book[15]<book[8])
                    book[15]++;
            }
            else if(a[i]==16)
            {
                if(book[16]<book[15])
                    book[16]++;
            }
            else if(a[i]==23)
            {
                if(book[23]<book[16])
                    book[23]++;
            }
            else if(a[i]==42)
            {
                if(book[42]<book[23])
                    book[42]++;
            }
        }
        cout<<n-book[42]*6<<endl;        
    }
    return 0;
 }