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

这是一个

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)

，但常数贼小，能够通过本题：

CPP

#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)

，但能够通过且较难卡掉。

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

文章操作

相关推荐

评论

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