8.7 mx模拟赛记录

· · 个人记录

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