题解：CF2201B Recollect Numbers

SUNCHAOYI · 2026-03-07 17:56:18 · 题解

队友知道我喜欢做构造题，于是总是给我推各种构造。然而很不幸的是，这是一道大水题。

题目给了一种贪心的翻翻牌策略，然后让你构造出一种方案使得恰好 k 次翻完。

首先先无脑地确定下界。显然最优情况下为 \{1,1,2,2,\ldots,n,n\}，直接每种牌翻一次即可完成。难点在于上界的确定，一开始以为是 n + \lceil \frac{n}{2} \rceil，构造为 \{1,2,\ldots,n,1,2,\ldots,n\}，观察了一下 n = 6,k = 10 的样例以后发现不对，可以尽可能的让一种牌翻 2 次来浪费次数。

【结论 1】 一张牌最多只会被翻两次，并且第二次被翻到时一定会被消掉。

根据贪心策略，一张牌在第一次翻到后就会被记住，因此第二次去翻它时一定进行消除操作。

【结论 2】 上界应为 2 \times n - 1。

一次翻牌操作如果没有消去任何的牌，那么就会使得数字为 x,y 的牌被记住。假设 x 未出现过，y 出现过，那么就需要额外花费一次翻牌的机会来消去 y。而初始时不会出现这种情况，因此一次翻牌会消去一种牌或者记住这两张牌所对应的数字。因此上界为 2 \times n - 1，构造为 \{1,2,1,3,2,\ldots,n,n - 1,n\}。

因此综上所述，k \in [n,2 \times n - 1] 时有解。结合两种构造方法，我们让前 t 种牌贴近上界构造，而后 n - t 种能贴近下界构造，于是需要翻牌的次数为 2t - 1 + (n - t) = k 解得 t = k - n + 1，因此我们得到了通解构造：

代码如下：

void solve ()
{
    int n = read (),k = read ();
    vector <int> ans;
    if (k < n || k >= 2 * n) {puts ("No");return;}
    puts ("Yes");
    ans.push_back (1);
    for (int i = 2;i <= k - n + 1;++i) ans.push_back (i),ans.push_back (i - 1);
    ans.push_back (k - n + 1);
    for (int i = k - n + 2;i <= n;++i) ans.push_back (i),ans.push_back (i);
    for (auto v : ans) printf ("%d ",v);
    puts ("");
}