#2412. 众数
众数
众数
题目描述
ZJOI 2022 第一试 众数(mode) 众数(mode) 【题目描述】 九条可怜是一个有超能力的女孩子,但她的超能力只能作用于一些奇怪的事情上。 有一天,可怜得到了一个序列a1, a2, · · · , an ,她可以对这个序列使用一次超能力:选择一个区 间[l, r] ( 1 ≤l ≤r ≤n ) 和一个整数k ∈[−109, 109] ,将区间内的所有数al, al+1, · · · , ar 加上k 。 九条可怜很喜欢长得比较一致的序列,因此她希望最终的序列众数的出现次数尽可能多。给出序 列a ,你需要输出最终序列的众数出现次数的最大值,并输出这个众数的所有可能取值。注意对于 一个序列,众数的取值可能不止一个。 【输入格式】 从文件mode.in 中读入数据。 输入包含多组数据,第一行输入数据组数T 。 对于接下来的每组数据,第一行输入序列长度n ,第二行包含n 个整数a1, a2, · · · , an 。 【输出格式】 输出到文件mode.out 中。 对于每组数据,第一行输出最终序列众数的出现次数的最大值。 假设这个众数有k 种不同的可能取值,则接下来k 行,从小到大输出这些取值。 【样例输入】 见下发文件中的mode ex1.in和mode ex2.in。 【样例输出】 见下发文件中的mode ex1.ans和mode ex2.ans。 第4 页 共7 页
ZJOI 2022 第一试 众数(mode) 【数据范围与提示】 对于所有测试点:1 ≤T ≤20 ,2 ≤n ≤200 000 ,1 ≤ai ≤109 ,保证P n ≤500 000 ,且ai 不全相等。 每个测试点的具体限制见下表: 测试点编号 P n ≤ n ≤ 特殊限制 1 ∼4 3 000 300 无 5 ∼8 500 000 200 000 ai 只有5 种取值 9 ∼10 200 000 50 000 无 11 ∼20 500 000 200 000 无 第5 页 共7 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
5
1 2 3 2 1
5
1 1 3 1 1
6
2 4 2 4 8 8
5
1 2 3 4 5
4
1
5
1
4
2
4
8
2
1
2
3
4
5