Lotuses's Blog

CF1654C Solution

  • 1012 字
  1. 1. Solution

Solution

暴 力 是不可能不打的。

这道题目有两种暴力方法。

一种从合并角度看，将相邻的两个数依次合并，看是否能合并完成。

但我选择的是更直观的暴力打法。

将总和依次分解，想到每一次的分解结果要是有对应的数字就消掉，剩下的分解，那么用 map 维护当前还需要处理的对应数字，一个 bfs 可以解决。

请注意，若分解个数大于 次后，必然是有些数字分解不了，那么这时候直接 return，以减小空间 & 时间。如果不处理会 TLE。

空间 ，时间 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum;
map<int,int> fk;
queue<int>q;

bool bfs()
{
    while(!q.empty()) q.pop();
    q.push(sum);
    while(!q.empty())
    {
        int lst=q.front();q.pop();
        if(fk[lst]) fk[lst]--;
        else
        {
            if(lst==1||q.size()>2*n) return false;
            int hl=lst/2,hr=lst/2+(lst%2);
            q.push(hl),q.push(hr);
        }
    }
    return true;
}

signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int k;sum=0;fk.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>k,sum+=k,fk[k]++;
        if(bfs()) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可