佛山网站制作的公司_学生html美食静态网页代码_百度旗下产品_安卓优化大师最新版

审题：

本题需要我们判断多组x，y的值的比赛结果

思路：

方法一：记忆化搜索

首先我们观察到以两个回合为一个轮回，x == (x+y)%p, y == (x+2*y)%p。

确认递归函数作用：返回dfs(x,y)的判断结果

不过本题有多组数据，所以我们必然会经历很多重复的计算，考虑使用记忆化搜索。

若我们直接用int型数组会导致空间占用过多，导致报错，所以我们使用char数组用字符的形

式记录结果。

平局分析：平局意味着计算出现中x，y完全重复的情况，任意只要出现过我们就可以记录为3,然后查备忘录的时候查到就说明出现过，可以直接返回了

解题：

#include<iostream>
using namespace std;
int t, p;
const int N = 1e4 + 10;
char f[N][N];//备忘录

（1）main函数

int main()
{cin >> t >> p;while (t--)//多组数据{int x, y;cin >> x >> y;char answer = dfs(x, y);if (answer == '1' || answer == '2'){cout << answer-'0' << endl;}else//平局{cout << "error" << endl;}}return 0;
}

（2）dfs

char dfs(int x, int y)
{if (f[x][y]) return f[x][y];//查找备忘录f[x][y] = '3';//标记已查询状态if (x == 0) return f[x][y] = '1';if (y == 0) return f[x][y] = '2';return f[x][y] = dfs((x+y)%p,(x+2*y)%p);
}

注意：

1.由于轮回中是先出现x，然后出现y，所以为了模拟轮次情况，先判断x再判断y。

2.每次判断结果都要记录在备忘录中，以进行剪枝

P5635 【CSGRound1】天下第一 - 洛谷