第九届河南理工大学算法程序设计大赛 正式赛 E：Mo的游戏

单测试点时限: 1.0 秒

内存限制: 512 MB

Mo翻书看到一种新的连连看游戏：对于一个字符串来说，只有当两个字符相同时候才可以进行相连，得分为字符串的长度减去两个相连字符的距离（如果整个字符串中某一种字符个数为1，那么不能相连故得分为$0$）。Mo现在在玩这个游戏，但是Mo不知道该选择哪一种字符进行相连，所以请你列出每种字符相连可以获得的最大分数，以此来让Mo进行参考。

输入

一个字符串$s$ （$0<strlen(s)<10^6$， $s$中只包含大小写字符）。

输出

针对$s$中出现过的字符，每行输出一个整数表示用当前字符进行相连可以获得的最大分数, 按照$a−z$，$A−Z​$的顺序。具体格式参见样例。

样例

input

Aabcaabcb

output

a:8
b:7
c:5
A:0

Solve

将每个字母出现的所有位置放进vector中，最后进行遍历，去寻找距离最小的两个位置

没想到什么好的方法，只有这样写了

Code

#include<bits/stdc++.h>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
const int maxn=1e6+10;
const int maxm=1e3+10;
const int inf=(1<<30);
const ll INF=(1LL*1<<60);
using namespace std;
vector<int>v[100];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	string s;
	cin>>s;
	int l=s.length();
	map<char,int>mp;
	for(int i=0;i<l;i++)
	{
		mp[s[i]]++;
		v[s[i]-'A'].push_back(i);
	}
	for(int i='a';i<='z';i++)
	{
		if(!mp[i])
			continue;
		cout<<(char)i<<":";
		if(mp[i]==1)
		{
			cout<<0<<endl;
			continue;
		}
		int minn=inf;
		for(int j=0;j<v[i-'A'].size()-1;j++)
		{
			for(int k=j+1;k<v[i-'A'].size();k++)
			{
				minn=min(v[i-'A'][k]-v[i-'A'][j],minn);
				if(minn==1)
					break;
			}
		}
		cout<<l-minn<<endl;
	}
	for(int i='A';i<='Z';i++)
	{
		if(!mp[i])
			continue;
		cout<<(char)i<<":";
		if(mp[i]==1)
		{
			cout<<0<<endl;
			continue;
		}
		int minn=inf;
		for(int j=0;j<v[i-'A'].size()-1;j++)
		{
			for(int k=j+1;k<v[i-'A'].size();k++)
			{
				minn=min(v[i-'A'][k]-v[i-'A'][j],minn);
				if(minn==1)
					break;
			}
		}
			cout<<l-minn<<endl;
	}
	return 0;
}