T3 strong password
- 就是对于输入的每一个 \(l,r\) ,我们遍历 \(s[l]~s[r]\)，对于每次遍历，我们设置一个临时指针 \(cur\) ,然后通过指针右移寻找所需要的值
- 在外面我们弄两个指针，分别代表每次遍历 \([l,r]\) 的区间的指针 \(nmx\) 和全局指针 \(mx\)
我们用临时指针更新单次区间的指针，易得递推式为 \(nmx = max(cur, nmx)\)，因为总不可能回头
用 \(nmx\) 更新 \(mx\) ,易得 \(mx=nmx+1\) ,因为 \(nmx\) 这个位置已经遍历过了
- 最后判断 \(mx\) 是否大于 \(n\),因为因为如果大于 \(n\) 说明找东西找到外面了，所以没找到输出 YES,否则输出 NO
#include <bits/stdc++.h>
using namespace std;
const int N = 11451454;
int l[N], r[N];
void solve()
{
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
string s;
cin >> s;
int n = s.size();
int m;
cin >> m;
int mx = 0;
string l, r;
cin >> l >> r;
// cout << l << ' ' << r << endl;
for (int i = 0; i < m; i++)
{
int nmx = mx, li = l[i] - '0', ri = r[i] - '0';
for (int j = li; j <= ri; j++)
{
int cur = mx;
while (cur < n && s[cur] != (j + '0'))
cur += 1;
nmx = max(nmx, cur);
}
mx = nmx + 1;
}
if (mx > n)
puts("YES");
else
puts("NO");
}