CFCF2201B.Recollect Numbers

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

2n2n 张牌,每张牌上写有编号 1,1,2,2,,n,n1, 1, 2, 2, \ldots, n, n。也就是说,对所有 j=1,2,,nj=1,2,\ldots,n,恰好有 22 张编号为 jj 的牌。每张牌的正面只写有一个数字。

你要玩一个翻牌游戏。初始时,全部 2n2n 张牌都是牌背朝上(不显示数字的一面)。每回合,你要翻开恰好两张牌。如果这两张牌的数字相同,你就将它们从场上移除。否则,你需要把它们重新扣回原来的位置。你在所有 2n2n 张牌都被移除时获胜。注意,你不需要同时翻两张牌,因此你可以先看到第一张牌的数字后,再决定翻哪一张作为第二张。

考虑如下贪心算法来玩这个游戏。起始时,2n2n 张牌被按某个顺序一排放好。你每一步的策略如下:

  • 如果你曾经翻过的两张牌中存在一对数字相同的牌,那么翻开这两张牌。
  • 否则,先去翻第一张你到目前为止还没翻过的牌。假设这张牌上的数字是 xx
    • 然后,如果你曾经翻过另一张数字为 xx 的牌,去翻那一张。
    • 否则,再去翻第一张你到目前为止(包括本轮刚翻的)还没翻过的牌作为第二张。

可以证明,上述算法的每一步选择都是唯一确定的。

你需要解决与上述算法相关的如下问题:

  • 给定 nnkk,请找出一种 2n2n 张牌的排列方式,使得按照上述算法恰好需要 kk 步才能获胜。

如果不存在满足条件的排列方式,请输出无解。

*^{\text{*}}这里,“第一张牌”指的是当前序列中符合条件的最靠前的那一张。

输入格式

每组测试包含多个测试用例。第一行为测试用例个数 tt1t1031 \le t \le 10^3)。
随后每个测试用例占一行,包含两个整数 nnkk1n3000001 \le n \le 300\,0001k10000001 \le k \le 1\,000\,000)。

保证所有测试用例中 nn 的总和不超过 300000300\,000

输出格式

如果存在满足条件的排列方式,请输出一行 "YES"。

然后在下一行输出 2n2n 个整数 a1,a2,,a2n1,a2na_1,a_2,\ldots,a_{2n-1},a_{2n},其中 aia_i 表示第 ii 张牌上的数字。

需要保证序列 aa 满足下列要求:

  • 对每个 1i2n1 \le i \le 2n,都有 1ain1 \le a_i \le n
  • 对每个 1jn1 \le j \le n,数字 jjaa 中恰好出现两次;
  • 若将牌按照此顺序排列,按题目中算法的策略,恰好需要 kk 步获胜。

如果有多种答案,输出任意一种即可。

如果不存在满足条件的排列方式,输出一行 "NO"。

你的输出大小写不限,"yEs"、"yes"、"Yes" 等均视为正确的肯定回答。

输入输出样例

  • 输入#1

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

    输出#1

    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

说明/提示

对于第一个测试用例,每一步的选择如下:

  1. $ [\color{red}{2},\color{red}{1},\color{black} 2,1] $ :两张牌数字不同,扣回原位。
  2. $ [\color{red}{2},\color{blue}{1},\color{red}{2},\color{black}1] $ :两张牌数字相同,移除。
  3. $ [\color{red}{1},\color{red}{1}] $ :两张牌数字相同,移除。

这里,红色数字表示本轮翻开的牌,蓝色数字表示你曾经翻开的牌。

对于第四个测试用例,每一步如下:

  1. $ [\color{red}{1},\color{red}{2},\color{black}3,1,2,3] $ :两张牌数字不同,扣回原位。
  2. $ [\color{blue}{1},\color{blue}{2},\color{red}{3},\color{red}{1},\color{black}2,3] $ :两张牌数字不同,扣回原位。
  3. $ [\color{red}{1},\color{blue}{2},\color{blue}{3},\color{red}{1},\color{black}2,3] $ :两张牌数字相同,移除。
  4. $ [\color{red}{2},\color{blue}{3},\color{red}{2},\color{black}3] $ :两张牌数字相同,移除。
  5. $ [\color{red}{3},\color{red}{3}] $ :两张牌数字相同,移除。

此时算法共计用了 k=5k=5 步获胜。

首页