1 条题解

  • 0
    @ 2026-11-15 22:53:17

    已知字符串 t=s+s′t = s + s',其中 s′s' 为 ss 去除所有 a 后的结果。由于 ss 去除 a 后与 s′s' 相同,可以从前往后找出第一个位置,使得该位置前非 a 字符的个数与该位置后的总字符数相等,然后判断该位置前的子串与后缀去除 a 后是否一致即可,时间复杂度 O(n)\mathcal O(n)。

    也可以通过哈希判断每个可能的分界点后缀是否匹配,时间复杂度 O(n)\mathcal O(n) 或 O(nlog⁡n)\mathcal O(n\log n)。

    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int N=1000005;
    char buf[N],tmp[N],res[N];
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s",buf+1);
    		int len=strlen(buf+1),p=0;
    		for(int i=1;i<=len;++i)
    			if(buf[i]!='a')tmp[++p]=buf[i];
    		if(p==0){
    			puts(buf+1);
    			continue;
    		}
    		if(p&1){
    			puts("No solution!");
    			continue;
    		}
    		bool ok=1;
    		for(int i=1,j=p/2+1;j<=p;++i,++j)
    			if(tmp[i]!=tmp[j]){
    				puts("No solution!");
    				ok=0;
    				break;
    			}
    		if(ok){
    			int cnt=0,q=0,r=0;
    			for(int i=1;i<=len;++i){
    				if(buf[i]!='a')++cnt;
    				if(cnt==p/2+1){
    					for(int j=i;j<=len;++j)
    						if(buf[j]=='a'){
    							ok=0;
    							break;
    						}
    					break;
    				}
    				res[++q]=buf[i];
    			}
    			if(ok){
    				for(int i=1;i<=q;++i)putchar(res[i]);
    				putchar('\n');
    			}
    			else puts("No solution!");
    		}
    	}
    }
    

    信息

    ID
    222
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者