专栏文章

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

qqkj_qwq
P14173题解参与者 11已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@minoegbf
此快照首次捕获于
2025/12/02 05:43
3 个月前
此快照最后确认于
2025/12/02 05:43
3 个月前
查看原文
说句闲话
若 Alice 和 Bob 一秒进行一次石头剪刀布，那么他们将会交战约 3.17×10903.17\times10^{90} 个世纪。
小 R 最多要请的奶茶杯数为 5×1055\times10^5。假设一杯奶茶 1515 元，则小 R 要花掉 750750 万元。
假设一杯奶茶 500g500\text g，则 Alice 和 Bob 一共要喝 250t250\text t 的奶茶。

解题思路

设 g=gcd⁡(n,m)g=\gcd(n,m)。若 i≡j(modg)i\equiv j \pmod g，则 aia_i 与 bib_i 一定是会进行交战的。
证明过程

必要性证明

假设存在局数 kk 使得 aia_i 与 bjb_j 交战，即 k≡i(modn)k \equiv i \pmod{n} 和 k≡j(modm)k \equiv j \pmod{m}。由定义：
  • k=i+ntk = i + n t 对于某个整数 tt。
  • 代入第二式：i+nt≡j(modm)i + n t \equiv j \pmod{m}，即 nt≡j−i(modm)n t \equiv j - i \pmod{m}。
该线性同余方程有解当且仅当 gcd⁡(n,m)∣(j−i)\gcd(n, m) \mid (j - i)。令 g=gcd⁡(n,m)g = \gcd(n, m)，则 g∣(j−i)g \mid (j - i)，即 i≡j(modg)i \equiv j \pmod{g}。必要性得证。

充分性证明

假设 i≡j(modg)i \equiv j \pmod{g}，即 g∣(j−i)g \mid (j - i)。令 n=gxn = g x，m=gym = g y，其中 gcd⁡(x,y)=1\gcd(x, y) = 1。由 i≡j(modg)i \equiv j \pmod{g}，可设 j−i=gdj - i = g d 对于某个整数 dd。
考虑方程 nt≡j−i(modm)n t \equiv j - i \pmod{m}，即 gxt≡gd(modgy)g x t \equiv g d \pmod{g y}。两边除以 gg（因 g≠0g \neq 0）：
xt≡d(mody)x t \equiv d \pmod{y}
由于 gcd⁡(x,y)=1\gcd(x, y) = 1，该方程有解 tt。令 k=i+ntk = i + n t，则：
  • k≡i(modn)k \equiv i \pmod{n}（由 k=i+ntk = i + n t），
  • k≡i+nt≡i+(j−i)=j(modm)k \equiv i + n t \equiv i + (j - i) = j \pmod{m}（因 nt≡j−i(modm)n t \equiv j - i \pmod{m}）。
故 aia_i 与 bjb_j 在局 kk 中相遇。充分性得证。
所以，我们对 n mod gn\bmod g 和 m mod gm\bmod g 的值对 aa 和 bb 进行分组。
由于一个组内的 aa 和 bb 都要两两进行交战，所以设这个组内的 aa 构成的集合为 AA，这个组内的 bb 构成的集合为 BB，我们要使 A∩B=∅A\cap B=\emptyset。
所以，对于每个组，我们需要进行最少次数的替换，使得出招满足上述条件。设 x1x_1 为当前组内 aa 中 R 出现的次数，x2x_2 为 P 出现的次数，x3x_3 为 S 出现的次数，y1y_1 为当前组内 bb 中 R 出现的次数，y2y_2 为 P 出现的次数，y3y_3 为 S 出现的次数，则替换的最少次数为：
min⁡(y1+x2+x3,x1+y2+x3,y1+y2+x3,x1+x2+y3,y1+x2+y3,x1+y2+y3)\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)
其中，y1+x2+x3y_1+x_2+x_3 指的是将 aa 中的 P 和 S 都替换成 R，把 bb 中的 R 替换成其它的字母所花的代价。其它式子同理。

Code

CPP
#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;
}
AI 使用说明
本文使用 DeepSeek 进行了证明。因为本人太菜了，不会证。

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...