Game link

2022 Niuke winter vacation algorithm basic training camp 3

1. Zhinai's password

Title Description

Zhinai went to register an account. He found that the password of the website must meet the following conditions

• A password is a string that contains only uppercase and lowercase English letters, numbers, and special symbols.
• The length of the password shall be no less than \ ({L} \) characters and no more than \ ({R} \) characters.
• The password should at least include three of the four types of characters: ① uppercase English letters, ② lowercase English letters, ③ numbers and ④ special symbols.
  The so-called special characters refer to the visible characters of invisible characters such as non uppercase and lowercase letters, numbers and space carriage return, including but not limited to "~! @#$% ^ & * () +".

Now zhinai has a string \ ({S} \) with a length of \ ({N} \). She wants to know how many substrings in the {S}S string are qualified passwords. Please help zhinai count the number of qualified passwords.
Substring refers to a continuous interval in a string. For example, "ABC" and "CDE" are all substrings of the string "abcde", while "ace" is not its substring.

Enter Description:

On the first line, enter three positive integers \ ({N,L,R(1\le N \le 10^5,1\le L\le R \le N)} \), indicating the length of {S}S string. The length of legal password should be between \ ({l} \) and \ ({r} \).
Enter a string \ ({S} \) with a length of \ ({N} \) in the next line. The string only includes four types of characters: ① uppercase English letters, ② lowercase English letters, ③ numbers and ④ special symbols.

Output Description:

Only one integer per line indicates how many substrings are a legal password.

input

10 6 8
asdfeg111*

output

3

explain

"eg111","feg111","dfeg111*"

Problem solving ideas

Double pointer

First, build a sliding window of \ (L \) length, that is, dynamic maintenance, considering the contribution of each entry window to the answer,

• Time complexity: \ (O(n) \)

code

// Problem: zhinai's password
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23478/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

// %%%Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,L,R,Left[4][N];
char s[N];
inline int get(char &c)
{
	if(c>='A'&&c<='Z')return 0;
	if(c>='a'&&c<='z')return 1;
	if(c>='0'&&c<='9')return 2;
	return 3;
}
int main()
{
	scanf("%d%d%d",&n,&L,&R);
	scanf("%s",s+1);
	int lst[4]={0};
	for(int i=1;i<=n;i++)
	{
		if(get(s[i])==0)lst[0]=i;
		if(get(s[i])==1)lst[1]=i;
		if(get(s[i])==2)lst[2]=i;
		if(get(s[i])==3)lst[3]=i;
		Left[0][i]=lst[0];
		Left[1][i]=lst[1];
		Left[2][i]=lst[2];
		Left[3][i]=lst[3];
	}
	LL res=0;
	for(int r=L,l=1;r<=n;r++)
	{
		if(r-l+1>R)l++;
		int a[4]={Left[0][r],Left[1][r],Left[2][r],Left[3][r]};
		sort(a,a+4);
		if(a[1]<l)continue;
		res+=min(a[1],r+1-L)-l+1;
	}
	printf("%lld",res);
	return 0;
}