目录
C. Factorials and Powers of Two
杂谈
不得不说这场 cf 的时间真的很阴间，在菜和状态差的双重影响下毫无疑问直接掉大分。
这场的A题特别友好，属于看完题直接能签的那种；B题上来就想了个假思路，连WA两发，意识到问题之后改完思路，但没完全改完代码，又草率地交了，理所当然的又WA了一发，最后调整完索性算是过了；C题上来又想了个分情况的假算法，但后来发现情况分不完（<@_@>），在结束前半个小时发现好像直接暴力枚举也T不了，可惜最后还是没写出来。
赛后看了下同学的暴力代码，二进制枚举，这才回想起来寒假集训营也有一题用二进制枚举不同的组合，没想到这才补完题没多久就忘了（看来还是不够努力－O－）。
A. Square Counting
题目大意：定义 n + 1 长度的序列中每个数是 [0, n) 或者是 ，序列所有元素的和为 s，求给定 n 和 s 的情况下，序列中是
的数的个数。（其中 s 是一定合法的值）
解题思路：因为 s 一定是合法值，那么如果 s 是大于等于??的数，那么一定有?
?个?
?的数；如果 s 小于?
，那么一定没有?
?这样的数。因此整合一下直接输出?
就好了。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
ll n, s;
cin >> n >> s;
cout << s / (n * n) << endl;
}
return 0;
}B. Quality vs Quantity
题目大意：判断给定的序列是否满足涂红色数的值之和大于涂蓝色数的值之和，且涂红色数的数量小于涂蓝色数的数量。其中涂色可以任意选择。
解题思路：对序列排个序，从最小的两个数的和开始与最大的一个数进行比较，每次左右各加上一个数，只要有一种状态下左边的和比右边的和小，那么这种状态就满足条件，就输出YES，如果每一种状态都不满足，就输出NO。
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
ll a[N];
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
ll sum1 = a[1], sum2 = 0;
int flag = 0;
for(int i = 2, j = n; i < j; i++, j--){
sum1 += a[i];
sum2 += a[j];
if(sum1 < sum2){
flag = 1;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}C. Factorials and Powers of Two
题目大意：定义 powerful number 为??或?
，求给定的数中能分成最少的不重复的 powerful number 的数之和的个数，如果不能分成若干个 powerful number 之和，输出 -1。
解题思路：首先打表发现阶乘要小于 ，那么最多只会到?
，那么可以预处理出前 15 个数的阶乘。然后通过二进制枚举的方式选择不同的阶乘组合进行求和 sum，然后在剩下的 n - sum 的值中找二进制中的 1 的个数就是剩下的还需要多少 2 的次幂的数，每种组合求出所需的 power number 的个数最后取最小值就是答案了。（由于?
?到?
?可以表示任意一个
?以内的数，因此一个数一定能够分解成若干个不同的 powerful number 之和）
AC代码：
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
ll n, sum, cnt, ans;
ll fac[15 + 1];
void init(){
fac[0] = 1;
for(int i = 1; i <= 15; i++){
fac[i] = fac[i - 1] * i;
}
}
int main(){
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
init();
int t;
cin >> t;
while(t--){
cin >> n;
ans = INF;
for(int i = 0; i < (1 << 15); i++){
sum = 0, cnt = 0;
for(int j = 0; j <= 15; j++){
if((i >> j) & 1){
sum += fac[j];
cnt++;
}
}
ll res = n - sum;
if(res >= 0){
while(res){
if(res & 1) cnt++;
res >>= 1;
}
ans = min(ans, cnt);
}
}
cout << ans << endl;
}
return 0;
}