题解：P14570 「LAOI-11」Metamorphosism

题意

给定正整数

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

CPP

#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; // 结束 (｡･ω･｡)
}

题解：P14570 「LAOI-11」Metamorphosism

文章操作

题意

思路

Code

相关推荐

评论

题解：P14570 「LAOI-11」Metamorphosism