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

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

[A. Divide it!][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!~][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!~][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;
     }

[A. Divide it]: https://codeforces.com/contest/1176/problem/A
[B. Merge it]: https://codeforces.com/contest/1176/problem/B
[C. Lose it]: https://codeforces.com/contest/1176/problem/C