比赛 |
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;
}