P9345 夕阳西下几时回【构造】

Nostopathy · 2025-11-28 21:55:37 · 题解

首先本题是道结论题。

先来一个结论：b 数组中最多有 \lfloor \frac{n}{2} \rfloor 个不同的数字。

::::info[证明]{open} 由于 \forall a_i \in [1,n] 且不重复，a 数组长度为 n，因此对于 \forall a_i、\forall a_j GCD 最大为 \lfloor \frac{n}{2} \rfloor，如果 GCD 超过 \lfloor \frac{n}{2} \rfloor 则一定不满足 \forall a_i \in [1,n]。证毕。 ::::

那么第一问就解决啦！判断是否 k \leq \lfloor \frac{n}{2} \rfloor 即可。

接下来，如何构造？

我们先考虑最多的情况，需要有 \lfloor \frac{n}{2} \rfloor 个不同的数字。由于 GCD 是取相邻的两数，我们肯定要尽可能的使一个数和它的倍数相邻。比如 1 2 4 3 6 这样。

但是这样可能会出现重复的 GCD。我们可以先输出 2 的整数次幂，然后枚举奇数的倍数进行构造。这样就实现去重啦！（显然奇数的倍数不会与 2 的整数次幂相等，从不同的奇数开始乘 2 也不会相等。）

接下来考虑减少到 k 个不同数字，根据上述我们只需要枚举到 2k 就可以了，后面的区间 [2k,n] 输出相邻的数字即可，因为它们的 GCD 都是 1，不影响答案。

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
int t, n, k;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> t;
    while(t --){
        cin >> n >> k;
        if(k > n / 2){
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
        cout << "1 ";
        for(int i = n; i >= 2 * k + 1; -- i) cout << i << " ";
        for(int i = 2; i <= 2 * k; i *= 2) cout << i << " ";
        for(int i = 3; i <= 2 * k; i += 2) for(int j = i; j <= 2 * k; j *= 2) cout << j << " ";
        cout << "\n"; // 多测不换行，爆零两行泪
    }
    return 0;
}

::::

感谢大家！