701 C. They Are Everywhere

链接

[http://codeforces.com/group/1EzrFFyOc0/contest/701/problem/C]

题意

给你一个包含大小写字母长度为n的字符串，让你找包含所有种类字符的最短串

分析

其实这个用尺取法，先从开始找包含各种字符的串，然后不断地贪心取最小ans,具体看代码

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int n,i;

	string s;

	int a[140],b[140];

	//freopen("in.txt","r",stdin);

	while(cin>>n){

		cin>>s;

		int sum=0;

		memset(a,0,sizeof(a));

		memset(b,0,sizeof(b));

		for(i=0;i<n;i++)

		a[s[i]]=1;

		for(i=50;i<='z';i++)

		sum+=a[i];

		//cout<<sum<<endl;

		memset(a,0,sizeof(a));

		int ans=n,st=0,cnt=0;

		for(i=0;i<n;i++){

			if(s[i]>='a'&&s[i]<='z'){

				if(!a[s[i]-'a']){

					cnt++;

				}

				a[s[i]-'a']++;

			}

				else {

					if(!b[s[i]-'A'])

					cnt++;

					b[s[i]-'A']++;

			}

				if(cnt==sum){

					while(cnt==sum){

						if(i-st+1<ans) ans=i-st+1;

						if(s[st]>='a'&&s[st]<='z'){

							a[s[st]-'a']--;

							if(!a[s[st]-'a'])

							cnt--;

						}

						else {

							b[s[st]-'A']--;

							if(!b[s[st]-'A'])

							cnt--;

						}

						st++;

					}

				}

			}

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

701 C. They Are Everywhere

链接

题意

分析

代码

最新文章

热门文章