题解：CF2201B Recollect Numbers

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

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

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

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

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

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

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

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

{1,2,1,…,k−n+1,k−n,k−n+1,k−n+2,k−n+2,…,n,n} \color{black}\{\color{blue}{1,2,1,\ldots,k - n + 1,k - n,k - n + 1}\color{black}{,}\color{red}{k - n + 2,k - n + 2,\ldots,n,n}\color{black}\}{1,2,1,…,k−n+1,k−n,k−n+1,k−n+2,k−n+2,…,n,n}

代码如下：

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