USACO 2024年1月铜组 MAJORITY OPINION

第一题：MAJORITY OPINION

标签：思维、模拟

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

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