题解：CF1845C Strong Password

mmmkkk111 · 2025-02-18 19:06:53 · 题解

贪心＋二分

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    string s;
    cin >> s;
    int m;
    cin >> m;
    vector<int> r(m + 1), l(m + 1);
    string sl, sr;
    cin >> sl >> sr;
    sl = ' ' + sl;
    sr = ' ' + sr;
    for (int i = 1; i <= m; i++)
    {
        l[i] = sl[i] - '0';
    }
    for (int i = 1; i <= m; i++)
    {
        r[i] = sr[i] - '0';
    }
    int n = s.size();
    s = ' ' + s;
    vector<int> mp[10];
    for (int i = 1; i <= n; i++)
    {
        mp[s[i] - '0'].push_back(i);
    }
    int max1 = -1;
    int max2 = -1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = l[i]; j <= r[i]; j++)
        {

            auto it = upper_bound(mp[j].begin(), mp[j].end(), max1);
            if (it == mp[j].end())
            {
                cout << "YES" << '\n';
                return;
            }
            else
            {
                max2 = max(max2, *it);
            }
        }
        max1 = max2;
    }
    cout << "NO" << '\n';
}
auto main() -> signed
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}