USACO 2024年1月铜组 MAJORITY OPINION

本文主要是介绍USACO 2024年1月铜组 MAJORITY OPINION，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题：MAJORITY OPINION

标签：思维、模拟

题意：给定一个长度为 $n$ 的序列 $a$ ，操作：若区间 $[i, j]$ 内某个数字 $k$ 出现的次数 大于区间长度的一半，可以将区间内的所有数都换成这个数 $k$ 。经过多次操作之后，让区间 $[1, n]$ 内都为同一个数，输出所有可能的数（按照数字递增的顺序），若没有输出 $- 1$ 。（ $1<=n<=10^5,1<=a_i<=n$ ）

题解：连续两个相同的数，不管是往前还是往后一个，都可以把加进来的数变成区间内的这个数。
比如 $x\ y \ y \ z$ 可以往前把 $x$ 变成 $y$ ，往后把 $z$ 变成 $y$ ，那其实再往前或者再往后可以把所有数都变成 $y$ 。
除此之外，还有 $\ x\ y$ 的情况也是满足条件的，先把中间的这个 $x$ 变成 $y$ ，然后也可以把所有数都变成 $y$ 。

最终就变成了求第 $i$ 数和 第 $i - 1$ 个数或者第 $i - 2$ 个数 是否相同，相同的话，就可以去作为我们的答案，当然可能有重复的情况，所以要去重输出。
代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int t, n, a[N], res[N];int main() {cin >> t;while (t--) {cin >> n;int c = 0;for (int i = 1; i <= n; i++) {cin >> a[i];if (i >= 2 && a[i] == a[i - 1]) res[++c] = a[i];else if (i >= 3 && a[i] == a[i - 2]) res[++c] = a[i];}sort(res + 1, res + 1 + c);c = unique(res + 1, res + 1 + c) - res - 1;if (c == 0) cout << -1 << endl;else {for (int i = 1; i < c; i++) {cout << res[i] << " ";}cout << res[c] << endl;}}return 0;
}