---

D. Gold Rush

原创 已于 2023-08-12 02:04:34 修改 · 粉丝可见 · 120 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132208685

题目：

cobol<br/>11<br/>6 4<br/>9 4<br/>4 2<br/>18 27<br/>27 4<br/>27 2<br/>27 10<br/>1 1<br/>3 1<br/>5 1<br/>746001 2984004<br/>

objectivec<br/>YES<br/>YES<br/>NO<br/>NO<br/>YES<br/>YES<br/>NO<br/>YES<br/>YES<br/>NO<br/>NO<br/>

思路：

这道题很有意思的，题目意思要我们从 一堆 n 个黄金中，按照分成的任意堆，按照两堆两堆分成的时候，另一堆应该是 另一堆的一倍

思路图：

所以，我们可以推出公式：

按照这个公式，进行建树，搜索，这里我建议是用BFS搜索每一层，查看是否有符合的 m 个黄金的堆

代码详解如下：

#include <iostream>
#include <queue>
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

int n;	// 原始黄金个数

int m;	// 目标堆黄金个数

inline bool BFS()
{
	// 开始BFS 判断
	// q 存储每个分成的每个堆
	queue<int>q;
	q.push(n);	// 存储原始黄金个数

	while (q.size())
	{
		// 取出其中的一个堆
		int sum = q.front();
		q.pop();

		if (sum == m)
			return true;
		// 如果这个堆符合我们的目标黄金个数
		// 返回 true 表示 可以分成

		// 如果可以分成 相应的 一个堆是另一个堆的倍数
		// 那么我们开始分
		if (sum % 3 == 0)
		{
			q.push(2 * sum / 3);
			q.push(sum / 3);
		}
	}
	// 如果都没有返回 false
	return false;
}

inline void solve()
{
	cin >> n >> m;
	if (BFS())
	{
		puts("YES");
	}
	else
		puts("NO");
}

int main()
{
	___G;
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：