本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-07 21:12:13

A

题意

给两个长度相等的字符串 $A$，$B$，每次可以在中任选一个字符并移到串的开头。求将 $A$ 变成 $B$ 的最小操作次数（无解输出 $-1$）。

思路

比较一眼。

不难发现，当且仅当两字符串的字母出现的次数不一样时，无解。

可以使用双指针，找到 $A$ 和 $B$ 的最长后缀(B必须连续，A不做要求)，答案即为字符串的长度减去最长后缀。

代码

signed main(){
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    cin>>a>>b;
    for(int i=0;i<a.size();i++){
        ta[a[i]-'A']++;
        tb[b[i]-'A']++;
    }
    for(int i=0;i<=27;i++){
        if(ta[i]!=tb[i]){
            cout<<-1;
            return 0;
        }
    }
    int j=b.size()-1;
    int cnt=0;
    for(int i=a.size()-1;i>=0;i--) if(a[i]==b[j]){
            j--;
            cnt++;
    }
    cout<<a.size()-cnt;
    return 0;
}
\/*
 0 7 4
 1 1 5 6 7 9 9
 *\/

B

题意

此处略

思路

40pts 是比较好拿的，二维前缀和直接判断即可。

不难发现， 以 $(x1,y1)$ 为左上角，$(x2,y2)$ 为右下角的子矩阵 $c$ 中 $1$ 的个数，就是 $a\left [ x1,\dots,x2\right ]$ 中 $1$ 的个数 乘上 $b\left [ y1,\dots,y2\right ]$ 中 $1$ 的个数。

枚举 $x \left (x \mid k\right )$，考虑 $a$ 有多少个区间和为 $x$，$b$ 有多少个区间和为 $\frac{k}{x}$，相乘即可。

可以记录 $a,b$ 序列每个0区间的长度，运用乘法原理求出 $a,b$ 序列中 $1$ 的个数为 $i$ 的区间个数。

细节蛮多的。

代码

signed main(){
    
   freopen("rain.in","r",stdin);
   freopen("rain.out","w",stdout);
    
    cin>>n>>m>>k;
    int cnta=0,sum=0;
    int la=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]){
            al[++cnta]=i-la;
            la=i;
        }
    }
    al[++cnta]=n-la+1;
\/\/    cout<<cnta<<endl;
\/\/    for(int i=1;i<=cnta;i++) cout<<al[i]<<' ';
    sum=0;
    int cntb=0,lb=0;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        if(b[i]){
            bl[++cntb]=i-lb;
            lb=i;
        }
    }
    bl[++cntb]=m-lb+1;
\/\/    Endl
\/\/    cout<<cntb<<endl;
\/\/    for(int i=1;i<=cntb;i++) cout<<bl[i]<<' ';
    int cnt=0;
    for(int i=1;i<=k\/i;i++){
        if(k%i==0){
            d[++cnt]=i;
            if(k\/i!=i){
                d[++cnt]=k\/i;
            }
           
        }
    }
\/\/    for(int i=1;i<=cnt;i++){
\/\/        cout<<d[i]<<' ';
\/\/    }
\/\/    Endl
    for(int i=1;i<=cnt;i++){
        int x=d[i];
        for(int j=1;j+x<=cnta;j++) suma[x]=(suma[x]+al[j]*al[j+x]%mod)%mod;
        for(int j=1;j+x<=cntb;j++) sumb[x]=(sumb[x]+bl[j]*bl[j+x]%mod)%mod;
    }
    int res=0;
    for(int i=1;i<=cnt;i++){
        int x=d[i],y=k\/x;
        res=(res+suma[x]*sumb[y])%mod;
    }
    cout<<res%mod;
    
    return 0;
}