题解：P14570 「LAOI-11」Metamorphosism

UNNN · 2025-11-22 21:31:06 · 题解

题意

给定正整数 n 和 m，构造一个正整数序列 a，使得序列中各数互不相同且都不超过 m，同时满足：不存在三个不同的下标 i, j, k \in [1, n]，满足：

• a_i + a_j = a_k
• a_i \times a_j = a_k
• a_i \oplus a_j = a_k

  上述等式的任意一种。

思路

我们可以从数的奇偶性下手。

对于加法运算，显然存在奇奇得偶，奇偶得奇，偶偶得偶。

对于异或运算，由于奇数二进制结尾为 1，偶数二进制结尾为 0，所以奇偶性相同的两数异或后得到偶数，不同的异或后得到奇数。

因此，我们保证序列中全是奇数即可。因为两奇数无论相加还是相异或都会得到偶数，而序列中又不存在偶数，因此加法和异或这两个等式不会出现在序列中。

如果我们从 1 开始从小到大枚举所有奇数，那么显然有个问题。举个例子，对于数字 15，它可以写作两个小于它的两个奇数相乘的结果，即 3 \times 5 = 15。因此从小到大枚举会造成很多麻烦。

所以，我们不妨从 m 开始从大到小枚举所有奇数，这样就会保证在 n 约束下 m 可取值的范围内，不会出现两个奇数相乘得到序列中奇数的情况。

Code

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, cnt = 0;
int main()
{
    scanf("%d%d", &n, &m);
    m = m - !(m & 1); // 由于从大到小枚举奇数，m 可能为偶数，所以起点要保证 m 是奇数。
    for(int i = m;i >= 1;i = i - 2){
        if(cnt == n) break; // 枚举够 n 个数。
        printf("%d ", i);
        cnt++;
    }
    return 0; // 结束 (｡･ω･｡)
}