江苏省信息与未来2022T3

YYDS314

已于 2025-04-09 19:45:05 修改

阅读量638

点赞数 18

分类专栏：题解文章标签：算法 c++ 剪枝

于 2025-04-04 13:42:48 首次发布

本文链接：https://blog.csdn.net/YYDS314/article/details/146997712

版权

题解专栏收录该内容

20 篇文章

订阅专栏

你可能见过下面这一句英文:The quick brown fox jumps over the lazy dog.
短短的一句话就包含了所有26个英文字母!因此这句话广泛地用于字体效果的展示。更短的有:The five boxing wizards jump quickly.
所以你很好奇:还有没有更多这样包含所有26个英文字母的句子? 于是你用爬虫在互联网上爬取了许多英文文本,并且提取出了其中的单词。你现在希望从一个很长的单词序列中找出一段连续出现的单词,它满足:所有26个英文字母都至少出现一次;长度尽可能短,即包含的字母总数尽可能少。
输入的第一行包含一个整数n,代表单词序列的长度,即单词的数量。
输入的第二行包含n个空格分隔的英文单词(单词仅由小写字母构成)。输入数据保证每个小写英文字母都至少出现一次。
输出一行一个整数,是你找到的单词序列中的字母总数。

输入

13 
there  is  a  quick  brown  fox  jumping  over the  lazy  dog  and  cat

输出

$n\leqslant 10^5$

保证输入合法。

#include <bits/stdc++.h>
using namespace std;
string sen[100005];
int h[30],t[30];
int n,have,ans;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>sen[i];
		for(int j=0; j<sen[i].size(); j++)
		{
			int nu=sen[i][j]-96;
			if(h[nu]==0) have++;
			h[nu]++;
			t[nu]++;
		}
		ans+=sen[i].size();
	}
	int l=1,r=n,jsi;
	bool f;
	while(l<r)
	{
		f=1;
		jsi=sen[r].size();
		for(int i=0; i<jsi; i++)
		{
			int no=sen[r][i]-96;
			t[no]--;
			if(t[no]==0)
			{
				f=0;
				break;
			}
		}
		if(f==1)
		{
			//cout<<"OUT+"<<'\n';
			for(int i=0; i<jsi; i++)
			{
				int no=sen[r][i]-96;
				ans-=h[no]-t[no];
				h[no]=t[no];
			}
			r--;
		}
		//cout<<f<<'\n';
		for(int i=1; i<=26; i++) t[i]=h[i];
		//for(int i=1; i<=26; i++) cout<<h[i]<<" ";
		//cout<<'\n';
		//cout<<l<<" "<<r<<'\n';
		if(f==0) break;
	}
	f=1;
	jsi=sen[l].size();
	for(int i=0; i<jsi; i++)
	{
		int no=sen[l][i]-96;
		if(t[no]==1)
		{
			f=0;
			break;
		}
		else t[no]--;
	}
	if(f==1)
	{
		for(int i=0; i<jsi; i++)
		{
			int no=sen[l][i]-96;
			ans-=h[no]-t[no];
			h[no]=t[no];
		}
	}
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
string sen[100005];
int h[30],t[30];
int n,have,ans;
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>n;
   for(int i=1; i<=n; i++)
   {
       cin>>sen[i];
       for(int j=0; j<sen[i].size(); j++)
       {
           int nu=sen[i][j]-96;
           if(h[nu]==0) have++;
           h[nu]++;
           t[nu]++;
       }
       ans+=sen[i].size();
   }
   int l=1,r=n,jsi;
   bool f;
   while(l<r)
   {
       f=1;
       jsi=sen[r].size();
       for(int i=0; i<jsi; i++)
       {
           int no=sen[r][i]-96;
           t[no]--;
           if(t[no]==0)
           {
               f=0;
               break;
           }
       }
       if(f==1)
       {
           //cout<<"OUT+"<<'\n';
           for(int i=0; i<jsi; i++)
           {
               int no=sen[r][i]-96;
               ans-=h[no]-t[no];
               h[no]=t[no];
           }
           r--;
       }
       //cout<<f<<'\n';
       for(int i=1; i<=26; i++) t[i]=h[i];
       //for(int i=1; i<=26; i++) cout<<h[i]<<" ";
       //cout<<'\n';
       //cout<<l<<" "<<r<<'\n';
       if(f==0) break;
   }
   f=1;
   jsi=sen[l].size();
   for(int i=0; i<jsi; i++)
   {
       int no=sen[l][i]-96;
       if(t[no]==1)
       {
           f=0;
           break;
       }
       else t[no]--;
   }
   if(f==1)
   {
       for(int i=0; i<jsi; i++)
       {
           int no=sen[l][i]-96;
           ans-=h[no]-t[no];
           h[no]=t[no];
       }
   }
   cout<<ans;
   return 0;
}
该代码WA,40pts