#P14222. [2026队测系列]星港远征计划之被盗的项链
[2026队测系列]星港远征计划之被盗的项链
题目背景
在星港远征计划中,远征队从遗迹中取回了 枚能量宝石。每种型号的宝石恰好有两枚,但在运输途中被打乱成一排。
为了进行后续分析,你希望在这排宝石之间插入若干隔板,把它们分成若干连续区间。要求把从左往右编号为奇数的区间中的宝石全部收集起来后,能够恰好得到每种型号各一枚。
请你构造一种满足条件的分隔方案。
题目描述
有 个宝石从左到右排成一列,第 个宝石的种类为 。其中, 是 到 之间的整数,并且每一种类型的宝石都恰好出现两次。
你需要插入若干隔板,使其满足以下条件:
- 每个隔板的位置用一个整数 ()表示,表示在从左起第 个宝石与第 个宝石之间插入隔板;
- 同一个位置不能插入两个或以上的隔板;
- 隔板总数 不超过 ;
- 插入这 个隔板后,整列宝石会被分成 个连续区间。此时,将从左往右编号为奇数的区间中的全部宝石取出,要求恰好得到种类 的宝石各一枚。
请输出任意一种满足条件的插入方法。可以证明,这样的方法一定存在。
共有 组测试数据,你需要分别求解。
输入格式
输入从标准输入给出,格式如下:
T
case1
case2
...
caseT
每组测试数据的格式为:
N
A1 A2 ... A2N
输出格式
按顺序输出 组测试数据的答案。
对于每组测试数据,设隔板数量为 ,隔板位置按升序为 ,则输出格式为:
K
C1 C2 ... CK
其中必须满足 。
样例 #1
输入
2
3
1 2 2 3 3 1
5
1 2 3 4 5 5 4 3 2 1
输出
3
1 2 4
1
5
说明
对于第 组测试数据,在位置 插入隔板后,宝石会被分成:
取出从左往右编号为奇数的区间中的全部宝石后,可得到种类 各恰好一枚。
数据范围
- 对于每个 ,满足 的位置恰好有两个
- 所有测试数据中 的总和不超过
- 输入中的所有值均为整数