[洛谷题解] CF1221A 2048 Game

发布于 2019-09-20  326 次阅读


题目链接: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


undefined