【题解】洛谷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;
}
后续
提交到洛谷上没过,本来想改一下再交,结果题解给关了。。。