比赛 20160407 评测结果 RRRRRRRRRR
题目名称 HH的项链 最终得分 0
用户昵称 FETS 1/3 运行时间 0.003 s
代码语言 C++ 内存使用 5.08 MiB
提交时间 2016-04-07 09:19:29
显示代码纯文本
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int SIGMA = 26, N = 1000050;
char buff[N];
int dt[N];
vector<int> pos[SIGMA], cur;//pos数组代表的是某个字符出现的位置
int main ()
{
	//freopen("diff.in", "r", stdin);
	//freopen("diff.out", "w", stdout);
	int n, res(0);
	scanf("%d", &n);
	scanf("%s", buff);
	for (int i = 0; i < n; ++i)
		pos[dt[i] = buff[i] - 'a'].push_back(i);
	for (int i = 0; i < SIGMA; ++i)
		for (int j = 0; j < SIGMA; ++j) if (i != j)
		{
			int cres(0), csum(0), cspre(0), cpre(~0u >> 2);
			cur.resize(pos[i].size() + pos[j].size());//设置cur的大小为第i个字符的出现次数+第j个字符的出现字数
			merge(pos[i].begin(), pos[i].end(), pos[j].begin(), pos[j].end(), cur.begin());//把两个序列合并到cur里
			for (__typeof(cur.begin()) it = cur.begin(); it != cur.end(); ++it)
			{
				csum += dt[*it] == i ? +1 : -1;
				if (dt[*it] == j)
				{
					cpre = min(cpre, cspre);
					cspre = csum;
				}
				cres = max(cres, csum - cpre);
			}
			res = max(res, cres);
		}
	printf("%d\n", res);
	return 0;
}