1 条题解
-
7
正如我在 这道题题解 中说的那样，一道恶心的大模拟，要分步做
考虑一下如何才能做到让一段字符串被删除后，后面的自动补位，自然而然想到在做括号匹配题时有过用 stack 解决的前例，显然在这里也可以。
第一步：判断栈顶串是否可被消除
因为题目要求提到过字符串 的长度小于 ，所以可以暴力从栈中取出 / 放回来判断。
第二步：取出与放回
如果取出来的串可以被消除，那就没必要放回去了，否则就按照顺序 push 回栈中。
第三步：结果施工
有一个坑点是，把结果从栈里倒出来时，结果是反着的，所以要再人为地翻转一次，才能出答案（说句实话我第一次提交忘记输出 ! 了）
代码：
#include<bits/stdc++.h> using namespace std; string s,rul[10],ans=""; stack<char> st; int n,k,flag=1; int main(){ freopen("matchgame.in","r",stdin); freopen("matchgame.out","w",stdout); cin>>n>>k>>s; for(int i=1;i<=k;i++) cin>>rul[i]; for(int i=0;i<n;i++){ st.push(s[i]); for(int j=1;j<=k;j++){ string zc=""; int e=rul[j].length(),u=st.size(); if(u>=e){ for(int p=0;p<e;p++){ zc+=st.pop(); st.top(); } reverse(zc.begin(),zc.end()); if(rul[j]!=zc){ for(int p=0;p<=e;p++) st.push(zc[p]); } } } } while(!st.empty()){ ans+=st.top(); st.pop(); } if(!ans.length()) cout<<"！"; else for(int i=ans.length()-1;i>=0;i--) cout<<ans[i]; return 0; }复杂度分析：，在最坏情况下是 ，可以通过
塞了仨 bug
-
luyunyi @ 2024-10-5 14:53:55
🎉️
-
dongzhengshuo
@ 2024-10-5 15:33:21
👍
-
corey0208
@ 2024-10-5 15:37:30
注意叹号是!不是！
-
dongzhengshuo
@ 2024-10-5 16:52:39
-
dongzhengshuo
@ 2024-10-5 16:54:22
zc+=st.top(); st.pop();
-
zoudonghan @ 2024-10-5 16:54:52
using namespace std; string s, rul[10], ans = ""; stack st; int n, k, flag = 1; int main() { freopen("matchgame.in", "r", stdin); freopen("matchgame.out", "w", stdout); cin >> n >> k >> s; for (int i = 1; i <= k; i++) cin >> rul[i]; for (int i = 0; i < n; i++) { st.push(s[i]); for (int j = 1; j <= k; j++) { string zc = ""; int e = rul[j].length(), u = st.size(); if (u >= e) { for (int p = 0; p < e; p++) { zc += st.top(); st.pop(); } reverse(zc.begin(), zc.end()); if (rul[j] != zc) { for (int p = 0; p <= e; p++) st.push(zc[p]); } } } } while (!st.empty()) { ans += st.top(); st.pop(); } if (!ans.length()) cout << "!"; else for (int i = ans.length() - 1; i >= 0; i--) cout << ans[i]; return 0; } 可能是完整版（没交） -
dongzhengshuo
@ 2024-10-5 16:56:31
-
linchufan
@ 2024-10-5 16:58:41
正解：
#include<bits/stdc++.h> using namespace std; string s,rul[10],ans=""; stack<char> st; int n,k,flag=1; int main(){ freopen("matchgame.in","r",stdin); freopen("matchgame.out","w",stdout); cin>>n>>k>>s; for(int i=1;i<=k;i++) cin>>rul[i]; for(int i=0;i<n;i++){ st.push(s[i]); for(int j=1;j<=k;j++){ string zc=""; int e=rul[j].length(),u=st.size(); if(u>=e){ for(int p=0;p<e;p++){ zc+=st.top(); st.pop(); } reverse(zc.begin(),zc.end()); if(rul[j]!=zc){ for(int p=0;p<e;p++) st.push(zc[p]); } } } } while(!st.empty()){ ans+=st.top(); st.pop(); } if(!ans.length()) cout<<"!"; else for(int i=ans.length()-1;i>=0;i--) cout<<ans[i]; return 0; } -
dongzhengshuo
@ 2024-10-5 16:59:10
-
dongzhengshuo
@ 2024-10-5 16:59:35
申书源 有人破解了你的bug
-
corey0208
@ 2024-10-5 17:04:37
bug1:
for(int p=0;p<=e;p++) st.push(zc[p]);应为
for(int p=0;p<e;p++) st.push(zc[p]);bug2:
if(!ans.length()) cout<<"！";！应为!
bug3:
for(int p=0;p<e;p++){ zc+=st.pop(); st.top(); }应为
for(int p=0;p<e;p++){ zc+=st.top(); st.pop(); }
-
申书源
LV 8
@ 2024-10-5 14:41:15
