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

YGBC_ · 2025-10-07 17:56:11 · 题解

P14173 猜拳游戏 题解

题意简述

Alice 和 Bob 玩石头剪刀布，按一定的序列出招若干次。给定他们的出招序列，要求将两人的出招序列修改，使得两人的对局中不出现平局。求最小修改次数。

分析

将两人的出拳序列一一合并，容易得到两人的出拳序列每在 \operatorname{lcm}(N,M) 次便重复，题目给定两人出拳 10^{100} 次，此数远超 \gcd(N,M)，所以考虑 \operatorname{lcm}(N,M) 内次的情况。
我们造一组数据进行分析：
令 a = RPPSSP, b = PRPS，则 \operatorname{lcm}(N,M)=12，两人的出拳序列为：

:::align{center}

:::

我们发现 \gcd(N,M)=2，而 a_0 匹配了 b_0,b_2 的情况（下标从 0 开始）；a_1 匹配了 b_1,b_3 的情况，b_0 匹配了 a_0,a_2,a_4 的情况（下标从 0 开始）；b_1 匹配了 a_0,a_2,a_4 的情况……
以此类推，令 g=\gcd(a,b)，对于任意的 a_i，令 j=i\mod g，可以匹配到所有满足条件的 b_j。

解法

根据分析很容易得到解法。令 g=\gcd(a,b)，对于一个 i \left ( 0\le i< g \right ) ，建立集合 A_i,B_i，存下所有 a,b 中下标模 g 为 i 的出拳类型，以及它们出现的个数。对于每一组，可以将其中一个集合中的出拳类型修改成指定的两个，并将另一个集合中的出拳类型修改成剩下的一个。对于每一组求修改的最小代价，并将所有 g 组的代价加起来即可。

AC Code:

#include<iostream>
#define MAXN 500005
#define INF 0x3f3f3f3f
using namespace std;

int N,M,G;
string s1,s2;
int ans;
int a[MAXN],b[MAXN];
int na[MAXN][3],nb[MAXN][3];

int gcd(int a,int b){
    if(b==1) return 1;
    if(a%b==0) return b;
    return gcd(b,a%b);
}

void init(){                 //读入出拳类型
    cin>>N>>M;
    cin>>s1>>s2;
    for(int i=0;i<N;i++){
        if(s1[i]=='P') a[i]=1;
        if(s1[i]=='S') a[i]=2;
    }
    for(int i=0;i<M;i++){
        if(s2[i]=='P') b[i]=1;
        if(s2[i]=='S') b[i]=2;
    }
    G=gcd(N,M);
    for(int i=0;i<N;i++) na[i%G][a[i]]++;
    for(int i=0;i<M;i++) nb[i%G][b[i]]++;
}

void solve(){
    for(int i=0;i<G;i++){    //统计每组的最小代价 
        int cnt=INF;
        cnt=min(cnt,na[i][0]+na[i][1]+nb[i][2]);
        cnt=min(cnt,na[i][0]+nb[i][1]+na[i][2]);
        cnt=min(cnt,nb[i][0]+na[i][1]+na[i][2]);
        cnt=min(cnt,na[i][0]+nb[i][1]+nb[i][2]);
        cnt=min(cnt,nb[i][0]+na[i][1]+nb[i][2]);
        cnt=min(cnt,nb[i][0]+nb[i][1]+na[i][2]);
        ans+=cnt;
    }
    cout<<ans<<endl;         //输出答案 
}

int main()
{
    init();
    solve();
    return 0;
}