P5635 【CSGRound1】天下第一题解

发布日期：2025-07-16 18:48:44

题目传送门

题目背景

天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后，开始了自己休闲的生活，并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人，所以 zhouwc 虽然是一个蒟蒻，也有能和 cbw 玩游戏的机会。

题目描述

游戏是这样的：

给定两个数 x，y，与一个模数 p。

cbw 拥有数 x，zhouwc 拥有数 y。

第一个回合：x←(x+y) mod p。

第二个回合：y←(x+y) mod p。

第三个回合：x←(x+y) mod p。

第四个回合：y←(x+y) mod p。

以此类推....

如果 x 先到 0，则 cbw 胜利。如果 y 先到 0，则 zhouwc 胜利。如果 x,y 都不能到 0，则为平局。

cbw 为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。

输入格式

有多组数据。

第一行：T 和 p 表示一共有 T 组数据且模数都为 p。

以下 T 行，每行两个数 x,y。

输出格式

共 T 行

1 表示 cbw 获胜，2 表示 zhouwc 获胜，error 表示平局。

输入输出样例 #1

输入 #1


 1 10
 1 3

输出 #1


 error

输入输出样例 #2

输入 #2


 1 10
 4 5

输出 #2

说明/提示

1 ≤ T ≤ 200。

1 ≤ x,y,p ≤ 10000。

题解

这道题我写了两种解法

1、纯模拟+代码优化

#include<cstdio>
 int main()
 {
 	register int t, p, x, y;
 	scanf("%d %d",&t,&p);
 	for (register int _ = 1; _ <= t; _++)
 	{
 		scanf("%d %d", &x, &y);
 		for(register int step=0;step<=10000;step++)
 		{
 			x = (x + y) % p;
 			if (x == 0) break;
 			y = (x + y) % p;
 			if (y == 0) break;
 		}
 		if (!x) printf("1\n");
 		else if (!y) printf("2\n");
 		else printf("error\n");
 	}
 	return 0;
 }

提交记录：

最多也就15ms。

2、DFS+记忆化搜索+代码优化

#include<cstdio>
 using namespace std;
 int t, p;
 const int MAXXYP = 20005;
 short int mem[MAXXYP][MAXXYP];
 static inline int dfs(register int x, register int y)
 {
 	if (mem[x][y] != 0) return mem[x][y];
 	register int nx = (x + y) % p;
 	register int ny = (nx + y) % p;
 	if (!nx) return 1;
 	if (!ny) return 2;
 	mem[x][y] = -1;
 	mem[x][y] = dfs(nx, ny);
 	return mem[x][y];
 }
 int main()
 {
 	scanf("%d %d", &t, &p);
 	register int x, y;
 	for (register int _ = 1; _ <= t; _++)
 	{
 		scanf("%d %d", &x, &y);
 		register int result = dfs(x, y);
 		if (result == -1) printf("error\n");
 		else printf("%d\n", result);
 	}
 	return 0;
 }