1 条题解

  • 0
    @ 2024-8-6 11:53:56

    哈希太难调,没成功直接放弃……

    首先,暴力很好想,直接枚举哪一个是插入的,把它删掉,再以中间为断点隔开两个字符子串,判断是否相同即可。注意如果 nn 为偶数,那么就是没有插入,直接输出 -2。好心的测试数据给了 88\color{#b0d628} 88 分。

    #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
    上传者