题解：P14317 「ALFR Round 11」A 浴眼盯真 (dingzhen)

· · 题解

思路

考虑用桶记录，细节看代码。

这里重点讲代码第 20 行。

只需检查去掉第一个字符或去掉最后一个字符的 s 是否满足条件 1。

原因是若去掉第一个字符或去掉最后一个字符的 s 包含 26 个不同字母，则条件 2 成立。

若两者都不满足，则任何非自身子串都无法同时包含所有 26 个字母。

因为缺少的字母仅存在于字符串的首尾，非自身子串无法同时覆盖首尾。

所以判断 s 的第一个字母与最后一个字母是否都只出现一次即可。

时间复杂度 O(\sum n)。

代码

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define f(n) for(int i=1;i<=n;i++)
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int T,len,t[200],cnt;
string s;
bool if1(){
    cnt=0;//记录出现过几个字符
    for(int i='a';i<='z';i++)cnt+=(1&&t[i]);//若t[i]不是0，即s中存在字符i，cnt就+1 
    return (cnt==26);//若26个字母都有则返回1 
}
signed main(){
    IOS;cin>>T;
    while(T--){
        memset(t,0,sizeof(t));//多测未清空，害的作者2024CSP-J挂100pts 
        cin>>s,len=s.length(),s=" "+s;//获取字符串长度 
        f(len)t[s[i]]++;//用桶记录各个字符出现的次数 
        if(if1()&&(t[s[1]]!=1||t[s[len]]!=1))cout<<"Yes\n"; 
        else if(if1())cout<<"No\n2\n";//易得若满足2，必满足1
        else cout<<"No\n1 2\n";
    }
    return 0;
}