题解：P14131 【MX-X22-T2】「TPOI-4B」K Problem

tommy24 · 2025-10-02 21:22:11 · 题解

这是一个 O(n^2) 的瞎搞做法。

我们称一个区间是合法的当且仅当期间有 1 个 1，2 个 2, ... , k 个 k。

观察到我们所求的合法区间长为 \frac{k(k+1)}{2}，因此可以考虑枚举所有长为 \frac{k(k+1)}{2} 的区间，然后使用桶维护该区间内的各个元素之数量以判断其是否合法，时间复杂度为 O(n^2)，显然无法通过。

因此我们考虑优化，观察到长度为 \frac{k(k+1)}{2} 的合法区间，其元素和必须等于 \sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}。因此，我们预处理前缀和数组，仅对长度和区间和均符合上述条件的区间进行合法性检验。尽管时间复杂度仍为 O(n^2)，但常数贼小，能够通过本题：

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

const int MAXN = 100050;
long long a[MAXN], s[MAXN], d[MAXN];
int ans = 0;

void check(int a1, int b, int c){ // 判断长为 c(c+1)/2 的区间 [a,b] 是否合法，如果是便更新答案，否则不动
    for(int i = 1; i <= c; i ++) d[i] = 0;
    for(int i = a1; i <= b; i ++){
        d[a[i]] ++;
    }
    for(int i = 1; i <= c; i ++){
        if(d[i] != i) return;
    }
    ans = c;
}

void solve(){
    int n = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) s[i] = 0;
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    ans = 0;
    for(int l = 1; l * (l + 1) <= 2 * n; l ++){
        int length = (l * (l + 1)) / 2;
        for(int i = 1; i + length <= n; i ++){
            int sum = l * (l + 1) * (2 * l + 1);
            if(s[i + length - 1] - s[i - 1] == sum / 6) check(i, i + length - 1, l);
            if(ans == l) break; // 此时继续往后枚举不影响答案，break掉即可
        }
    }
    printf("%d\n", ans);
}

int main(){
    int t = 0;
    scanf("%d", &t);
    for(int i = 1; i <= t; i ++){
        solve();
    }
}

当然，如果出题人刻意构造数据卡掉该做法，我们还能更新换代：考虑再维护一个前缀和数组来计算数组 a 每一项的平方和，此后在调用 check 函数前增加判断该区间的平方和是否为 \frac{n^2(n+1)^2}{4}。这样，程序每次使用 check 函数几乎都能找到合法区间，虽然时间复杂度仍为 O(n^2)，但能够通过且较难卡掉。