给一个堆 \(n\) 个石子,如果可以分裂为整数,它将分裂为 \(\frac{1}{3} n\) 和 \(\frac{2}{3} n\) 的两堆石子。并且新石堆会继续分裂。
询问过程中是否出现过大小为 \(m\) 的石堆。
显然记忆化 \(dfs\) 即可。
记忆数组一般开全局。容易观察到值域很大,多测清空导致大量开销。但是有效状态很少。于是可以记使用状态为 \(was\) ,然后遍历 \(was\) 初始化记忆数组。
注意:申请数组不需要时间,但是访问到数组的内存需要时间,此题数组不能开局部。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int v[10000005];
void solve(){
int n, m; std::cin >> n >> m;
if (m > n) { std::cout << "NO\n"; return; }
std::vector<int> was;
std::function<void(int)> dfs = [&](int x) {
if (v[x]) return;
v[x] = 1;
was.push_back(x);
if (x % 3 == 0) {
dfs (x / 3);
dfs (x / 3 * 2);
}
};
dfs(n);
std::cout << (v[m] ? "YES" : "NO") << '\n';
for (auto x : was) v[x] = 0;
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}