- 來源:2094(Div4)D-CF
- 題意:給定兩個(gè)僅由
L與R組成的字符串 \(p\) 和 \(s\),對(duì)于原字符串中的每個(gè)字符,可進(jìn)行如下操作:在左側(cè)或右側(cè)復(fù)制該字符,復(fù)制出的字符不可進(jìn)行操作。每個(gè)字符最多只能操作 \(1\) 次,也可不操作。判斷 \(s\) 是否為經(jīng)過操作 \(p\) 后所得到。
- 關(guān)鍵詞:模擬(簽到)
- 題解:先預(yù)處理去重,并計(jì)數(shù)在該段內(nèi)重復(fù)次數(shù)。若去重后的數(shù)組大小不相等則直接無解,否則逐位比較數(shù)組:若出現(xiàn)字符不同則無解,若重復(fù)次數(shù)\(s<p\)或\(s>2p\)則無解,其他情形則有解。
- Fun Fact:2024 ICPC香港站題目LRString為本題的Hard版,博主也寫過該題題解,感興趣請(qǐng)移步
- 代碼:
#include<bits/stdc++.h>
using namespace std;
using pci=pair<char,int>;
#define fi first
#define se second
void solve(){
string p,s;cin>>p>>s;
vector<pci>pp,ss;
int i=0;
while(i<p.size()){
int j=i;
while(j<p.size()&&p[j]==p[i]) j++;
pp.push_back({p[i],j-i});
i=j;
}
i=0;
while(i<s.size()){
int j=i;
while(j<s.size()&&s[j]==s[i]) j++;
ss.push_back({s[i],j-i});
i=j;
}
if(pp.size()!=ss.size()) cout<<"No\n";
else{
for(int i=0;i<pp.size();i++)
if(pp[i].fi!=ss[i].fi||ss[i].se<pp[i].se||ss[i].se>(pp[i].se<<1)){
cout<<"No\n";
return;
}
cout<<"Yes\n";
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
int t=1;cin>>t;
while(t--) solve();
return 0;
}