A. Square Counting
题意：
给出一个长度为n的数组和数组的和S，构成数组的数要么是从0~n，要么是n*n，求n*n的个数最多是多少个
思路：
默认全是(n*n)，那么算个数就直接(n*n)/s
#include<bits/stdc++.h> using namespace std; int main() { long long n,i,j,t,s; cin>>t; while(t--) { cin>>n>>s; //s/(n*n) cout<<s/(n*n)<<endl; } return 0; }
B. Quality vs Quantity
题意：
给出一个长度为n的数组，现在进行染色，可以选择染为红色，蓝色或者不染，问是否可以染色完数组后染色数量少的一方，相加的值大于染色数量多的一方
思路：
可以通过前缀和算，我是排序之后，双指针一个从左边取，一个从右边取。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+1000; int a[maxn], b[maxn]; int main() { int n,i,j,t; cin>>t; while(t--) { cin>>n; for(i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); long long ans1=0,ans2=0,flag=0; vector<int >b1,b2; b2.push_back(a[n-1]); ans2+=a[n-1]; j=n-2; for(i=0;i<n;i++){ ans1+=a[i]; b1.push_back(a[i]); while(ans2<=ans1&&j>i) { ans2+=a[j]; b2.push_back(a[j]); j--; } if(ans2>ans1&&b2.size()<b1.size()) { flag=1; } } if(flag==0){ cout<<"No"<<endl; }else { cout<<"Yes"<<endl; } } return 0; } /* 我要选两组数，且第一组的数量小于第二组并且第一组的和大于第二组 第一组肯定先选最大的a[n-1]，第二组选两个小的，如果第二组比第一组大，再双指针不停选，总和2e5 应该不会t，处理好就是O（n）的复杂度了 7 3 1 2 3 5 2 8 6 3 1 4 3 5 4 2 5 1000000000 1000000000 1000000000 1000000000 1000000000 5 3 5 6 8 7 */
C. Factorials and Powers of Two
题意：
问一个数n能否全部由2的次幂或者n的阶乘构成，且构成n的数都得不相同
思路：
首先d!如果是小于1e12，那么最多只会有15种，又因为构成n的阶乘数和2的次方的数必须是不相同的
所以可以先枚举n的阶乘，这里使用状态压缩，因为每种数都有选择和不选两种方案，又因为最多就16个数
所以应该是有2^16次方种方案，再用位运算算出取1的时候就是选这个数，最后加起来如果是小于等于n的
再去求2的n次方，这个容易求直接使用位运算算剩下的数字里转为成2进制1的个数即可
最后把个数加起来取最小值
#include<cstdio> #include<algorithm> using namespace std; int t; long long n,fac[20]; int BitCount(long long x) { int res=0; while(x) { res+=(x&1); x>>=1; } return res; } int main() { fac[0]=1; for(int i=1;i<=15;i++) fac[i]=fac[i-1]*i; int tot=(1<<16); scanf("%d",&t); while(t--) { scanf("%lld",&n); int ans=1000; for(int i=0;i<tot;i++) { long long tmp=0; int cnt=0; for(int j=0;j<=15;j++) { if(i & (1<<j)) { tmp+=fac[j]; cnt++; } } if(tmp<=n) ans=min(ans,BitCount(n-tmp) + cnt); } printf("%d\n",ans); } }
