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;
}