1 条题解
-
0徐静雨 (xujingyu) LV 8 @ 2024-8-6 11:53:56
哈希太难调,没成功直接放弃……
首先,暴力很好想,直接枚举哪一个是插入的,把它删掉,再以中间为断点隔开两个字符子串,判断是否相同即可。注意如果 为偶数,那么就是没有插入,直接输出
-2
。好心的测试数据给了 分。#include <bits/stdc++.h> using namespace std; int n,cnt; string s,ans,out; bool flag; signed main() { cin >> s; n = s.size(); if(n % 2 == 0){printf("-2");return 0;} for(int x = 0;x <= n / 2;x++)//哪个是插入的 { char c = s[x]; s[x] = '.'; flag = true; for(int i = 0,j = n / 2 + 1;i <= n / 2;i++,j++) { if(s[i] == '.') i++;//跳过 if(s[i] != s[j]) { flag = false;//不可能 break; } ans += s[i]; } if(flag && out != ans){cnt++;out = ans;} if(cnt > 1){printf("-1");return 0;}//不止一个 ans = ""; s[x] = c; } for(int x = n / 2;x < n;x++)//与上面一样 { char c = s[x]; s[x] = '.'; flag = true; for(int i = 0,j = n / 2;i < n / 2;i++,j++) { if(s[j] == '.') j++; if(s[i] != s[j]) { flag = false; break; } ans += s[i]; } if(flag && out != ans){cnt++;out = ans;} if(cnt > 1){printf("-1");return 0;} ans = ""; s[x] = c; } if(cnt) cout << out; else printf("-2"); return 0; } /* 11 ababcabaabc aba?? */
那么考虑优化,枚举哪个是插入的耗时过多,可以考虑直接断开两段,遇到不一样的就不管,最后看看有多少相同的即可。
#include <bits/stdc++.h> using namespace std; int n,cnt; string s,o,t,ans; signed main() { cin >> s; n = s.size(); if(n % 2 == 0){printf("-2");return 0;} o = s.substr(0,n / 2);//直接断 t = s.substr(n - n / 2,n / 2); int i,j; for(i = 0,j = n / 2;i < n / 2 && j < n;j++) if(o[i] == s[j]) i++;//一样的个数 if(i == n / 2){cnt++;ans = o;}//有答案了 for(i = 0,j = 0;i < n / 2 && j < n - n / 2;j++) if(t[i] == s[j]) i++;//同上 if(i == n / 2) { cnt++; if(cnt > 1 && ans != t){printf("-1");return 0;}//答案不唯一 ans = t; } if(!cnt) printf("-2"); else cout << ans; return 0; }
- 1
信息
- ID
- 2897
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 45
- 已通过
- 3
- 上传者