2022牛客寒假算法基础集训营3——I 智乃的密码

原题链接

思路(双指针)

• $ii$: 枚举密码的左边界
• $j-1j-1$: 表示第一个满足条件3(包含至少三种字符)的右边界
• $\mathrm{对}\mathrm{每}\mathrm{个}i,j,\mathrm{合}\mathrm{法}\mathrm{左}\mathrm{边}\mathrm{界}l=max(j-1,i+L-1),\mathrm{合}\mathrm{法}\mathrm{右}\mathrm{边}\mathrm{界}r=min(n-1,i+R-1)对每个i,j,\; 合法左边界l\; =\; max(j\; -\; 1,\; i\; +\; L\; -\; 1),\; 合法右边界r\; =\; min(n\; -\; 1,\; i\; +\; R\; -\; 1)$
• 算法的正确性：对于每个$ii$, 当$i+1i+1$时, $jj$的位置只能增加不能减少, 因为$j-1j-1$是第一个满足条件的右边界, $i+1i+1$, 字符减少了$11$个, 要么仍然符合条件($jj$不变)，要么不符合条件($jj$增加)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e5 + 10;
int n, L, R;
int cnt[4];
int type[N];

// 是否至少包括三类字符
bool check()
{
    return ((cnt[0] > 0) + (cnt[1] > 0) + (cnt[2] > 0) + (cnt[3] > 0)) >= 3;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> L >> R;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        if (isdigit(s[i]))
            type[i] = 0;
        else if (islower(s[i]))
            type[i] = 1;
        else if (isupper(s[i]))
            type[i] = 2;
        else
            type[i] = 3;
    }

    LL ans = 0;
    for (int i = 0, j = 0; i < n; i ++)
    {
        // while循环得到j: 第一个满足条件的(右边界+1)
        while (j <= n && !check())
        {
            // 先把s[j]的类型记录, 再j++. 这是因为s[0]的类型也要算到cnt数组内, 先j++的话, s[0]的类型没有记录
            if (j < n) // j == n时s[j]不存在, type[j]无意义
                cnt[type[j]]++;
            j++;
        }

        int r = min(n - 1, i + R - 1); // 右边界
        int l = max(j - 1, i + L - 1); // 左边界
        if (j <= n && check())
        {
            ans += max(0,  r - l + 1);
        }
        cnt[type[i]]--;
    }
    cout << ans << '\n';

    return 0;
}