#CW62. 列交换(columns)
列交换(columns)
题目描述
给定一个有 列、两行的表格。第 列的上方和下方分别是两个整数;列编号从左到右为 到 。每个整数都在 到 之间,但不保证每个整数恰好出现两次;同一个整数可能在某一行中重复出现,也可能在两行中出现不同次数。
交换只会改变数字所在的行,不会改变它在整个表格中的总出现次数。因此,若某个数的总出现次数不等于 ,这一组数据一定无解;即使每个数都出现两次,也仍需进一步判断是否能通过交换满足要求。
你可以选择若干列,每个被选列至多操作一次;操作是交换这一列的上下两个数。交换完成后,要求上面一行和下面一行都恰好包含 到 各一次,也就是说两行都必须是 个元素的排列。请先求达到要求所需的最少交换列数,再给出任意一个达到这个最少值的列集合。如果无论怎样交换都无法达到要求,则该组数据无解。
输入格式
从 columns.in 文件中读入。
第一行是测试组数 。每组数据先给出列数 ,随后给出上面一行的 个整数和下面一行的 个整数。输入保证所有测试组的列数之和不超过 ,且给出的整数均在 到 之间。
输出格式
从 columns.out 文件中输出。
如果无解,输出一行 。否则先输出最少交换次数 ;随后输出 个被交换的列编号。列编号可以按任意顺序给出,答案只要确实使两行成为排列且 最小即可。
样例 1 输入
6
4
1 2 3 4
2 3 1 4
5
5 3 5 1 4
1 2 3 2 4
3
1 2 1
3 3 2
4
1 2 2 1
3 4 3 4
4
4 3 1 4
3 2 2 1
3
1 1 2
3 2 2
样例 1 输出
0
2
2 3
1
1
2
3 4
2
3 4
-1
样例 1 解释
- 第 组已经满足要求,不需要交换。
- 第 组交换第 列后,两行分别为 和 。
- 第 组交换第 列后,两行分别为 和 。
- 第 组交换第 列后,两行分别为 和 。
- 第 组交换第 列后,两行分别为 和 。
- 第 组无解。
样例输出中的列编号只是其中一种合法方案,任何达到最少交换次数且合法的列集合都会被接受。
数据范围
对全部数据,,,且 。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 25 | ||
| 2 | |||
| 3 | |||
| 4 | 完整数据范围 |