社区讨论

WA#4#5求调

B3773[信息与未来 2022] 完美字符串参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m5we8svi
此快照首次捕获于
2025/01/14 19:32
去年
此快照最后确认于
2025/11/04 11:36
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define map mapp
using namespace std;
const int N=100000;
char s[N+10];
int n,len,map[N+10],tot,l=1,ans=0x3f3f3f3f,ac[N+10],lcmp,totot=1;
int check(int l,int r)
{
	int cntt[30],ret=1;
	memset(cntt,0,sizeof cntt);
	for(int i=l;i<=r;i++) cntt[map[i]]++;
	for(int i=1;i<=26;i++)
	{
		if(!cntt[i]) return 0;
	} 
	return 1;
}
void read()
{
	scanf("%s",s+1);
	len=strlen(s+1);
	totot++;
	ac[totot]=len+ac[totot-1];
	for(int i=1;i<=len;i++)
	{
		if(s[i]==' ') continue;
		map[++tot]=s[i]-'a'+1;
////		printf("%d ",map[tot]);
//		if(tot>26) continue;
//		cnt[map[tot]]++;
	}
}
//int find(int l,int r)
//{
//	int ret=0,i=1;
//	while(ac[i]<=l) i++;
//	i--;
//	ret=ret+l-ac[i];
//	i=totot;
//	while(ac[i]>=r) i--;
//	i++;
//	ret=ret+ac[i]-r;
//	return ret;
//}
int main()
{
	ac[1]=1;
	lcmp=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) read();
//	for(int r=27;r<=tot;r++)
//	{
//		cnt[map[r]]++;
//		if(!check(l,r)) continue;
//		while(check(l+1,r)) l++,cnt[map[l-1]]--;
//		int cmp=find(l,r);
//		ans=min(ans,cmp);
//		
//		for(int i=1;i<=26;i++) printf("i=%d,cnt=%d\n",i,cnt[i]);
//	}
//	for(int i=1;i<=totot;i++) printf("%d ",ac[i]);
	for(int i=1;i<=tot;i++)
	{
		int r=ac[i]-1;
		if(!check(l,r)) continue;
		
		while(check(l,r)&&l<r) l=ac[++lcmp];
		l=ac[--lcmp];
		ans=min(r-l+1,ans);
		//printf("\nans=%d,l=%d,r=%d\n",ans,l,r);
		
	}
	if(ans==0x3f3f3f3f) puts("-1");
	else printf("%d",ans);
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...