目录
C. Factorials and Powers of Two
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;
}
}