526互联

Educational Codeforces Round 151 (Rated for Div. 2) C. Strong Password

发布时间 2023-07-07 17:14:31作者: 突破铁皮

题目翻译，给定t组数据，每组数据包含一个字符串s，两个长度为m的字符串l和r，要求判断是否存在一个长度为m的字符串res,满足l[i]<=res[i]<=r[i]（i->0~m)且不是s的子序列

贪心

首先对于所有满足l<res<r的字符串，我们只需判断是否存在一个字符串不是子序列即可，那么我们让res成为子序列的可能性最小

如何得到最优的字符串呢，我们发现对于res[i]来说可以从l[i]到r[i]中任意选择，对于第i个字符，我们求得在经过i-1次选择后，res[i]的选项中在s中首次出现的位置，然后在所有首次出现的位置中选那个首次位置最靠后的字符串，这样可以保证选择完第i个字符后，s中可以选择的字符数量最少，因此成为子序列的可能性最小，因为每次都是选中首次出现的所以不用担心前面会有重复的

判断条件，当q[j]的长度为0时，说明不存在该子序列

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
string s,l,r;
int t,m;
queue<int> q[10];
void solve(){
	for(int i=0;i<10;i++)
	while(q[i].size()) q[i].pop();
	cin>>s;
	cin>>m;
	cin>>l>>r;
	for(int i=0;i<s.length();i++){
		q[s[i]-'0'].push(i);
	}
	int last=-1;//记录上次选中的字符位置 
	for(int i=0;i<m;i++){
		for(int j=l[i]-'0';j<=r[i]-'0';j++){
			if(q[j].size()==0){//说明该可选方案不为子序列 
				cout<<"YES"<<endl;
				return;
			}
			int u=q[j].front();
			if(u>last){
				last=u;
			}
		}
		for(int j=0;j<10;j++){//更新首次出现的位置，当last越大时每个q减少的越多，只要有一个q[j]减少为0，就不能为子序列 
			while(q[j].size()&&q[j].front()<=last) q[j].pop();
		}
	}
	cout<<"NO"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
		cin>>t;
		while(t--){
		solve();
	}
}