比赛 20241021 评测结果 AAAAAAAAAAAAEE
题目名称 子序列 最终得分 86
用户昵称 flyfree 运行时间 0.530 s
代码语言 C++ 内存使用 3.60 MiB
提交时间 2024-10-21 08:37:54
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 256
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll l,r,lst;
	ll s[2];
}tr[300*110];
ll idx,lena,len,n;
string a,s;
ll rot[100010];
void build(ll &now,ll l,ll r){
	now=++idx;
	tr[now].l=l,tr[now].r=r;
	if(l==r){
		tr[now].lst=-1;
		return;
	}
	ll mid=(l+r)/2;
	build(tr[now].s[0],l,mid);
	build(tr[now].s[1],mid+1,r);
}
void ad_(ll &now,ll p,ll loc,ll val){
	now=++idx;
	tr[now].l=tr[p].l,tr[now].r=tr[p].r;
	if(tr[now].l==tr[now].r){
		tr[now].lst=val;
		return;
	}
	ll mid=(tr[now].l+tr[now].r)/2;
	if(loc<=mid){
		tr[now].s[1]=tr[p].s[1];
		ad_(tr[now].s[0],tr[p].s[0],loc,val);
	}else{
		tr[now].s[0]=tr[p].s[0];
		ad_(tr[now].s[1],tr[p].s[1],loc,val);
	}
}
ll re_(ll now,ll loc){
	if(!now)return -1;
	if(tr[now].l==tr[now].r)return tr[now].lst;
	ll mid=(tr[now].l+tr[now].r)/2;
	if(loc<=mid)return re_(tr[now].s[0],loc);
	else return re_(tr[now].s[1],loc);
}
int main(){
	freopen("subsequence.in","r",stdin);
	freopen("subsequence.out","w",stdout);
	cin>>a;
	lena=a.length();
	a="0"+a;
	build(rot[lena+1],1,N);
	for(int i=lena;i;i--){
		ad_(rot[i],rot[i+1],a[i],i);
	}
	n=read();
	for(int i=1;i<=n;i++){
		cin>>s;
		len=s.length();
		s="0"+s;
		ll now=0;
		for(int j=1;j<=len;j++){
			now=re_(rot[now+1],s[j]);
			if(now==-1)break;
		}
		if(now==-1)cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}