正題

題目鏈接:http://noip.ybtoj.com.cn/contest/86/problem/2

---

題目大意

給兩個(gè)字符串，第一個(gè)中的$?$號(hào)可以替換為若干個(gè)（可以為0個(gè)）相同的它的前一個(gè)字符。求能否構(gòu)成第二個(gè)字符串。

---

解題思路

把所有的$?$號(hào)去掉然后在有的$?$號(hào)的連續(xù)相同字符后面加上一個(gè)$?$。然后就可以暴力判斷了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e4+10; int T,n,m; char s[N],t[N]; int main() {freopen("strinq.in","r",stdin);freopen("strinq.out","w",stdout);scanf("%d",&T);while(T--){scanf("%s",s+1);n=strlen(s+1);scanf("%s",t+1);m=strlen(t+1);int last=0,cnt=0,tail=0;bool flag=0;for(int i=1;i<=n;i++){if(last&&(s[i]==last||s[i]=='*'))cnt+=(s[i]==last); else if(s[i]=='*')last=s[i-1],cnt=0;else if(last){for(int j=1;j<=cnt;j++)s[++tail]=last;last=0;s[++tail]='*';s[++tail]=s[i];}else s[++tail]=s[i];}if(last){for(int j=1;j<=cnt;j++)s[++tail]=last;s[++tail]='*';}n=tail;tail=1;for(int i=1;i<=n;i++){if(s[i]!='*'&&tail>m){flag=1;break;}else if(s[i]==t[tail])tail++;else if(s[i]=='*'){while(s[i]=='*'&&t[tail]==s[i-1])tail++;}else{flag=1;break;}}if(flag||tail<=m)printf("No\n");else printf("Yes\n");} }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#20060-[NOIP2020模拟赛B组Day3]字串修改【模拟】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。