Codeforces Round #682 (Div. 2) B. Valerii Against Everyone (思维)
阅读原文时间:2023年07月08日阅读:4

  • 题意:给你一组数\(b\),对于每个\(b_i\),相对应的\(a_i=2^{b_i}\),问你是否能找出两个不相交的区间,使得两个区间的\(a_i\)的元素和相等.

  • 题解:对于任意一个\(2^k\),如果它只能由\(2^k\)相加得到的话,那么只能是他自己本身,或者这些\(2^k\)中含有相同元素,我们可以推一下,\(1,2,4,8,16,32,64\),\(8\)只能由自己或者\(4*2\),\(2*4\)得来,所以某个\(2^k\)必须出现多次,所以只要判断是否有相同元素即可.

  • 代码:

    int t;
    int n;
    int a[N];
    map<int,int> mp;
    
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        cin>>t;
        while(t--){
            cin>>n;
            rep(i,1,n) cin>>a[i];
            mp.clear();
            bool flag=false;
            rep(i,1,n){
                if(mp[a[i]]) {flag=true;break;}
                mp[a[i]]++;
            }
            if(flag) cout<<"YES\n";
            else cout<<"NO\n";
        }
    return 0;
    }