专栏文章

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

YYGBC_
P14173题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minnzvfv
此快照首次捕获于
2025/12/02 05:31
3 个月前
此快照最后确认于
2025/12/02 05:31
3 个月前
查看原文

P14173 猜拳游戏 题解

题意简述

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

分析

将两人的出拳序列一一合并，容易得到两人的出拳序列每在 lcm⁡(N,M)\operatorname{lcm}(N,M) 次便重复，题目给定两人出拳 1010010^{100} 次，此数远超 gcd⁡(N,M)\gcd(N,M)，所以考虑 lcm⁡(N,M)\operatorname{lcm}(N,M) 内次的情况。
我们造一组数据进行分析：
令 a=RPPSSPa = RPPSSP, b=PRPSb = PRPS，则 lcm⁡(N,M)=12\operatorname{lcm}(N,M)=12，两人的出拳序列为：
R,P,P,S,S,P,R,P,P,S,S,PR,P,P,S,S,P,R,P,P,S,S,P
P,R,P,S,P,R,P,S,P,R,P,SP,R,P,S,P,R,P,S,P,R,P,S
我们发现 gcd⁡(N,M)=2\gcd(N,M)=2，而 a0a_0 匹配了 b0,b2b_0,b_2 的情况（下标从 00 开始）；a1a_1 匹配了 b1,b3b_1,b_3 的情况，b0b_0 匹配了 a0,a2,a4a_0,a_2,a_4 的情况（下标从 00 开始）；b1b_1 匹配了 a0,a2,a4a_0,a_2,a_4 的情况……
以此类推，令 g=gcd⁡(a,b)g=\gcd(a,b)，对于任意的 aia_i，令 j=imod  gj=i\mod g，可以匹配到所有满足条件的 bjb_j。

解法

根据分析很容易得到解法。令 g=gcd⁡(a,b)g=\gcd(a,b)，对于一个 i(0≤i<g)i \left ( 0\le i< g \right ) ，建立集合 Ai,BiA_i,B_i，存下所有 a,ba,b 中下标模 gg 为 ii 的出拳类型，以及它们出现的个数。对于每一组，可以将其中一个集合中的出拳类型修改成指定的两个，并将另一个集合中的出拳类型修改成剩下的一个。对于每一组求修改的最小代价，并将所有 gg 组的代价加起来即可。
AC Code:
CPP
#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;
}

评论

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

正在加载评论...