题目链接：CF1221A 2048 Game
题目大意
初始你有一个可重集合，其中每个数都是2的幂次，你可以执行若干次这样的操作：从可重集合中取出两个相等的数，把它们相加，然后插入到集合中，问：能否经过若干次操作使得集合中出现2048
解题思路
我们开一个数组st统计每个数出现的次数。由于全都是2的幂次，所以用一个数的log_2值来代表这个数即可。
我们从小的数往大的扫描（到1024为止）。假设当前扫描到2^i，那么我们令2_{i+1}的个数增加floor(\frac{st[i]}{2})（相当于尽可能地将较小数相加得到较大数）。操作完成后判断2048的个数是否大于0即可。
为什么正确？因为比2048大的数一定对答案没有贡献，无需考虑。而一个小于2048的数，必须要两两相加，最终才能到达2048。
代码
代码中的Log2函数相当于(int)log2，使用了“手动二分”的写法。
注意不要让数组越界了
// status: [Accepted]
// oj: [luogu]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int Log2(int val) {if(val<2147483648) { if(val<32768) { if(val<128) { if(val<8) { if(val<2) { return 0;} else {if(val<4) { return 1;} else {return 2;}}} else {if(val<32) { if(val<16) { return 3;} else {return 4;}} else {if(val<64) { return 5;} else {return 6;}}}} else {if(val<2048) { if(val<512) { if(val<256) { return 7;} else {return 8;}} else {if(val<1024) { return 9;} else {return 10;}}} else {if(val<8192) { if(val<4096) { return 11;} else {return 12;}} else {if(val<16384) { return 13;} else {return 14;}}}}} else {if(val<8388608) { if(val<524288) { if(val<131072) { if(val<65536) { return 15;} else {return 16;}} else {if(val<262144) { return 17;} else {return 18;}}} else {if(val<2097152) { if(val<1048576) { return 19;} else {return 20;}} else {if(val<4194304) { return 21;} else {return 22;}}}} else {if(val<134217728) { if(val<33554432) { if(val<16777216) { return 23;} else {return 24;}} else {if(val<67108864) { return 25;} else {return 26;}}} else {if(val<536870912) { if(val<268435456) { return 27;} else {return 28;}} else {if(val<1073741824) { return 29;} else {return 30;}}}}}} else {if(val<140737488355328) { if(val<549755813888) { if(val<34359738368) { if(val<8589934592) { if(val<4294967296) { return 31;} else {return 32;}} else {if(val<17179869184) { return 33;} else {return 34;}}} else {if(val<137438953472) { if(val<68719476736) { return 35;} else {return 36;}} else {if(val<274877906944) { return 37;} else {return 38;}}}} else {if(val<8796093022208) { if(val<2199023255552) { if(val<1099511627776) { return 39;} else {return 40;}} else {if(val<4398046511104) { return 41;} else {return 42;}}} else {if(val<35184372088832) { if(val<17592186044416) { return 43;} else {return 44;}} else {if(val<70368744177664) { return 45;} else {return 46;}}}}} else {if(val<36028797018963968) { if(val<2251799813685248) { if(val<562949953421312) { if(val<281474976710656) { return 47;} else {return 48;}} else {if(val<1125899906842624) { return 49;} else {return 50;}}} else {if(val<9007199254740992) { if(val<4503599627370496) { return 51;} else {return 52;}} else {if(val<18014398509481984) { return 53;} else {return 54;}}}} else {if(val<576460752303423488) { if(val<144115188075855872) { if(val<72057594037927936) { return 55;} else {return 56;}} else {if(val<288230376151711744) { return 57;} else {return 58;}}} else {if(val<2305843009213693952) { if(val<1152921504606846976) { return 59;} else {return 60;}} else {if(val<4611686018427387904) { return 61;} else {return 62;}}}}}}}
int st[31];
signed main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
for(int i=0;i<=11;i++) st[i] = 0;
int n;
cin>>n;
while(n--) {
int x;
cin>>x;
st[Log2(x)] ++;
}
for(int i=0;i<11;i++) {
st[i+1] += st[i]/2;
}
if(st[11]) cout<<"YES\n";
else cout<<"NO\n";
}
cout.flush();
}
评测记录：R24129136
Comments | NOTHING