2 条题解

  • 1
    @ 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;
    }
    
  • 0
    @ 2022-07-29 15:31:24

    #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;
    }

  • 1

F 礼物(2) /[模板]FFT字符串匹配

信息

ID
1243
难度
9
分类
FFT 点击显示
标签
递交数
11
已通过
4
通过率
36%
被复制
4
上传者