[ZPG TEST 115] 字符串【归类思想】

pdf效果太差，转成word效果依旧差，只好转成jpg传了。

这一题用到了“归类”的思想，令s(i, a)表示前i个字体，字符a出现的次数。那么ans一定等于一个

( s(i, a) - s(j, a) ) - ( s(i, b) - s(j, b) )，

归一下类，得到ans等于一个

( s(i, a) - s(i, b) ) - ( s(j, a) - s(j, b) ).

所以我们只需要读入一个字符a，然后枚举那个字符b，在用上式计算答案，要保存前面的s(j, a) - s(j, b)的最小值。

然而还是有一种特殊情况，举个例子，aaabbbb，如果直接向上面那样做得到的答案是4，对应的是bbbb那一串，即4个b减去0个a，但是出现0次并不算出现，所以我们需要保存一个cj[26][26],其中cj[a][b]表示s(j, a) - s(j, b)取到最小值时，b字符出现的个数。那么如果s(i, b) == cj(a, b)的话，就不能更新答案，因为这一段是没有字符b的。

#include <cstdio>

#include <algorithm>

#include <cstring>

const int maxn = 1000005;

int n, a[maxn], mn[30][30], ans, s[30], cj[30][30];

char ch;

int main(void) {

	freopen("string.in", "r", stdin);

	freopen("string.out", "w", stdout);

	scanf("%d", &n);

	while ((ch = getchar()) < 'a');

	a[1] = ch - 'a';

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

		a[i] = getchar() - 'a';

	}

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

		++s[a[i]];

		for (int j = 0; j < 26; ++j) {

			if (a[i] == j) {

				continue;

			}

			if (s[a[i]] > s[j]) {

				if (s[j] > cj[a[i]][j]) {

					ans = std::max(ans, s[a[i]] - s[j] - mn[a[i]][j]);

				}

			}

			else if (s[a[i]] < s[j]) {

				ans = std::max(ans, s[j] - s[a[i]] - mn[j][a[i]]);

			}

			if (s[a[i]] - s[j] < mn[a[i]][j]) {

				mn[a[i]][j] = s[a[i]] - s[j];

				cj[a[i]][j] = s[j];

			}

			if (s[j] - s[a[i]] < mn[j][a[i]]) {

				mn[j][a[i]] = s[j] - s[a[i]];

				cj[j][a[i]] = s[a[i]];

			}

		}

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

[ZPG TEST 115] 字符串【归类思想】

最新文章

热门文章