【题解】「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;
}
上一篇:Codeforces 1530E Minimax 题解


下一篇:雲雀