CF1748B Diverse Substrings

题链：cf luogu

诈骗题。

Description

给你一个数字（\(0\sim 9\)）组成的字串，问有多少个子串满足：不同数字种类数不少于相同数字的最多出现次数。

Analysis

暴力思路很好想其实，无非就是暴力跑每一个子串，\(\mathcal{O}(n^3)\)，略加优化即可 \(\mathcal{O}(n^2)\)。

考虑一个合法的子串最多长度不会超过 \(100\)，证明也很容易：根据鸽巢原理，当全长达 \(101\) 时，至少有一种数字个数达到 \(11\) 或以上，而最多只有 \(10\) 个不同数字种类，显然不满足合法的定义。故合法必须长度不超过 \(100\)。

由此，时间复杂度降为 \(\mathcal{O}(100n)\)。可写。不难看出是一道诈骗题。

Code

此处为了进一步优化，用 \(a\) 和 \(b\) 直接记录不同数字种类数和相同数字的最多出现次数。可以看出当总长超出 \(100\) 时亦会退出。

#include <stdio.h>
const int N = (int)2e5 + 5;
int n; char s[N];
inline void Solve() {
	scanf("%d %s", &n, s + 1); long long ans = 0; int a, b;
	for (int i = 1; i <= n; ++i) {
		a = b = 0; int vis[10] = {0};
		for (int j = i; j <= n && a <= 10 && b <= 10; ++j) {
			if (!vis[s[j] - '0']) ++a; ++vis[s[j] - '0']; //不同
			if (vis[s[j] - '0'] > b) b = vis[s[j] - '0']; //最大次数
//			printf("%d %d: %d %d\n", i, j, a, b);
			if (a >= b) ++ans; //合法
		}
	}
	printf("%lld\n", ans);
}
int main(void) {
	int T; for (scanf("%d", &T); T--; ) Solve();
	return 0;
}

The end. Thanks.

Codeforces 名手：诈骗题

原文地址：http://www.cnblogs.com/dry-ice/p/cf1748b.html