P10131 Majority Opinion 题解

Su777 · 2024-02-06 10:49:04 · 题解

题意简述

给定一个长度为 n 的序列 h 且 1 \leq h_i \leq n。对于每次操作，可以选择一个区间 [l,r]，此时如果存在一个数的出现次数严格大于区间长度的一半，就把整个区间都替换成那个数。求最后一共有多少种数可以出现 n 次（整个序列都是那种数）。

分析样例

• 在 T=1 的情况下，2 连续出现了三次，此时可以选择区间 [1,5]，将所有位置替换为 2，答案为 2。
• 在 T=2 的情况下，没有两个相邻位置是同样的数，所以无法替换，答案为 -1。
• 在 T=4 的情况下，出现了形如 \{3,x,3\} 的情形，这时只需要选择这个长度为 3 的区间替换为 3，就可以转化为 T=1 的情况了。

感性理解

• 当有两个相邻位置是同样的数时，可以将整个序列替换为这种数。
• 当有两个位置是同样的数，且中间只隔了一个位置，可以将整个序列替换为这种数。
• 当不存在上述两种情况时，无法替换。

严谨证明

结论一

假设 h_i=h_{i+1}=x。此时考虑左右两种方向。

左方向操作方法：假设此时 [i-k,i] 区间内的数均为 x，那么 k \geq 1。选择区间 [i-k-1,i] 进行操作。
右方向操作方法：假设此时 [i,i+k] 区间内的数均为 x，那么 k \geq 1。选择区间 [i,i+k+1] 进行操作。
操作可行性：区间长度为 k+2，其中至少有 k+1 个数为 x。又因为 k \geq 1，等价于 k+1 \geq \frac{k+2}{2}+1，所以可以将整个区间替换为 x。后续区间以此类推，直到 i-k-1=0 为止。

结论二

假设 h_i=h_{i+2}=x。此时选择区间 [i,i+2]，长度为 3，至少有 2 个元素为 x。因为 2 > \frac{3}{2}，所以可以将整个区间替换为 x。

替换后可以发现，h_i=h_{i+1}=x。然后用结论一中的替换方法把整个序列都替换为 x 即可。

结论三

用反证法进行解决。如果上述两种情况都不存在，也就意味着任意连续的三个位置都互不相同。

假设存在可替换区间 [l,r]，那么这个区间中有一种数的出现次数必定 \geq \frac{r-l+1}{2}+1。又因为任意连续三个位置都不不相同，这种数的出现次数必定 \leq \lfloor \frac{r-l+1}{3} \rfloor，矛盾。所以原假设不成立，在这样的序列中不存在任何一个区间可以进行替换，也就不可能有数出现 n 次。

赛时代码

注意特判行末空格即可。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2e5 + 10;
ll T, n;
ll arr[N];
ll ok[N];

int main() {
    cin >> T;
    while (T--) {
        memset(ok, 0, sizeof(ok));
        cin >> n;
        for (int i = 1; i <= n; i ++) {
            cin >> arr[i];
            if (arr[i] == arr[i - 1]) ok[arr[i]] = 1;
            if (i > 1 && arr[i] == arr[i - 2]) ok[arr[i]] = 1;
        }
        ll cnt = 0;
        for (int i = 1; i <= n; i ++) {
            if (ok[i]) {
                cnt ++;
            }
        }

        if (cnt != 0) {
            int cnt2 = 1;
            for (int i = 1; i <= n; i ++) {
                if (ok[i]) {
                    if (cnt2 != cnt) {
                        cnt2 ++;
                        cout << i << " ";
                    } else {
                        cout << i;
                    }
                }
            }
        } else if (cnt == 0) cout << "-1";
        cout << endl;
    }
    return 0;
}