题解：P14173 【MX-X23-T3】猜拳游戏

Moanran · 2025-10-07 11:42:26 · 题解

题意简述

找到 A 和 B 序列在接近无限次比赛中不出现平局的最小修改次数。

思路分析

定义 g=\gcd(n,m)， 可以发现每一个元素会和对面每 g 个元素产生重复，所以按照最大公因数分为 g 组，每一组中找到最小的修改次数。

AC CODE

#include<iostream>
#include<set>
using namespace std;
char a[500005],b[500005];
int GCD(int a,int b)
{
    if(a%b==0) return b;
    return GCD(b,a%b);
}
int ar,ap,as,br,bp,bs;
int ans;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    int g=GCD(n,m);
    for(int i=1;i<=g;i++)
    {
        ar=0,as=0,ap=0;
        br=0,bs=0,bp=0;
        for(int j=i;j<=n;j+=g)
        {
            if(a[j]=='R') ar++;
            if(a[j]=='S') as++;
            if(a[j]=='P') ap++;
        }
        //cout<<ar<<" "<<as<<" "<<ap<<endl;
        for(int j=i;j<=m;j+=g)
        {
            if(b[j]=='R') br++;
            if(b[j]=='S') bs++;
            if(b[j]=='P') bp++;
        }
        //cout<<br<<" "<<bs<<" "<<bp<<endl;
        ans+=min(ar+bs+ap,min(ar+as+bp,min(ar+bs+bp,min(br+as+bp,min(br+bs+ap,br+as+ap)))));
    }
    cout<<ans;
    return 0;
}