acwing-193. 算乘方的牛

发表于 分类于 阅读次数： Waline： 本文字数： 570 阅读时长 ≈ 2 分钟

考点

  • IDAstar
  • 剪枝
  • 最大公约数

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e2 + 50;
int P;
#define f                           \
  x = max(tx, ty), y = min(tx, ty); \
  if (y && dfs(x, y, dep + 1, mxdep)) return true

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// 搜索顺序优化：令a一定大于等于b
bool dfs(int a, int b, int dep, int mxdep) {
  // 可行性剪枝：当前层数大于阈值，剪枝
  if (dep > mxdep) return false;
  // 得到答案，返回
  if (a == P) return true;
  // 最优性剪枝：未来剩余所有轮次都选择最大的进行翻倍，都无法到达答案
  if ((a << (mxdep - dep)) < P) return false;
  // 可行性剪枝：必须是gcd(a,b)的倍数
  if (P % gcd(a, b)) return false;
  int x, y, tx, ty;
  // 分类讨论
  tx = a + a, ty = b, f;
  tx = a + a, ty = a, f;
  tx = b + b, ty = a, f;
  tx = b + b, ty = b, f;
  tx = a + b, ty = b, f;
  tx = a + b, ty = a, f;
  tx = a - b, ty = b, f;
  tx = a - b, ty = a, f;
  return false;
}

int main() {
  cin >> P;
  int depth = 0;
  while (!dfs(1, 0, 0, depth)) ++depth;
  cout << depth;
  return 0;
}

思路

只能使用DFS，且要找最少，考虑IDAstar

由于只涉及到乘除法，所以只需要在乎幂次即可，令工作变量1的幂次为a，工作变量2的幂次为b；

那么初始状况下a = 1, b = 0

搜索顺序优化：

  • 同样的扩展分支，显然先扩展大的数更快到达目标，令a一定大于等于b

可行性剪枝：

  • 当前搜索层数大于阈值，剪枝

  • 如果P不是gcd(a, b)的倍数，剪枝

    因为很显然，P = ax + by，而gcd(a, b) = e，显然P / e应该是整数

估价函数：

  • 如果(a << (mxdep - dep)) < P，剪枝

    当前只剩mxdep - dep次翻倍的机会，每次都翻倍更大的a都无法到达P，显然应该剪掉

接下来讨论有几种情况：

一共只有以下8种情况，

(a + a, a)，(a + a, b)，(b + b, a)，(b + b, b)，(a + b, a)和(a + b, b)，(a - b, a)和(a - b, b)

a一定大于等于b，而b - a一定是小于等于0的，负数相当于回头，所以(b - a, a)和(b - a, b)舍去；

(a - a, a)，(a - a, b)，(b - b, a),(b - b, b)这四种带0的也舍去，是减法的特例，不需要重复枚举。