题解：P10494 [USACO02FEB] Power Hungry Cows

wangbinfeng · 2024-08-08 08:55:43 · 题解

已被打回两次，烦请告知具体不合规的位置，以便作者进行修改。

• 题解意义：这道题的原题空间限制是 30000KiB，所以必须用 ID-DFS。但是 luogu 里这道题的空间限制是 512.00MiB，所以用 BFS 的空间复杂度是没有问题的。鉴于这道题可以被作为是 ID-DFS 的模板题，建议还是跟着其他题解学一下 ID-DFS。那么为什么会有这个题解呢？因为我为了验证 BFS 可以通过本题，尝试了长达 20 天，所以本题解分享方法，以免后来人重复浪费时间。
• 题意简述：有两个变量，其初值分别为 x 和 1，请问这两个变量最少经过多少次乘或除操作，使得至少一个变量的值成为 x^P。
• 必备公式：x^a\times x^b=x^{a+b},\frac{x^a}{x^b}=x^{a-b},x^0=1。

首先可以发现变量 x 其实没啥用，因为乘除操作完全可以转换为对其指数加减操作，所以题目可以转化为两个数 0,1 经过任意多操作得到 P。因为 P\le2\times 10^4，所以搜索即可。 对于状态 (x,y)，可以转移到 \begin{cases} (x,x+x)\\(x,y+y)\\(x+x,y)\\(y+y,y)\\(x,x+y)\\(x+y,y)\\(x,\lvert x-y\rvert)\\(\lvert x-y\rvert,y) \end{cases} 共计 8 种状态，搜索一下。

设答案为 ans，则时间复杂度约为 8^{ans}，经测试 ans\le20，跑所有状态显然不可能完成。容易想到记忆化，不幸的是还是超时。

考虑到令 A=\gcd(x,y)，则 x=\lambda_1A,y=\lambda_2 A，那么他们凑出来的数将一定也只能是 A 的倍数（也可以把 \lambda 搞成零然后再找，但显然更劣）。那么如果发现若 P\bmod\gcd(x,y)\neq0，那么就可以直接剪枝。

现在 ID-DFS 已经可以 \colorbox{green}{\color{white}{AC}} 了，但是 BFS 还是有可能会 \colorbox{black}{\color{white}{TLE}}，考虑继续卡常。由于每个人卡常的方法不尽相同，这里仅介绍我本人的卡常方法：

1. 手写队列，不要用 STL 的 queue，经测试可以节省 300 ms。
2. 手写 gcd，不要用 STL 的 __gcd。
3. 用 bitset 或 bool 数组，不要用 STL 的 map/unordered_map。

总结一下就是少用或不用 STL。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int p, cnt;
const int maxp = 2e4 + 9;
bitset<maxp * maxp * 5> vis;
const int M = 4e7 + 5, P = 4e7;
struct Node
{
    unsigned short x, y, dep;
} v[M];

int l = 1, r = 0;
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)
#define ctz __builtin_ctz
int az, bz, z, t;
inline int gcd(int a, int b)
{
    if (!a || !b)
        return 0;
    az = ctz(a), bz = ctz(b), z = (az > bz) ? bz : az, t;
    b >>= bz;
    while (a)
        a >>= az, t = a - b, az = ctz(t), b = min(a, b), a = t < 0 ? -t : t;
    return b << z;
}
int x, y, dep;
inline int bfs()
{
    Node now = {1, 0, 0};
    for (v[++r] = now, (r == P) && (r = 0); 1; l++, (l == P + 1) && (l = 1))
    {
        cnt++;
        x = max(v[l].x, v[l].y), y = min(v[l].x, v[l].y), dep = v[l].dep;
        if (x == p || y == p)
        {
            cout << dep;
            return dep;
        }
        if (x > p * 2)
            continue;
        if (vis[x * p * 2 + y])
            continue;
        if (gcd(x, y) && p % gcd(x, y))
            continue;
        vis[x * p * 2 + y] = true;
        now.x = x * 2, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x * 2, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x, now.y = y * 2, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = y, now.y = y * 2, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x + y, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x + y, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x - y, now.y = x, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
        now.x = x - y, now.y = y, now.dep = dep + 1, v[++r] = now, (r == P) && (r = 0);
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> p;
    bfs();
}

• 后记： 经过我本人的测试，其实 ID-DFS 和 BFS 的遍历节点数相近，为同一个数量级，且 BFS 遍历的节点数甚至会更小（UPD：经过第二次测试，发现结果与第一次测试结论不符，等待最终确定结果），不清楚为什么经过卡常的 BFS 算法会比 ID-DFS 慢了 \frac{835ms}{18ms}\approx46.3 倍（对于第 #11 个测试点），希望有大佬可以告知原因。
• 鸣谢：感谢 @C20252323tzy 帮我卡常，题解中的代码也是这位大佬修改的，在此表示万分的感谢。
• 附录：关于代码运行时间的测试（在这个链接进行测试，仅供参考）：