【题解】「P6832」[Cnoi2020]子弦

【题解】「P6832」[Cnoi2020]子弦第一次写月赛题解（

首先第一眼看到这题，怎么感觉要用 \(\texttt{SAM}\) 什么高科技的？结果一仔细读题，简单模拟即可。

我们不难想出，出现最多次的子串的长度必然是 \(1\)，不管怎样，长度 \(\geqslant 2\) 的子串的出现次数都必然 \(\leqslant\) 长度为 \(1\) 的子串的出现次数。

这样我们就可以将题目描述变变：

给定字符串 \(\texttt{S}\)，求 \(\texttt{S}\) 出现次数最多的字符的出现次数。

那么就很容易写出代码了：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <string>

#define line cout << endl

using namespace std;

const int NR = 1e4 + 5;

int cnt[NR], ans = -1;

int main () {

	char c;

	int n = 0;

	while (cin >> c) {

		n = max ((int) c, n);

		cnt[c]++;

	}

	for (int i = 1; i <= n; i++) {

		ans = max (ans, cnt[i]);

	}

	cout << ans << endl;

	return 0;

}

巴特西

【题解】「P6832」[Cnoi2020]子弦

最新文章

热门文章