P9033「KDOI-04」XOR Sum 题解

题目链接

传送门

题意简述

构造一个长度为 \(n\)，值域为 \([0,m]\) 的异或和为 \(k\) 的序列，如果不存在则输出 \(-1\)。

题目分析

首先很容易想到，当 \(k \le m\) 的时候，我们仅需要输出一个 \(k\) 剩下的位置全部填 \(0\) 即可。

而当 \(k > m\) 时，我们至少需要两个数，因此在此时判断 \(n\) 是否等于 \(1\)，若不等于 \(1\)，根据异或不进位原理，我们还需判断 \(k\) 和 \(m\) 的二进制位数关系。设 \(l_k,l_m\) 分别为 \(k,m\) 的二进制位数。

• 若 \(l_m \le l_k\) 则无解。
• 反之，我们可以让一个数是 \(2^{l_k}\)，此时再构造出 \(k - 2^{l_k}\) 即可，可以证明 \(k - 2^{l_k} \le m\) 因此只需两个数 \(2^{l_k},k-2^{l_k}\) 即可，剩余部位补零。

Codes

//author: yuhang-ren
#include <bits/stdc++.h>
using namespace std;
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
    {
        write_(x/10);
    }
    putchar(x%10+'0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int T,n,m,k;
signed main()
{
    #if _clang_
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif 
    read(T);
    for(int t = 1;t<=T;t++)
    {
        read(n),read(k),read(m);
        if(k <= m)
        {
            writesp(k);
            for(int i = 2;i<=n;i++)
            {
                writesp(0);
            }
            puts("");
            continue;
        }
        else
        {
            int l_k = 0,l_m = 0;
            int k_ = k;//k后面还需要用到，所以用k_代替k进行运算。
            for(;k_;k_>>=1)
            {
                l_k++;
            }
            for(;m;m>>=1)
            {
                l_m++;
            }
            if(n == 1)
            {
                writeln(-1);
                continue;
            }
            if(l_k > l_m)
            {
                writeln(-1);
                continue;
            }
            writesp((1<<(l_k-1)));
            writesp((k - (1<<(l_k-1))));
            for(int i = 3;i<=n;i++)
            {
                writesp(0);
            }
            puts("");
        }
    }
    return 0;
}