第一届程序设计竞赛题解（J题）

题目描述：

一天，陈梓豪学长去注册账号。
陈梓豪学长发现网站的密码必须符合下面三个条件
密码中应该至少包括大写英文字母、小写英文字母、数字、特殊符号这四类字符中的三种。
密码的长度不少于 L 个字符，并且不多于 R 个字符。
密码是仅包含大小写英文字母、数字、特殊符号的字符串。
特殊字符，是指非大小写字母、数字以及空格回车等不可见字符的可见字符，包括但不限于 “!@#^()_+*” 。

现在，陈末给了陈梓豪学长一个长度大小为 N 的字符串 S ，陈梓豪学长想知道 S 串中有多少个子串是一个符合条件的密码。
请你帮助陈梓豪学长统计符合条件的密码数目。

子串是指字符串中某一段连续的区间，例如对于字符串 “aqwerdf” 来说，“aqw”, “qwe” 都是它的子串，而 “aqr” 不是它的子串。

输入描述：

第一行输入三个正整数 N, L, R (1 <= N <= 10⁵), (1 <= L <= R <= N)，表示字符串的长度，以及合法字符的长度限制 。
第二行输入一个长度为 N 的字符串 S 。
保证字符串只包含大小写英文字母、数字、特殊符号。

输出描述：

一个整数，表示有多少个子串是一个合法的密码

示例：

输入：
6 2 6
abcD2!
输出：
7
说明：
abcD2
bcD2
cD2
D2!
abcD2!
bcD2!
cD2!

思路：
首先使用一个 flag[5] 数组判断字符种类，flag[1] ~ flag[4] 表示四种字符，flag[0] 表示已有的字符种类。
要求求出符合条件的子串密码，我们可以使用快慢指针来一步步遍历字符串，每次符合条件则加一，最后输出结果。

AC代码如下：

#include 
using namespace std;
const int N = 1e5 + 5;

int n, L, R;
int flag[5];
char s[N];

//判断字符的函数
int P(int x)
{
    if (s[x] >= 'A' && s[x] <= 'Z')
        return 1;
    if (s[x] >= 'a' && s[x] <= 'z')
        return 2;
    if (s[x] >= '0' && s[x] <= '9')
        return 3;
    //其他字符则返回4
    return 4;
}

int main()
{
    //初始化
    scanf("%d %d %dn", &n, &L, &R);
    scanf("%s", s + 1);

	//快慢指针
    int l = 1, r = 0;
    int ans = 0;
    while (l <= n){
        while (r - l + 1 <= R && r < n){
        	//右指针先右移一位后，判断是哪种字符
            int p = P(r++);

			//统计字符种类，若没有该字符，则加一，标记为已存在
            if (flag[p] == 0)
                flag[0]++;

			//该字符数量加一
            flag[p]++;

			//若子串中字符种类有三种及以上，且符合合法字符的长度限制
            if (flag[0] >= 3 && r - l + 1 >= L){
                ans += min(n - r + 1, R - (r - l + 1) + 1);
                break;
            }
        }

		//右移左指针
        int p = P(l++);

		//若该种字符已存在，右移，字符种类减一
        if (flag[p] == 1)
            flag[0]--;

		//字符数量减一
        flag[p]--;

        if (flag[0] >= 3 && r - l + 1 >= L)
            ans += min(n - r + 1, R - L + 1);
    }

    printf("%dn", ans);

    return 0;
}