题解：CF1692H Gambling

FiraCode · 2024-08-15 17:27:02 · 题解

显然的，对于一个 a_i，我们把等于 a_i 的设为 1，其他设为 -1，那么就转化成了求最大字段和。

考虑顺着枚举 a_i，对于当前 i 暴力往后扫求以 i 开始的极长区间 [i,j]，使得对于所有区间 [i,k] 其中 (i \le k \le j) 满足这个区间的和 \ge 0。

那么对于这个区间 [i,j] 中所有的 =a_i 的 k 打上标记，下一次若遇到标记就不用再扫一遍了。

时间复杂度约为 O(n \sqrt n)，因为对于个数 \le \sqrt n 的数字，每个的贡献是 O(\sqrt n)。而对于个数 > \sqrt n 的数字，最多也就 O(\sqrt n)，所以这部分也就 O(n \sqrt n)，所以总时间复杂度为 O(n \sqrt n)。

#include <bits/stdc++.h>

using namespace std;

int T;
int n;
int a[200010];

int main() {
    scanf("%d", &T);
    for (int Tc = 1; Tc <= T; ++Tc) {
        unordered_map<int, int> st;

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

        int ans = 0, v, l, r;
        for (int i = 1; i <= n; ++i) {
            if (st.count(i)) continue;

            int s = 0;
            for (int j = i; j <= n; ++j) {
                if (a[j] == a[i]) ++s, st[j] = 1;
                else --s;

                if (s > ans) {
                    ans = s;
                    v = a[i];
                    l = i, r = j;
                }
                if (s < 0) break;
            }
        }

        printf("%d %d %d\n", v, l, r);
    }
    return 0;
}