Problem

Luogu

Codeforces

Solution

给你一串数字，这串数字是由一个很大的数字分割出来的，然后你需要检查是否合法

分割方式就是对半分，如果不能对半分，那么一个向上取整，一个向下取整

你就会想着如何把数字合起来，如果没法合起来就是不合法

然而这种做法有个问题

1 1 1 1 1 1

类似这个串，就可以 ban 掉这个做法了

所以我们换种思路

一个数如果是奇数，那么可以分成两个数，而这两个数加起来就是原来的数，下面证一下：

如果是奇数，那么 \lceil \frac {w}{2} \rceil + \lfloor \frac {w}{2} \rfloor = \frac {w+1}{2} + \frac {w-1}{2} = w

如果是偶数，那么 \lceil \frac {w}{2} \rceil + \lfloor \frac {w}{2} \rfloor = \frac {w}{2} + \frac {w}{2} = w

所以我们将所有的数字加起来，然后一个一个分

由于序列会很多种情况，我们需要来 模拟 他的思路分割

我的串是 q ，目标串是 p ，用 maxx(x) 代表某个 x 串中最大的数

如果 maxx(q) > maxx(p) ，那就是我这个最大的数还需要再细分，对半分完后还需要放回我自己的串中

如果 maxx(q) = maxx(p) ，那么这两个串中最大的数就是匹配好的数字，我们把他们从两个串中拿开

如果 maxx(q) < maxx(p) ，那么我就分不到他的情况了，连我最大的数都比目标串小了，再分就更小，剩下的数怎么细分也无济于事

我们要怎么 高效 寻找这个最大的数字呢

multiset 和 priority queue 都是比较好的选择

我这里用的是 优先队列

Code

#include <bits/stdc++.h>
using namespace std;

#define il inline
#define INF 0x3f3f3f3f
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;

#define int ll

priority_queue<int> q, p;

int t, n, temp, tot;

bool flag;

signed main()
{
    scanf("%lld", &t);
    for (int kkz = 0; kkz < t; kkz++)
    {
        tot = 0;
        flag = true;
        while (!q.empty()) q.pop();
        while (!p.empty()) p.pop();
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &temp);
            tot += temp;
            q.push(temp);
        }
        p.push(tot);
        while (!q.empty() && !p.empty() && flag)
        {
            if (q.top() == p.top()) q.pop(), p.pop();
            if (q.top() > p.top()) flag = false;
            if (q.top() < p.top())
            {
                p.push(p.top() % 2 == 0 ? p.top() / 2 : p.top() / 2);
                p.push(p.top() % 2 == 0 ? p.top() / 2 : p.top() / 2 + 1);
                p.pop();
            }
        }
        if (flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}