比赛 |
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;
}