2 条题解
-
1Takagi-san (njnu19200437) LV 10 MOD @ 2021-04-18 17:02:38
化环为链,FFT做字符串匹配即可。
Code:#include<bits/stdc++.h> using namespace std; #define ll long long int //Header namespace fft { const double pi=acos(-1); int limit=1,l=0; struct cp{//complex double r,i; cp(double real=0,double img=0){r=real;i=img;} void set(double real=0,double img=0){r=real;i=img;} cp operator+(const cp& a){return cp(r+a.r,i+a.i);} cp operator-(const cp& a){return cp(r-a.r,i-a.i);} cp operator*(const cp& a){return cp(r*a.r-i*a.i,r*a.i+i*a.r);} }; void FFT(vector<cp> &a,int type) { vector<int>r(limit+1); //int r[limit+1];r[0]=0; for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1 | (i&1)<<(l-1)); for(int i=0;i<limit;i++)if(i<r[i])swap(a[i],a[r[i]]); cp Wn,w; for(int mid=1;mid<limit;mid<<=1)//不断取出中点 { Wn.set(cos(pi/mid),type*sin(pi/mid));//因 mid只有一半 所以就不用乘2了。 int size=mid<<1; for(int i=0;i<limit;i+=size) { w.set(1,0); int j=i+mid;//计算前一半 for(int k=i;k<j;k++,w=w*Wn) { cp x=a[k],y=w*a[k+mid]; a[k]=x+y; a[k+mid]=x-y; } } } } void mul_fft(vector<cp> &a, vector<cp> &b) { int siz=a.size()+b.size(); limit=1;l=0; while(limit<siz)limit*=2,l++; a.resize(limit);b.resize(limit); for(int i=0;i<limit;i++)a[i].i=b[i].r; FFT(a,1);for(int i=0;i<limit;i++)a[i]=a[i]*a[i];FFT(a,-1);//三次变两次优化 for(int i=0;i<=siz;i++) a[i].r=a[i].i/limit/2; } } string s1,s2; double ans[1000005]; int s[3][3]; void solve() { for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)cin>>s[i][j]; string s1,s2;cin>>s1>>s2; s1+=s1; char ch[]={'R','G','B'}; reverse(s2.begin(),s2.end()); int n = s1.length(),m=s2.length(); for(int i=0;i<=n+m;i++)ans[i]=0; for(int i=0;i<3;i++) { vector<fft::cp> a(n+m+1),b(m+1); for(int j=0;j<n;j++) { if(s1[j]==ch[i]) a[j]=fft::cp(1,0); else a[j]=fft::cp(0,0); } for(int j=0;j<m;j++) { if(s2[j]=='R')b[j]=fft::cp(s[i][0],0); if(s2[j]=='G')b[j]=fft::cp(s[i][1],0); if(s2[j]=='B')b[j]=fft::cp(s[i][2],0); } fft::mul_fft(a,b); for(int j=m;j<=n-1;j++) ans[j]+=a[j].r; } ll res=0; for(int i=m;i<=n-1;i++)res=max(res,(ll)(ans[i]+0.5)); cout<<res<<endl; } int main() { solve(); return 0; }
-
02022-07-29 15:31:24@
#include<bits/stdc++.h>
using namespace std;#define ll long long int
//Headernamespace fft
{
const double pi=acos(-1);
int limit=1,l=0;
struct cp{//complex
double r,i;
cp(double real=0,double img=0){r=real;i=img;}
void set(double real=0,double img=0){r=real;i=img;}
cp operator+(const cp& a){return cp(r+a.r,i+a.i);}
cp operator-(const cp& a){return cp(r-a.r,i-a.i);}
cp operator*(const cp& a){return cp(r*a.r-i*a.i,r*a.i+i*a.r);}
};void FFT(vector<cp> &a,int type)
{
vector<int>r(limit+1);
//int r[limit+1];r[0]=0;
for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1 | (i&1)<<(l-1));
for(int i=0;i<limit;i++)if(i<r[i])swap(a[i],a[r[i]]);
cp Wn,w;
for(int mid=1;mid<limit;mid<<=1)//不断取出中点
{
Wn.set(cos(pi/mid),type*sin(pi/mid));//因 mid只有一半 所以就不用乘2了。
int size=mid<<1;
for(int i=0;i<limit;i+=size)
{
w.set(1,0);
int j=i+mid;//计算前一半
for(int k=i;k<j;k++,w=w*Wn)
{
cp x=a[k],y=w*a[k+mid];
a[k]=x+y;
a[k+mid]=x-y;
}
}
}
}void mul_fft(vector<cp> &a, vector<cp> &b)
{
int siz=a.size()+b.size();
limit=1;l=0;
while(limit<siz)limit*=2,l++;
a.resize(limit);b.resize(limit);
for(int i=0;i<limit;i++)a[i].i=b[i].r;
FFT(a,1);for(int i=0;i<limit;i++)a[i]=a[i]*a[i];FFT(a,-1);//三次变两次优化
for(int i=0;i<=siz;i++) a[i].r=a[i].i/limit/2;
}
}string s1,s2;
double ans[1000005];
int s[3][3];
void solve()
{
for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)cin>>s[i][j];
string s1,s2;cin>>s1>>s2;
s1+=s1;
char ch[]={'R','G','B'};
reverse(s2.begin(),s2.end());
int n = s1.length(),m=s2.length();
for(int i=0;i<=n+m;i++)ans[i]=0;
for(int i=0;i<3;i++)
{
vector<fft::cp> a(n+m+1),b(m+1);
for(int j=0;j<n;j++)
{
if(s1[j]==ch[i]) a[j]=fft::cp(1,0); else a[j]=fft::cp(0,0);
}
for(int j=0;j<m;j++)
{
if(s2[j]=='R')b[j]=fft::cp(s[i][0],0);
if(s2[j]=='G')b[j]=fft::cp(s[i][1],0);
if(s2[j]=='B')b[j]=fft::cp(s[i][2],0);
}
fft::mul_fft(a,b);
for(int j=m;j<=n-1;j++) ans[j]+=a[j].r;
}
ll res=0;
for(int i=m;i<=n-1;i++)res=max(res,(ll)(ans[i]+0.5));
cout<<res<<endl;
}
int main()
{
solve();
return 0;
}
- 1