上海计算机学会2021年7月月赛C++丙组T4比赛组卷
发布时间
阅读量：
阅读量
比赛组卷
内存限制: 256 Mb时间限制: 1000 ms
题目描述
小爱老师正在准备计算机知识竞赛的考试试题，认真负责的她精心挑选了 k 道试题（编号1~k）组成了题库，并由系统随机抽选其中 n 题作为考试试卷。
系统在组卷时自动组成了A卷和B卷，其中𝐴A卷𝑛n道题的编号为a1,a2,…,an，其中B卷n道题的编号为b1,b2,…,bn。
请你帮小爱老师计算一下，有多少道试题同时出现在A,B卷中，并按从小到大的顺序给出重复试题的编号。
输入格式
输入共三行：
第一行，两个正整数表示n,k
第二行，n个正整数表示a1,a2,...,an
第三行，n个正整数表示b1,b2,...,bn
输出格式
输出第一行：重复试题的数量
输出第二行：按从小到大顺序输出重复试题的编号
（若第一行重复试题的数量为0，则不用输出第二行的信息）
数据范围
- 对于30%的数据，1≤k≤10
- 对于70%的数据，1≤k≤10^4
- 对于100%的数据，1≤k≤10^5
1≤n≤k，1≤a1,a2,...,an≤k，1≤b1,b2,...,bn≤k
样例数据
输入:
5 10
1 2 3 4 5
10 9 8 7 6
输出:
0
说明:
A,B卷没有出现重复试题
输入:
5 10
6 4 1 8 10
5 1 7 4 6
输出:
3
1 4 6
说明:
A,B卷中均出现了编号为1，编号为4，编号为6的题目，其余题目没有重复
解析：使用桶排序，找到出现次数两次的题号
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n,k,x;
int t[100005];
int cnt=0;
int main () {
cin>>n>>k;
for(int i=1;i<=n*2;i++){//桶排序
cin>>x;
t[x]++;
}
for(int i=1;i<=k;i++){//统计重复题号数量
if (t[i]==2){
cnt++;
}
}
cout<<cnt<<endl;
if(cnt>0){//有重复
for(int i=1;i<=k;i++){//输出重复题号
if (t[i]==2){
cout<<i<<" ";
}
}
}
return 0;
}
全部评论 (0)
还没有任何评论哟~