阿里国际笔试阿里国际笔试题 0428

笔试时间：2025年04月28日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

Tk 有一个长度为 n编号为 1\sim n 且仅包含 0 与 1 的数组。设该数组为 a。现在给定一个正整数 k。你的任务是构造一个长度同为 n 的新数组 b，使得对于任意的下标 i，都有

$a_i \oplus b_i \oplus b_{i+1} \oplus \cdots \oplus b_{\min(i+k-1,n)} = 0$

输入描述

第一行输入两个正整数 n, k ，其中 n 表示数组 a 的长度，满足 1 ≤ n ≤ 2×10^6 ；k 表示参数，满足 1 ≤ k ≤ n 。

第二行输入 n 个整数 a₁, a₂, …, aₙ ，其中每个 aᵢ ∈ {0, 1} 。

输出描述

输出一行 n 个数字，表示你构造的数组 b。

样例输入

5 2

1 1 0 1 1

样例输出

0 1 0 0 1

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> b(n, 0);
    int t = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i + k < n) {
            t ^= b[i + k];
        }
        b[i] = t ^ a[i];
        t ^= b[i];
    }
    for (int i = 0; i < n; i++) {
        cout << b[i] << (i == n - 1 ? "\n" : " ");
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) {
        FastReader scanner = new FastReader();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        solve(n, k, a);
    }

    private static void solve(int n, int k, int[] a) {
        int[] b = new int[n];
        int t = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i + k < n) {
                t ^= b[i + k];
            }
            b[i] = t ^ a[i];
            t ^= b[i];
        }
        StringBuilder sb = new StringBuilder();
        for (int num : b) {
            sb.append(num).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

import sys

input = lambda: sys.stdin.readline().rstrip()
sint = lambda: int(input())
mint = lambda: map(int, input().split())
ints = lambda: list(map(int, input().split()))

def solve() -> None:
    n, k = mint()
    a = ints()
    b = [0] * n
    t = 0
    for i in range(n-1, -1, -1):
        if i + k < n:
            t ^= b[i + k]
        b[i] = t ^ a[i]
        t ^= b[i]
    print(*b)

if __name__ == '__main__':
    solve()