P8942 Digital Fortress 题解

· · 题解

唯一打出正解的题，还是得写篇东西纪念一下（主要是这场比赛是拉满比赛分的关键一场）。

题意

求构造一个长度为 n 的序列，每个数都在 [1,m] 之间，使得前缀、后缀异或和均递增。

Solution

这个题非常像 CF 的 A，构造的签到题。

首先有个贪心的结论，只要我们能够知道最大数的最小值，就能快速判断是否能构造。

考虑异或和持续变大是什么情况。每次异或和若想变大，显然需要将高位的某一位变成 1。以此类推，n 个数的异或和要想递增，至少需要有 n 位是 1，这个结果肯定是最小的。

考虑当刚好 n 位是 1，即前 n 个数的异或和为 2^n-1 时，每个数是什么。显然每一个数只能够是 2^i，因为一共只有 n 位是 1，所以每个数都只能够有一位是 1。

题目要求递增，我们就令 a_i=2^{i-1}，注意 1=2^0，也是符合条件的。

由于异或和只是一个 0,1 变换的过程，而且按上面的构造，1 之间的位置是不影响的，所以只要前缀和递增，后缀和显然也是递增的。

判断无解也很简单，如果 2^{n-1}>m，就无解了。

但是注意这东西似乎不能用位运算，2^{100000} 会炸掉，有两种解决方案：一种是使用 __lg 函数反向判断（考场用的 log2，hack 添加之后就丢精了），即 \log_2m+1 和 n 的大小关系；第二种是特判，如果 n>63 必定无解（m\leq 2^{63}-1）。

就喜欢 T1 放这种诈骗了又好像没有诈骗的题目 qwq。

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

int T, n;
long long m;

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%lld", &n, &m);
        if(__lg(m) + 1 >= n){
            printf("Yes\n");
            for(int i=0;i<n;i++)
                printf("%lld ", (1ll << i));
            printf("\n");
        }
        else
            printf("No\n");
    }
    return 0;
}