2017ACM ICPC Asia Regional-Daejeon H-Rock Paper Scissors[ FFT]

题目大意

给你两个字符串，N,M |N|>|M|，经过转换之后，问你，连续的一段，能够匹配上的最大元素个数。
n <1e5

题目分析

题目求区间内匹配数最大。考虑区间有n^2个，暴力做显然会T，所以这里考虑，用FFT
将第二个串反置，这样我们相邻位置的匹配，可以转化为，对应位置的匹配

如下图：

此时我们发现，最大匹配数 就是 i+j的系数

因此，我们分别求R,S,P的匹配，三次FFT之后将系数加起来，求一个最大值即可

代码分析

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e6+50;
const double pi = acos(-1.0);
typedef long long ll;
struct Complex
{
	double x,y;
	Complex(double _x = 0,double _y=0)
	{
		x=_x; y=_y;
	}
	Complex operator +(const Complex &b) const
	{
		return Complex(x+b.x,y+b.y);
	}
	Complex operator -(const Complex &b) const
	{
		return Complex(x-b.x,y-b.y);
	}
	Complex operator * (const  Complex&b) const
	{
		return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
	}
}a[maxn],b[maxn];
int S,T,n,m,L,R[maxn],ans[maxn]; //S 表示A序列的长度 ,T表示B序列的长度
//n 表示 >=S+T 的2的幂次 L表示幂次 R数组是旋转数组，ans答案数组
ll F[maxn];
double f[maxn][3],g[maxn][3];// f,g数组是整数转化为实数的数组 
char x[maxn],y[maxn];
void FFT(Complex a[],int opt)
{
	for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);// 翻转数组
	for(int k=1;k<n;k<<=1)
	{
		Complex wn = Complex(cos(pi/k),opt*sin(pi/k));
		for(int i=0;i<n;i+=(k<<1))
		{
			Complex w = Complex(1,0);
			for(int j=0;j<k;j++,w=w*wn)
			{
				Complex x = a[i+j],y = w*a[i+j+k];
				a[i+j] = x+y;
				a[i+j+k] = x-y;
			}
		}
	}
} 
void calc(int opt)
{
	FFT(a,1);
	FFT(b,1);
	for(int i=0;i<=n;i++) a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=0;i<=n;i++) F[i] = (ll) (a[i].x/n+0.5)*opt;
	
}
int main()
{
	
	scanf("%d%d",&S,&T);
	S--,T--;
	scanf("%s%s",x,y);
	for(int i=0;i<=S;i++)
	{
		if(x[i]=='R') f[i][0] = 1.0;
		if(x[i]=='S') f[i][1] = 1.0;
		if(x[i]=='P') f[i][2] = 1.0;
	}
	for(int i=0;i<=T;i++)
	{
		if(y[i]=='R') g[T-i][1] = 1.0;
		if(y[i]=='S') g[T-i][2] = 1.0;
		if(y[i]=='P') g[T-i][0] = 1.0;
	}
//	for(int i=0;i<=T;i++) scanf("%lf",&g[i]);
	m=T+S; L=0;
	for(n=1;n<=m;n<<=1) L++;
	for(int i=0;i<n;i++) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));
	for(int kase=0;kase<3;kase++)
	{
		for(int i=0;i<=n;i++)
		{
			a[i]= Complex(1.0*f[i][kase],0.0);
			b[i]= Complex(1.0*g[i][kase],0.0);
		}
		calc(1);
		for(int i=0;i<=S+T;i++) {
			ans[i]+=F[i];
		//	printf("%lld ",F[i]);
		}
	//	printf("\n");
	}
	int allans=0;
	for(int i=T;i<=S+T;i++) allans= max(allans,ans[i]);
	printf("%d\n",allans); 
	return 0;
} 

/*
12 4
PPPRRRRRRRRR
RSSS

12 4
RRRRRRRRRSSS
RRRS



*/