P8942 Digital Fortress 题解

JackMerryYoung · 2023-01-15 18:43:29 · 题解

前言

挺简单一道结论题。

正文

先瞎猜一波：输出 2 的 K 次方即为答案。

那么这个结论咋来的？我们来模拟一个小样例：

先加入 1，异或和为 1，再加入 3，异或和为 2，再加入 4，异或和为 6。

若要仍满足条件，必须加入 9。

但是我们又更好的一条路可走：选择加入 1 \ 2 \ 4 \ 8.

这是个贪心的思想，你要尽量在满足条件的情况下最小。

于是我们先加入 1 \ 2. 这时候想要最优必须加入 4。

发现了这样子考虑的话之后加入的都是 2 的 K 次方，那么直接判断是否合法并输出即可。

代码

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

#define ll unsigned long long
#define rint register int

int T;
__int128_t N, M;

__int128_t fastread()
{
    __int128_t res = 0, fh = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') fh = -fh;
        ch = getchar();
    }

    while(ch >= '0' && ch <= '9')
    {
        res = res * 10 + ch - '0';
        ch = getchar();
    }

    return res;
}

void fastwrite(__int128_t x)
{
    string str = "";
    while(x)
    {
        str += char((x % 10) ^ 48);
        x /= 10;
    }

    str.reserve();
    cout << str << endl;
}

signed main()
{
    cin >> T;
    while(T --)
    {
        N = fastread(), M = fastread();
        if(N > 63 || (1ll << (N - 1)) > M) 
        {
            puts("No");
        }
        else
        {
            puts("Yes");
            for(int i = 1; i <= N; ++ i)
            {
                cout << (1ll << (i - 1)) << ' ';
            }

            puts("");
        }
    }
    return 0;
}

后言

注意是 N > 63，之前被 Hack 了。