CFCF2201B.Recollect Numbers
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 2n 张牌,每张牌上写有编号 1,1,2,2,…,n,n。也就是说,对所有 j=1,2,…,n,恰好有 2 张编号为 j 的牌。每张牌的正面只写有一个数字。
你要玩一个翻牌游戏。初始时,全部 2n 张牌都是牌背朝上(不显示数字的一面)。每回合,你要翻开恰好两张牌。如果这两张牌的数字相同,你就将它们从场上移除。否则,你需要把它们重新扣回原来的位置。你在所有 2n 张牌都被移除时获胜。注意,你不需要同时翻两张牌,因此你可以先看到第一张牌的数字后,再决定翻哪一张作为第二张。
考虑如下贪心算法来玩这个游戏。起始时,2n 张牌被按某个顺序一排放好。你每一步的策略如下:
- 如果你曾经翻过的两张牌中存在一对数字相同的牌,那么翻开这两张牌。
- 否则,先去翻第一张你到目前为止还没翻过的牌。假设这张牌上的数字是 x。
- 然后,如果你曾经翻过另一张数字为 x 的牌,去翻那一张。
- 否则,再去翻第一张你到目前为止(包括本轮刚翻的)还没翻过的牌作为第二张。
可以证明,上述算法的每一步选择都是唯一确定的。
你需要解决与上述算法相关的如下问题:
- 给定 n 与 k,请找出一种 2n 张牌的排列方式,使得按照上述算法恰好需要 k 步才能获胜。
如果不存在满足条件的排列方式,请输出无解。
*这里,“第一张牌”指的是当前序列中符合条件的最靠前的那一张。
输入格式
每组测试包含多个测试用例。第一行为测试用例个数 t(1≤t≤103)。
随后每个测试用例占一行,包含两个整数 n 与 k(1≤n≤300000,1≤k≤1000000)。
保证所有测试用例中 n 的总和不超过 300000。
输出格式
如果存在满足条件的排列方式,请输出一行 "YES"。
然后在下一行输出 2n 个整数 a1,a2,…,a2n−1,a2n,其中 ai 表示第 i 张牌上的数字。
需要保证序列 a 满足下列要求:
- 对每个 1≤i≤2n,都有 1≤ai≤n;
- 对每个 1≤j≤n,数字 j 在 a 中恰好出现两次;
- 若将牌按照此顺序排列,按题目中算法的策略,恰好需要 k 步获胜。
如果有多种答案,输出任意一种即可。
如果不存在满足条件的排列方式,输出一行 "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
说明/提示
对于第一个测试用例,每一步的选择如下:
- $ [\color{red}{2},\color{red}{1},\color{black} 2,1] $ :两张牌数字不同,扣回原位。
- $ [\color{red}{2},\color{blue}{1},\color{red}{2},\color{black}1] $ :两张牌数字相同,移除。
- $ [\color{red}{1},\color{red}{1}] $ :两张牌数字相同,移除。
这里,红色数字表示本轮翻开的牌,蓝色数字表示你曾经翻开的牌。
对于第四个测试用例,每一步如下:
- $ [\color{red}{1},\color{red}{2},\color{black}3,1,2,3] $ :两张牌数字不同,扣回原位。
- $ [\color{blue}{1},\color{blue}{2},\color{red}{3},\color{red}{1},\color{black}2,3] $ :两张牌数字不同,扣回原位。
- $ [\color{red}{1},\color{blue}{2},\color{blue}{3},\color{red}{1},\color{black}2,3] $ :两张牌数字相同,移除。
- $ [\color{red}{2},\color{blue}{3},\color{red}{2},\color{black}3] $ :两张牌数字相同,移除。
- $ [\color{red}{3},\color{red}{3}] $ :两张牌数字相同,移除。
此时算法共计用了 k=5 步获胜。