Codeforces Round 1082 (Div. 2)-CF-1082-D. Recollect Numbers（太简单了，后悔花太多时间在C2上了）

题目大意

题目大意

有 $2n$ 张卡片排成一排，卡片上分别写着数字 $1, 1, 2, 2, \dots, n, n$，初始时全部背面朝上。

你将使用以下“贪心”策略来进行翻牌游戏，每回合精确地翻开两张卡片：

1. 如果你之前已经翻开过（且未被消除）两张数字相同的卡片，则直接翻开并消除它们。

2. 否则，翻开从左到右第一张从未被翻开过的卡片，设其数字为 $x$。

3. 接着，如果之前已经翻开过另一张数字为 $x$ 的卡片，则翻开并消除它。

4. 否则，再次翻开从左到右第一张从未被翻开过的卡片。如果这两张卡片数字相同，则消除；如果不同，则重新翻回背面。

给定 $n$ 和 $k$，要求构造一个 $1$ 到 $n$ 各出现两次的排列，使得上述算法恰好需要 $k$ 个回合才能消除所有卡片。如果存在这样的排列，输出 YES 并输出该排列；否则输出 NO。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试数据组数。
接下来每组数据包含一行，包含两个整数 $n$ 和 $k$（$1 \le n \le 3 \times 10^5$，$1 \le k \le 10^6$）。
保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

如果不存在满足条件的卡片排列，输出一行 NO。
如果存在，输出一行 YES，并在下一行输出 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$（$1 \le a_i \le n$），表示卡片上的数字排列。如果有多个合法的排列，输出任意一个即可。

样例输入

6
2 3
3 4
3 2
3 5
6 10
6 67

样例输出

YES
2 1 2 1
YES
1 3 2 2 1 3
NO
YES
1 2 3 1 2 3
YES
2 1 3 4 5 4 1 2 6 5 6 3
NO

样例解释

对于第一组样例，初始排列为 2 1 2 1，每回合的操作如下：

• 第 $1$ 回合：翻开第一张未翻过的卡片（数字 $2$），之前没有记录，接着翻开下一张未翻过的卡片（数字 $1$）。数字不同，翻回背面。此时记下前两张卡片的数字为 $2$ 和 $1$。

• 第 $2$ 回合：翻开第一张未翻过的卡片（第三张，数字 $2$），由于之前已经翻开过数字为 $2$ 的卡片（第一张），因此翻开第一张，两张卡片相同并消除。

• 第 $3$ 回合：翻开第一张未翻过的卡片（第四张，数字 $1$），由于之前已经翻开过数字为 $1$ 的卡片（第二张），因此翻开第二张，两张卡片相同并消除。
  游戏结束，共花费 $3$ 个回合。

对于第四组样例，初始排列为 1 2 3 1 2 3，每回合的操作如下：

• 第 $1$ 回合：翻开第一、第二张从未翻过的卡片，数字分别为 $1$ 和 $2$。数字不同，翻回背面。

• 第 $2$ 回合：翻开第三、第四张从未翻过的卡片，数字分别为 $3$ 和 $1$。数字不同，翻回背面。

• 第 $3$ 回合：此时发现之前翻开过（且未消除）的卡片中存在两张数字相同的卡片（第一张和第四张均为 $1$），触发规则第一条，直接翻开这两张卡片并消除。

• 第 $4$ 回合：没有两张已翻开且相同的卡片。翻开第五张卡片（数字 $2$），由于之前翻开过数字 $2$（第二张卡片），因此翻开第二张卡片并消除。

• 第 $5$ 回合：翻开第六张卡片（数字 $3$），由于之前翻开过数字 $3$（第三张卡片），因此翻开第三张卡片并消除。
  游戏结束，算法恰好在 $k=5$ 回合赢得游戏。

注意啊，这是一个翻牌游戏，就是一开始你是不知道这些数字，它的大小，你需要翻开来你才知道。

思路讲解

这个题实在是太简单了，我操，哎呀，真的是后悔为什么没看这题。

不难发现，在这种位置交换一下，就会增加一次这个轮数，那么你就把所有的这些位置，就是你就交换他要求的这个轮数啊，当然是比N多的这个轮数然后就就好了。也就是把我们所找到的这个位置交换我们代码当中的REM次就可以了。

ll rem=K-N;
for (int cnt=1,i=2;cnt<=rem;++cnt,i+=2) {
    if (i>=N2) {
        cout<<"NO\n";
        return;
    }
    swap(ans_ls[i],ans_ls[i+1]);
}
cout<<"YES\n";
for (int i=1;i<=N2;++i) {
    cout<<ans_ls[i]<<" ";
}
cout<<"\n";

AC代码

https://codeforces.com/contest/2202/submission/364156796

源代码

/**
 * Problem: D. Recollect Numbers
 * Contest: Codeforces Round 1082 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2202/problem/D
 * Created: 2026-02-24 10:57:23
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,K;
    cin >> N >> K;
    // 要求输出N个数，然后按照题目做法呢，他可以在K个回合内去这个叫什么，恰好K个回合就结束
    // 如果存在这种构造方法，就输出yes，不存在就输出no
    // 然后呢，题目它的做法是这样子的，就是没什么信息的，就翻第一张没有翻过的牌
    // 翻开了第一张没翻过的牌后，我们已经翻过的牌里有和这张牌一样的数字，就把它move掉。如果说还是没有，那么就继续翻第一张
    ll N2=2*N;
    vector<ll> ans_ls(N2+2);
    if (K<N) {
        cout<<"NO\n";
        return;
    }
    if (K==N) {
        cout<<"YES\n";
        for (int i=1,j=1;i<=N2;i+=2,j++) {
            cout<<j<<" "<<j<<" ";
        }
        cout<<"\n";
        return;
    }
    for (int i=1,j=1;i<=N2;i+=2,j++) {
        ans_ls[i]=j;
        ans_ls[i+1]=j;
    }
    ll rem=K-N;
    for (int cnt=1,i=2;cnt<=rem;++cnt,i+=2) {
        if (i>=N2) {
            cout<<"NO\n";
            return;
        }
        swap(ans_ls[i],ans_ls[i+1]);
    }
    cout<<"YES\n";
    for (int i=1;i<=N2;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/