例题

小Why的数论测试

题目大意

给定$a,b$($1\le a\le b \le 10^{12}$,)，有三种操作

①$a:=a+1$

②$a:=2a$

③$a:=a^2$

问从$a$变成b的最少操作次数。

解题思路

从$a$搜索到$b$，每步的选择都有三种，而从$b$搜索到$a$，第②步必须保证$b$是偶数，第③步必须保证$b$是完全平方数，状态少了很多。从b记忆化搜索到a即可。

参考代码

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
41
42
43
44
45
46
// Problem: 小Why的数论测试
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/64384/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 1;

unordered_map<int,int> mp;
int a,b;

int dfs(int x){
	if(mp.count(x)) return mp[x];
	int ans = x - a;
	if(x / 2 >= a) ans = min(ans, dfs(x / 2) + 1 + x % 2);
	int u = sqrt(x);
	if(u >= a) ans = min(ans, dfs(u) + 1 + x - u * u);
	return mp[x] = ans;
}

void solve() {
	cin >> a >> b;
	mp.clear();
	mp[a] = 0;
	dfs(b);
	cout << mp[b] << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	if (multi) cin >> T;
	while (T--) {
		solve();
	}
	
	return 0;
}

Shortest path

题目大意

给你一个数n，初始值为1，每次可以对他进行 乘2/乘3/加1 三种操作之一，问最小操作次数。

解题思路

由于从1到n的情况数比n到1多的多，所以我们考虑从n向1搜索，但肯定不能完全暴力。

可以发现，除以2或除以3的操作比减1进行的贡献要优的多。我们应考虑将减1作为该数不能整除2或整除3时来使用这一操作。

这里采用记忆化搜索，能有效降低时间复杂度。

参考代码

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
41
42
43
44
45
// Problem: Shortest path
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=7372
// Memory Limit: 262 MB
// Time Limit: 2000 ms

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi = 1;

int n;
unordered_map<int, int> mp;

int dfs(int x) {
	if(mp.count(x)) return mp[x];
	int ans = x - 1;
	if(x / 3 >= 1) ans = min(ans, dfs(x / 3) + 1 + x % 3);
	if(x / 3 >= 1) ans = min(ans, dfs(x / 2) + 1 + x % 2);
	return mp[x] = ans;
}

void solve() {
	cin >> n;
	mp.clear();
	mp[1] = 0;//这样可以在dfs中少一个判断
	dfs(n);
	cout << mp[n] << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	if (multi) cin >> T;
	while (T--) {
		solve();
	}
	
	return 0;
}