专栏文章

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

ccogimyun
P14173题解参与者 5已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@minodvrm
此快照首次捕获于
2025/12/02 05:42
3 个月前
此快照最后确认于
2025/12/02 05:42
3 个月前
查看原文
我们不妨先寻找 Alice 的出招序列 aa 中的 aia_i 与 Bob 的出招序列 bb 中的 bjb_j 在什么时候会在同一局中出现，考虑 Alice 与 Bob 会进行 1010010^{100} 局游戏，所以可以认为是无限局游戏，那么只要 nx+i=by+jnx+i=by+j 存在一对非负整数解 (x,y)(x,y)，aia_i 与 bjb_j 会在同一局中出现。又根据裴蜀定理，nx+i=by+jnx+i=by+j 存在一对非负整数解 (x,y)(x,y) 的充要条件是 i≡j(mod gcd⁡(n,m))i\equiv j (mod\ \gcd(n,m))，所以我们可以根据 ii 或 jj 对 gcd⁡(n,m)\gcd(n,m) 的余数进行分组，分别记录 aa 和 bb 中对 gcd⁡(n,m)\gcd(n,m) 余数相同的位置的 RPS 个数分别是多少，代码如下：
CPP
    mp['P']=1;
	mp['S']=2;
	for(int i=0;i<n;i++)
		cnt[i%l][mp[a[i]]]++;
	for(int j=0;j<m;j++)
		cnt1[j%l][mp[b[j]]]++;
接下来我们便可以对于每组进行计算贡献，由于每组中的 i,ji,j 都满足 nx+i=by+jnx+i=by+j 存在一对非负整数解 (x,y)(x,y)，那么里面所有的 aia_i 与 bjb_j 两两都会在某一局中同时出现，于是我们存在两种修改序列的方式：
  1. Alice 所有在这一组的位置的出招均为 RPS 中的同一种 XX，Bob 的则为 RPS 中的另两种，贡献为 Alice 所有在这一组的位置的出招不为 XX 的个数加上 Bob 所有在这一组的位置的出招为 XX 的个数；
  2. Bob 所有在这一组的位置的出招均为 RPS 中的同一种 XX，Alice 的则为 RPS 中的另两种，贡献与第一种类似。
我们取每一组在上面两种方案中的最小值加到总贡献上即可算出答案。

CODE

CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,l,cnt[500005][3],cnt1[500005][3];
string a,b;
map<char,int> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	l=__gcd(n,m);
	cin>>a>>b;
	mp['P']=1;
	mp['S']=2;
	for(int i=0;i<n;i++)
		cnt[i%l][mp[a[i]]]++;
	for(int j=0;j<m;j++)
		cnt1[j%l][mp[b[j]]]++;
	int ans=0;
	for(int i=0;i<l;i++){
		int k1,k2;
		k1=min({cnt[i][0]+cnt[i][1]+cnt1[i][2],cnt[i][0]+cnt[i][2]+cnt1[i][1],cnt[i][2]+cnt[i][1]+cnt1[i][0]});
		k2=min({cnt1[i][0]+cnt1[i][1]+cnt[i][2],cnt1[i][0]+cnt1[i][2]+cnt[i][1],cnt1[i][2]+cnt1[i][1]+cnt[i][0]});
		ans+=min(k1,k2); 
	}
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...