BGN83 完美异或

思路

题目要求构造一个长度为 的非递减数组，使得所有元素的异或和是 的因子。如果无法构造就输出 -1。

先想想，有没有什么万能的构造方法？

关键观察

我们可以用大量的 1 来"填充"数组，然后在末尾放一个较大的数来调整异或和。

具体来说：前 个元素都是 1，最后一个元素设为 。数组自然是非递减的（只要 ）。

那异或和是多少呢？ 个 1 异或在一起：

  • 如果 是偶数（即 是奇数）：异或和为 0，总异或和就是
  • 如果 是奇数（即 是偶数）：异或和为 1，总异或和就是

分情况构造

为奇数时： 前面 个 1 异或得 0，令 ，总异或和 ，而 ，完美。

为偶数时： 前面 个 1 异或得 1，令 。因为 是偶数，二进制最低位为 0，所以 的最低位为 1。那 就是把最低位从 1 翻成 0，结果恰好是 。总异或和 ，，同样完美。

来验证一下样例：

  • ：，异或和 ， ✓
  • ：，异或和 ， ✓
  • ：，异或和 ， ✓

所以答案永远存在，不需要输出 -1。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        if(n==1){
            printf("1\n");
        } else if(n%2==1){
            for(int i=0;i<n-1;i++) printf("1 ");
            printf("%d\n",n);
        } else {
            for(int i=0;i<n-1;i++) printf("1 ");
            printf("%d\n",n+1);
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            if (n == 1) {
                sb.append("1\n");
            } else if (n % 2 == 1) {
                for (int i = 0; i < n - 1; i++) sb.append("1 ");
                sb.append(n).append("\n");
            } else {
                for (int i = 0; i < n - 1; i++) sb.append("1 ");
                sb.append(n + 1).append("\n");
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    n = int(input())
    if n == 1:
        out.append("1")
    elif n % 2 == 1:
        out.append(' '.join(['1'] * (n - 1)) + ' ' + str(n))
    else:
        out.append(' '.join(['1'] * (n - 1)) + ' ' + str(n + 1))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const res = [];
    for (let i = 0; i < t; i++) {
        const n = parseInt(lines[idx++]);
        if (n === 1) {
            res.push("1");
        } else if (n % 2 === 1) {
            res.push(Array(n - 1).fill('1').join(' ') + ' ' + n);
        } else {
            res.push(Array(n - 1).fill('1').join(' ') + ' ' + (n + 1));
        }
    }
    console.log(res.join('\n'));
});

复杂度分析

  • 时间复杂度：，每组测试用例输出 个数。
  • 空间复杂度：，不需要额外存储数组（Java 的 StringBuilder 除外）。