社区讨论

求助,有人知道我的eps为什么开到20000才过么

P4173残缺的字符串参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lq9hcmvy
此快照首次捕获于
2023/12/17 20:45
2 年前
此快照最后确认于
2023/12/17 23:31
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int N=3e5+5;
const db pi=acos(-1);
struct comp{
	db a,b;
	comp(){
	}
	comp(db _a,db _b){
		a=_a,b=_b;
	}
	friend comp operator+(comp x,comp y){
		return comp(x.a+y.a,x.b+y.b);
	}
	friend comp operator-(comp x,comp y){
		return comp(x.a-y.a,x.b-y.b);
	}
	friend comp operator*(comp x,comp y){
		return comp(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);
	}
};
int r,c,n;
bool vis[N<<2];
comp a[N<<2],b[N<<2],ans[N<<2];
void fft(comp *a,int len,int opt=1){
	if(len==1)return;
	comp* a0=new comp[len/2];
	comp* a1=new comp[len/2];
	for(int i=0;i<len;i+=2){
		a0[i/2]=a[i];
		a1[i/2]=a[i+1];
	}
	fft(a0,len>>1,opt);
	fft(a1,len>>1,opt);
	comp w=comp(1,0),w_n=comp(cos(2*pi/len),opt*sin(2*pi/len));
	for(int i=0;i<len/2;++i){
		a[i]=a0[i]+w*a1[i];
		a[i+len/2]=a0[i]-w*a1[i];
		w=w*w_n;
	}
	delete[]a0;
	delete[]a1;
	return;
}
string s1,s2;
double A[N<<2],B[N<<2]; 
void work(){
	int n,m;
	cin>>n>>m>>s1>>s2;
	reverse(s1.begin(),s1.end());
	for(int i=0;i<n;++i)A[i]=(s1[i]=='*')?0:(s1[i]-'a'+1);
	for(int i=0;i<m;++i)B[i]=(s2[i]=='*')?0:(s2[i]-'a'+1);
	int lim=1;
	while(lim<=2*m)lim<<=1;
	for(int i=0;i<=lim;++i)a[i]=comp(A[i]*A[i]*A[i],0);
	for(int i=0;i<=lim;++i)b[i]=comp(B[i],0);
	fft(a,lim,1);fft(b,lim,1);
	for(int i=0;i<=lim;++i)ans[i]=ans[i]+a[i]*b[i];
	for(int i=0;i<=lim;++i)a[i]=comp(A[i],0);
	for(int i=0;i<=lim;++i)b[i]=comp(B[i]*B[i]*B[i],0);
	fft(a,lim,1);fft(b,lim,1);
	for(int i=0;i<=lim;++i)ans[i]=ans[i]+a[i]*b[i];
	for(int i=0;i<=lim;++i)a[i]=comp(A[i]*A[i],0);
	for(int i=0;i<=lim;++i)b[i]=comp(B[i]*B[i],0);
	fft(a,lim,1);fft(b,lim,1);
	for(int i=0;i<=lim;++i)ans[i]=ans[i]-a[i]*b[i]*comp(2,0);
	fft(ans,lim,-1);
	int cnt=0;
	for(int i=s1.size()-1;i<s2.size();++i)if(abs(ans[i].a)<=20000)cnt++;
	cout<<cnt<<'\n';
	for(int i=s1.size()-1;i<s2.size();++i)if(abs(ans[i].a)<=20000)cout<<i-n+2<<' ';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);	
	int T=1;
//	cin>>T;
	while(T--)work();
	return 0; 
}
if(fabs(abs(ans[i].a))<20000)
就是这一句话。。而且我样例都过不了还能水过去。。
虽然某位学长在讨论区里提出过一样的问题,但是好像现在也没有结果(((

回复

0 条回复,欢迎继续交流。

正在加载回复...