诈骗题。
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 名手：诈骗题