Codeforces Round #682 (Div. 2) B. Valerii Against Everyone (思维)

Codeforces Round #682 (Div. 2)  B. Valerii Against Everyone  (思维)

  • 题意:给你一组数\(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;
    }
    
上一篇:Seventh season fourteenth episode,everyone turned thirty??????


下一篇:Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) 题解