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

· · 题解

:::info[说句闲话] 若 Alice 和 Bob 一秒进行一次石头剪刀布，那么他们将会交战约 3.17\times10^{90} 个世纪。

小 R 最多要请的奶茶杯数为 5\times10^5。假设一杯奶茶 15 元，则小 R 要花掉 750 万元。

假设一杯奶茶 500\text g，则 Alice 和 Bob 一共要喝 250\text t 的奶茶。 :::

解题思路

设 g=\gcd(n,m)。若 i\equiv j \pmod g，则 a_i 与 b_i 一定是会进行交战的。

:::info[证明过程]

必要性证明

假设存在局数 k 使得 a_i 与 b_j 交战，即 k \equiv i \pmod{n} 和 k \equiv j \pmod{m} 。由定义：

该线性同余方程有解当且仅当 \gcd(n, m) \mid (j - i) 。令 g = \gcd(n, m) ，则 g \mid (j - i) ，即 i \equiv j \pmod{g} 。必要性得证。

充分性证明

假设 i \equiv j \pmod{g} ，即 g \mid (j - i) 。令 n = g x ， m = g y ，其中 \gcd(x, y) = 1 。由 i \equiv j \pmod{g} ，可设 j - i = g d 对于某个整数 d 。

考虑方程 n t \equiv j - i \pmod{m} ，即 g x t \equiv g d \pmod{g y} 。两边除以 g （因 g \neq 0 ）：

x t \equiv d \pmod{y}

由于 \gcd(x, y) = 1 ，该方程有解 t 。令 k = i + n t ，则：

故 a_i 与 b_j 在局 k 中相遇。充分性得证。 :::

所以，我们对 n\bmod g 和 m\bmod g 的值对 a 和 b 进行分组。

由于一个组内的 a 和 b 都要两两进行交战，所以设这个组内的 a 构成的集合为 A，这个组内的 b 构成的集合为 B，我们要使 A\cap B=\emptyset。

所以，对于每个组，我们需要进行最少次数的替换，使得出招满足上述条件。设 x_1 为当前组内 a 中 R 出现的次数，x_2 为 P 出现的次数，x_3 为 S 出现的次数，y_1 为当前组内 b 中 R 出现的次数，y_2 为 P 出现的次数，y_3 为 S 出现的次数，则替换的最少次数为：

\min(y_1+x_2+x_3,x_1+y_2+x_3,y_1+y_2+x_3,x_1+x_2+y_3,y_1+x_2+y_3,x_1+y_2+y_3)

其中，y_1+x_2+x_3 指的是将 a 中的 P 和 S 都替换成 R，把 b 中的 R 替换成其它的字母所花的代价。其它式子同理。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gg(char c)
{
    if(c=='R')return 1;
    if(c=='P')return 2;
    if(c=='S')return 3;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,s=0;
    string a,b;
    cin>>n>>m>>a>>b;
    int g=__gcd(n,m);
    for(int i=1;i<=g;i++)
    {
        int x[5]={},y[5]={};
        for(int j=i-1;j<n;j+=g)x[gg(a[j])]++;
        for(int j=i-1;j<m;j+=g)y[gg(b[j])]++;
        s+=min({x[1]+y[2]+y[3],
                y[1]+x[2]+x[3],
                x[2]+y[1]+y[3],
                y[2]+x[1]+x[3],
                x[3]+y[1]+y[2],
                y[3]+x[1]+x[2]});
    }
    cout<<s;
    return 0;
}

:::info[AI 使用说明] 本文使用 DeepSeek 进行了证明。因为本人太菜了，不会证。 :::