神奇问题求条 玄关
  • 板块灌水区
  • 楼主_KMnO4_
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/20 18:47
  • 上次更新2025/1/20 18:51:42
查看原帖
神奇问题求条 玄关
1211186
_KMnO4_楼主2025/1/20 18:47

rt,这份代码在本地都没有问题,一提交甚至在洛谷IDE上就炸,题目是P4824

#include<bits/stdc++.h>
#define N 1000005
#define ull unsigned long long
using namespace std;

int n,m,cnt;
stack<char>s;
char S[N],T[N];
ull hashT,p[N],hashS[N];
ull gethash(int l,int r){
	return hashS[r]-hashS[l-1]*p[r-l+1];
}
int main(){
	scanf(" %s %s",S+1,T+1);
	n=strlen(S+1);
	m=strlen(T+1);
	p[0]=1;
	for(int i=1;i<=m;i++){
		p[i]=p[i-1]*1331;
		hashT=hashT*1331+(T[i]-'a');
	}
	for(int i=1;i<=n;i++){
		hashS[++cnt]=hashS[cnt-1]*1331+(S[i]-'a');
		s.push(S[i]);
		if(s.size()<m)continue;
		if(gethash(cnt-m+1,cnt)==hashT){
			for(int j=1;j<=m;j++){
				s.pop();
				cnt--;
			}
		}
	}
	n=0;
	while(s.size()){
		S[++n]=s.top();
		s.pop();
	}
	for(int i=n;i;i--)printf("%c",S[i]);
    return 0;
}
2025/1/20 18:47
加载中...