队友知道我喜欢做构造题于是总是给我推各种构造。然而很不幸的是这是一道大水题。题目给了一种贪心的翻翻牌策略然后让你构造出一种方案使得恰好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}观察了一下n6,k10n 6,k 10n6,k10的样例以后发现不对可以尽可能的让一种牌翻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解得tk−n1t k - n 1tk−n1因此我们得到了通解构造{1,2,1,…,k−n1,k−n,k−n1,k−n2,k−n2,…,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−n1,k−n,k−n1,k−n2,k−n2,…,n,n}代码如下voidsolve(){intnread(),kread();vectorintans;if(kn||k2*n){puts(No);return;}puts(Yes);ans.push_back(1);for(inti2;ik-n1;i)ans.push_back(i),ans.push_back(i-1);ans.push_back(k-n1);for(intik-n2;in;i)ans.push_back(i),ans.push_back(i);for(autov:ans)printf(%d ,v);puts();}