C. Factorials and Powers of TwoC. Factorials and Powers of TwoB. Quality vs Quantity

68 阅读 0 评论 45 点赞

我是靠谱客的博主过时奇异果，最近开发中收集的这篇文章主要介绍C. Factorials and Powers of TwoC. Factorials and Powers of TwoB. Quality vs Quantity，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

C. Factorials and Powers of Two

一.原题描述

二.题意理解

三.题解

四.AC代码

B. Quality vs Quantity

一.原题描述

二.题解

三.AC代码

C. Factorials and Powers of Two

一.原题描述

二.题意理解

当一个数由阶乘或者2的幂次组成时，可以称它为强大的。

现在给一个正整数n，找到最小的个数k使得n是由k个阶乘或者2的幂次相加得到的强大的数。

或者说，没有这样的k。

三.题解

我们知道任何一个数都能被2的次幂所表示，因为当我们把一个数转换为2进制的时候，就是如此表示的，所以一个数如果只有2的次幂组成，那么k等于这个数2进制表示里1的个数。（很显然），现在我们要用阶乘来替换2的次幂。对于第i位阶乘，我们只有取或不取两种选择，用一个数记录下当前所取的阶乘和，然后每次选择完取或不取后，用原来的数减去当前阶乘和求其二进制表示中1的个数，再加上所取的阶乘个数，即为答案。因为这样，一个数就被表示成立若干2的幂次和，与若干阶乘和。

四.AC代码

#include<bits/stdc++.h>
using namespace std;
long long pre[100];
int x,y,ans;
int BitCount(long long n)
{
    int c =0 ; 
    while (n >0)
    {
        if((n &1) ==1) 
            ++c ;
        n >>=1 ;
    }
    return c ;
}
void dfs(int p,long long sum,long long fsum,int f){
	if(p>15) return;
	if(sum>=fsum)ans=min(ans,BitCount(sum-fsum)+f);
	dfs(p+1,sum,fsum+pre[p],f+1);
	dfs(p+1,sum,fsum,f);
}
int main(){
	int t;
	cin>>t;
	pre[1]=1;
	for(int i=2;pre[i]<=1e13;i++){
		pre[i]=pre[i-1]*i;
	}
	while(t--){
		ans=INT_MAX;
		long long n;
		cin>>n;
		dfs(3,n,0,0);
		if(ans==INT_MAX) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}

B. Quality vs Quantity

一.原题描述

二.题解

将原数组排序后，用两个指针分别从两端往中间移动，符合要求则跳出循环即可。

三种情况：

1.前端数组个数大于后端且和小于后端，符合题意。

2.前端和小于后端和，移动前指针，且累加。

3.前端和大于等于后端和，移动后指针，且累加。

三.AC代码

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
long long a[N]={0};
int main(){
	int _;
	cin>>_;
	while(_--){
		int n;
		long long pre=0,sum=0;
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+1+n);
		int cnt1=1;
		int cnt2=1;
		int i=1;
		int j=n;
		bool f=0;
		pre=a[i];
		sum=a[j];
		while(i<=j){
			if(cnt1>cnt2&&pre<sum){
				f=1;
				break;
			}
			else if(pre<sum){
				pre+=a[++i];
				cnt1++;
			}
			else if(pre>=sum){
				sum+=a[--j];
				cnt2++;
			}
		}
		if(f) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
}