#P1366. 有序表的合并
有序表的合并
题目描述
给出两个数列 ,均按不降序排序。其中保证 中没有重复的数字。
现在请你求出: 中每一个数字在 中出现了几次?
输入格式
本题单测试点内有多组测试数据。
输入的第一行是一个整数,表示数据组数 。接下来按顺序给出每组数据的输入信息:
第一行为两个整数,依次表示 数列的长度 和 数列的长度 。
第二行有 个整数表示数列 ,第 个整数表示 。
第三行有 个整数表示数列 ,第 个整数表示 。
输出格式
为了避免输出过大,对于每组数据,请你输出一行一个整数,表示数列 的每个数在 中出现次数的按位异或和。
形式化的,设 在 中出现了 次,则你需要输出 的值,其中 表示按位异或操作。你可以参考提示来完成计算。
1
3 5
1 3 6
1 3 3 5 5
3
1
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5
2
2
3 5
1 3 6
1 3 3 5 5
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5
3
2
提示
样例 1 解释
- 在 中出现了 次。
- 在 中出现了 次。
- 在 中出现了 次。
故输出为 。
样例 2 解释
分别在 中出现了 次,故输出为 。
数据规模与约定
对于全部的测试点,保证:
- ;
- ,;
- ,且 ,。
其中 表示单测试点内所有 与 的和,即输入数列的总长度不超过 。
提示
- 请注意大量数据读入对程序效率造成的影响,选择合适的读入方式,避免超时。
- 请采用合适的数据类型存储变量,避免溢出。
- 如果你不知道什么是按位异或和,可以在你的代码里添加如下的函数:
template <class T>
T getXorSum(T *begin, T *end) {
T ret = 0;
for (T *it = begin; it != end; ++it) ret ^= *it;
return ret;
}
这一函数的作用是计算传入数组(包括 std::vector
)某一左闭右开区间的按位异或和,返回值类型与传入数组的类型相同,调用方法与 std::sort
类似,例如,要求数组 的 的按位异或和,则调用 getXorSum(a + 1, a + 1 + n)
,求 的按位异或和,则调用 getXorSum(a, a + n)
。如果 是 std::vector
,则将上述调用代码里的 a
均改为 a.begin()
即可。