【题解】洛谷P14317「ALFR Round 11」A 浴眼盯真 (dingzhen) 题解

题目传送门

思路

如果一个字符串不是浴眼盯真,那么可以大致分为2种情况:

  1. 不包含26个字母(即1 2
  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;
}