【题解】洛谷P14317「ALFR Round 11」A 浴眼盯真 (dingzhen) 题解
思路
如果一个字符串不是浴眼盯真,那么可以大致分为2种情况:
- 不包含26个字母(即
1 2) - 包含26各字母,但这26个字母不在同一个非本身的子串内(即
2)
当然,肯定是不会包含情况1的,因为如果不包含26个字母则26个字母不可能在同一个非本身的子串内。
那么我们可以通过来看这个字符串是否满足以上2种情况,如果满足则不为浴眼盯真,否则为浴眼盯真。
情况检查分析
首先看是否满足情况1,这一点非常好写,只需要遍历一下字符串,使用一个桶来进行统计即可。
接下来看是否满足情况2。逐个字串检查肯定不行,我们可以采用一个非常简单的贪心策略。我们要想让一个字符串的字串(不包含自己本身)包含的字符种类尽可能多,那么我们可以将该字符串去头或者去尾。也就是说要满足情况2,那么就字符串的开头和结尾的字符在字符串中只出现一次,这里就可以用到我们计算检查情况1时计算出的桶。
代码
#include<bits/stdc++.h>
using namespace std;
int mp[30];
void sol(){
memset(mp,0,sizeof mp);
string s;
cin >> s;
int n = s.size();
// 检查情况1
for(int i = 0;i < n;i++){
mp[s[i]-'a']++;
}
for(int i = 0;i < 26;i++){
if(!mp[i]){
cout << "No\n1 2\n";
return;
}
}
// 检查情况2
if(mp[s[0]-'a'] == 1 && mp[s[n-1]-'a'] == 1){
cout << "No\n2\n";
return;
}
cout << "Yes\n";
}
int main(){
int t;
cin >> t;
while(t--){
sol();
}
return 0;
}