题解 P9033 「KDOI-04」XOR Sum

JuRuoOIer · 2023-02-04 15:18:58 · 题解

题解 P9033 「KDOI-04」XOR Sum

UPD：介绍异或的部分及数据范围部分均按要求进行了调整。

好吧又是赛时唯一 AC 的题目……

Part1 题意

原题传送门

• 给定 n,m,k，要求构造一个非负整数序列，长度为 n，所有项均不超过 m，且异或和为 k。

Part2 思路

2-1 关于异或

首先大家要知道异或是什么。

异或有一个外号，叫做不进位加法，因为 0\ \text{xor}\ 0 = 0，1\ \text{xor}\ 1=0，0\ \text{xor}\ 1=1（0+0 和 1+1 二进制最后一位均为 0）。

于是我们得出：任何数异或 0 等于其本身。这条性质记好了，后面会用到。

2-2 判无解、凑答案

接着我们看怎么得到 k。

既然 k 只能通过不超过 m 的数字异或得到，所以 k 的二进制位数不能超过 m 的二进制位数（显然异或没法变出新的位），即 \lceil\log_2k\rceil \le \lceil\log_2m\rceil，否则无解。

接下来分两种情况考虑：

• 当 k \le m 时，只需要第一项赋值为 k，其余项均为 0 即可（还记得 2-1 中的性质吗？）。
• 当 k > m 时，又由于 \lceil\log_2k\rceil \le \lceil\log_2m\rceil，所以 k 和 m 位数相同。也就是说，k 与 m 二进制下最高位是同一位且都是 1。
  • 然后我们把 k 最高位上的 1 去掉，此时 k 一定小于 m（因为位数减少了），一项就可以完成。
  • 而刚才去掉的 1 实际上就是 100...00（长度同 k,m），一定不会超过 m，也需要一项完成。
  • 由于是同一个数字拆出来的，所以它们不可能在同一个位置均为 1。也就是说，它们两个的异或等于它们的和 k。

于是 k>m 的情况就解决了：n=1 无解，否则将 k 像上面那样分成两份，后面填 0 即可。

Part3 代码

注释在代码里啦！

#include<bits/stdc++.h>
//此处省略快读快输，见我的主页
//它将这个程序优化了约 4ms 
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
using namespace std;
ll t,n,k,m; //意义如题面 
ll log2(ll x){//用不断除以 2 的方式求二进制长度（仅比转换成二进制少了取余，因此很明显正确） 
    ll ans=0;
    while(x){
        ans++;
        x/=2;
    }
    return ans;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k>>m;
        if(log2(m)<log2(k)){//m 的二进制长度小于 k，无解 
            cout<<"-1\n";
        }
        else if(m<k){//m<k 的情况，见 Part2-2 
            if(n==1)cout<<"-1\n";//一项不够，无解 
            else{
                cout<<(1ll<<log2(k)-1)<<' '<<k-(1ll<<log2(k)-1);//左移，1<<k 结果为 2^k 
                for(int i=0;i<n-2;i++){//补 0 
                    cout<<" 0";
                }
                cout<<endl;
            }
        }
        else{
            cout<<k;
            for(int i=0;i<n-1;i++){//补 0 
                cout<<" 0";
            }
            cout<<endl;
        }
    }
    return 0;
}