题解：P10494 [USACO02FEB] Power Hungry Cows

PeppaPig_qwq · 2024-05-18 09:41:20 · 题解

这道题可以用搜索来实现，我用的是迭代加深，也可以用 bfs 等算法。主要考虑剪枝。

• 首先，可以发现 wv_1,wv_2 在 k 轮操作后最大值就是 wv_1 一直翻倍，最大值为 2^{k} \times{wv_1}，因为只有 wv_1 是 1，所以可以判断搜索时 2^{lim-dep} 是否大于 P，小于的话就停止搜索。
• 还有，wv_1 + wv_2, wv_1 - wv_2, wv_1 \times{wv_2},wv_1 \div 2,wv_2 \times{2},wv_2 \div 2,wv_1 \times{2}, wv_1 \div 2 都整除 \gcd(wv_1,wv_2)，所以可以判断 \gcd(wv_1, wv_2) 是否为 P 的因数。否的话退出搜索。

下面是代码：

#include <bits/stdc++.h>
using namespace std;

int lim, p, _pow[31];
bool flag = 0;

void dfs(int dep, int x, int y) {
    if (x < y)
        swap(x, y);
    if (dep == lim + 1) {
        if (x == p or y == p) {
            cout << dep - 1 << endl;
            exit(0);
        }
        return ;
    }
    if (gcd(x, y) and p % gcd(x, y) != 0)
        return ;
    if (x * _pow[lim - dep + 1] < p)
        return ;
    dep++;
    dfs(dep, x, y + x);
    dfs(dep, y + x, y);
    dfs(dep, x, x - y);
    dfs(dep, x - y, y);
    dfs(dep, x, x + x);
    dfs(dep, x + x, y);
    dfs(dep, x, y + y);
    dfs(dep, y + y, y);
}

int main() {
    _pow[0] = 1;
    for (int i = 1; i < 32; i++)
        _pow[i] = _pow[i - 1] * 2;
    cin >> p;
    for (lim = 0; !flag; lim++)
        dfs(1, 1, 0);
    return 0;
}