今日学习记录
1. Problem-1845C-cf
关键词：子序列自动机 贪心
问题分析：
核心思路:
子序列自动机
用于快速找子序列
O(n∣Σ∣+km)，其中 n 是目标的长度，∣Σ∣=26 是字符集合的大小，m 是s[i]的平均长度,k≥10^9（十亿）是 s 的个数,s 为要进行查找的子序列
贪心
题目中是要找到满足条件的非子序列,所以只需要找到一个例子就可以了,我们要尽量往后面找,在l[i]~r[i]中找第一个数,要使这个数尽量在后面位子记为 cur,然后再在 cur+1 后面再找,一直到cur==n为止,说明存在满足条件的非子序列,于是直接跳出循环输出就行
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
int T,n;
sr t,l,r;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>T;
while(T--){
cin>>t>>n>>l>>r;
int m = t.size();
vector<array<int,10>> nxt(m+1);
fill(nxt[m].begin(),nxt[m].end(),m);
for(int i = m-1;i>=0;i--){
nxt[i] = nxt[i+1];
nxt[i][t[i]-'0'] = i;
}
bool flage = true;
int ans = -1;
for(int i = 0;i<n;i++){
int index = ans+1;
for(char c = l[i];c<=r[i];c++){
ans = max(ans,nxt[index][c-'0']);
}
if(ans>=m){
cout<<"YES";
flage = false;
break;
}
}
if(flage) cout<<"NO";
cout<<endl;
}
return 0;
}学到的点：
- 子序列自动机