cf1553D. Backspace

cf1553D. Backspace

题意：

有一个字符串A,现在将其一个一个输入至B中,在输入一个字符时,如果按下backspace,那么这个字符不会被键入,而且如果B不为空,则前一位(B.back)也会被删除,现给出一个字符串C,问能否得到一个B，使得B=C

题解：

为了通过a得到b，我们有可能需要去除a串的某段前缀，然后模拟余下部分得到b
枚举每种删除前缀的情况是很麻烦的。
那我们可以考虑将a和b反转进行考虑，反转后操作就变成1：输入当前字符 2：不输入当前字符和下一个字符
这样做，如果我们去执行操作2，去除了a的一段后缀，而a被反转过，相当于去除原本a的一段前缀。这样就解决了删除前缀很麻烦的事

代码：

// Problem: D. Backspace // Contest: Codeforces - Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1553/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // Data:2021-08-10 12:42:38#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime = clock(); freopen("in.txt","r",stdin);#endif } void Time_test(){#ifdef ONLINE_JUDGE#elseendTime = clock(); printf("\nRun Time:%lfs\n",(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif } int main() {//rd_test();int t;cin>>t;while(t--){string a,b;cin>>a>>b;reverse(a.begin(),a.end());reverse(b.begin(),b.end());int pos=0;bool f=0;for(auto op:a){if(f){f=0;continue;}if(op==b[pos])pos++;else f=1;if(pos==b.size())break;}if(pos==b.size())puts("YES");else puts("NO");}//Time_test(); }

总结

以上是生活随笔为你收集整理的cf1553D. Backspace的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。