目录
Description
有 \(n\) 个字符串,第 \(i\) 次操作,可以将这 \(n\) 个字符串的第 \(i\%|s|\) 个字符依次发送形成一个新的无限长字符串,在这个新字符串上找到最短区间包含这 \(n\) 个字符串上出现的字符,输出这个区间长度
State
\(1<=n<=100\)
\(1<=T<=100\)
\(1<=|s|<=12\)
Input
2
2
abc
bd
2
bab
bbc
Output
4
4
Solution
题意劝退
就像第一组样例一样,可以构造一个字符串 \(ans=ab\ bd\ cb\ ad\ bb\ cd\ (ab)\) ,最小长度的区间为 \(cbad\) ,构造出这个字符串来尺取一下就可以了
\(hint:\) 构造出一个字符串是不够的,\(ans +ans\) 才是正解
Code
ll n, m, _;
int i, j, k;
//ll a[N];
string s[105];
int sz[105], p[105];
bool judge()
{
int ok = 1;
for(int i = 1; i <= n && ok; i ++){
if(p[i] >= sz[i]) continue;
ok = 0;
}
for(int i = 1; i < n && ok; i ++){
if(p[i] % sz[i] == p[i + 1] % sz[i + 1]) continue;
ok = 0;
}
return ok;
}
string go()
{
string ans = "";
while(true){
if(judge()) break;
for(int i = 1; i <= n; i ++){
ans += s[i][(p[i] ++) % sz[i]];
}
}
return ans;
}
char vis[30];
signed main()
{
IOS;
rush(){
cin >> n;
fill(vis, 0);
rep(i, 1, n){
cin >> s[i];
sz[i] = s[i].size();
p[i] = 0;
for(int j = 0; s[i][j]; j ++){
vis[s[i][j] - ‘a‘] = 1;
}
}
string ans = go();
//dbg(ans);
ans = ans + ans;
int len = ans.size();
int l = 0, r = 0, now = 0, cur = 0, res = 2e9;
for(int i = 0; i < 26; i ++){
if(vis[i]) cur ++;
vis[i] = 0;
}
while(true){
while(r < len && now < cur){
if(vis[ans[r] - ‘a‘] == 0) now ++;
vis[ans[r] - ‘a‘] ++;
r ++;
}
if(now < cur) break;
res = min(res, (r - l));
if(vis[ans[l] - ‘a‘] == 1) now --;
vis[ans[l] - ‘a‘] --;
l ++;
}
pd(res);
}
//PAUSE;
return 0;
}