题解：CF2201B Recollect Numbers

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

题目给了一种贪心的翻翻牌策略，然后让你构造出一种方案使得恰好 $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$，因此我们得到了通解构造：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

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 ("");
}