社区讨论
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 条回复,欢迎继续交流。
正在加载回复...