对数器打表找规律的技巧
使用场景
对数器打表找规律的使用场景：输入参数是简单类型，返回值也是简单类型。
步骤
- 可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力
- 打印入参不大情况下的答案，观察规律
- 把规律变成代码，就是最优解了
例子
题目1 用袋子买苹果问题
使用规格8和规格6的袋子买苹果问题。
输入n个苹果，苹果数量必须要装满袋子。问苹果数量能否用规格8和规格6的袋子装满？可以的话返回每个袋子的数量，否则返回-1。
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
// 递归模拟——暴力解
int f(int rest) { // rest表示还剩多少苹果
if (rest < 0) {
return INT_MAX;
}
if (rest == 0) {
return 0;
}
int p1 = f(rest - 8);
int p2 = f(rest - 6);
p1 += p1 != INT_MAX ? 1 : 0;
p2 += p2 != INT_MAX ? 1 : 0;
return min(p1, p2);
}
int bags1(int apple) {
int ans = f(apple);
return ans == INT_MAX ? -1 : ans;
}
// 找到规律——正解
int bags2(int apple){
if(apple % 2 == 1){
return -1;
}
if(apple < 18){
if(apple == 0){
return 0;
}
if(apple == 6 || apple == 8){
return 1;
}
if(apple == 12 || apple == 14 || apple == 16){
return 2;
}
return (apple - 18) / 8 + 3;
}
}
void solve() {
// 暴力打表过程
// for (int i = 0; i <= 100; i++) {
// cout << "i = " << i << " : ";
// cout << bags1(i) << endl;
// }
// // 正解O(1)
cin >> apple;
cout << "ans = " << bags2(apple) << endl;
}
题目2 A和B轮流吃草，谁会赢？
博弈论中，A和B轮流吃草，每次AB都只能吃 $4^m$ 堆草，谁吃到最后一根草谁就赢，给定草堆的大小$n$，问谁会赢？
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
// 递归模拟——暴力解
string f(int rest, string cur) {
string enemy = cur == "A" ? "B" : "A";
if (rest < 5) {
return (rest == 0 || rest == 2) ? enemy : cur;
}
int pick = 1;
while (pick <= rest) {
if (f(rest - pick, enemy) == cur) {
return cur;
}
pick *= 4;
}
return enemy;
}
string win1(int n) { return f(n, "A"); }
// 正解O(1)
string win2(int n){
n %= 5;
if(n == 0 || n == 2){
return "B";
}else{
return "A";
}
}
void solve() {
// 打表找规律过程
// for (int i = 0; i <= 50; i++) {
// cout << i << " : " << win1(i) << endl;
// }
cin >> n;
cout << win2(n) << endl;
}
题目3 判断一个数字是否为连续正整数的和
给定一个整数n，判断它是否可以表示为连续的正整数之和。
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
bool getnum1(int num) {
for (int start = 1, sum; start <= num; start++) {
sum = start;
int plus = start + 1;
while (plus <= num) {
if (sum + plus > num) {
break;
}
if (sum + plus == num) {
return true;
}
sum += plus;
plus++;
}
}
return false;
}
bool getnum2(int num) { // 判读num是否是2的幂次方
return (num & (num - 1)) != 0;
}
void solve() {
// for (int i = 1; i <= 200; i++) {
// if (getnum1(i)) {
// cout << i << " : " << "YES" << endl;
// } else {
// cout << i << " : " << "NO" << endl;
// }
// }
cin >> n;
if(getnum2(n)){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
题目4 red好串数量问题
“好串”指的是只有’r’, ‘e’, ‘d’这三个字符的字符串，且字符串有且仅有一个长度>=2的回文子串。给定一个字符串s，求s中好串的数量。
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
47
48
49
50
51
52
53
54
55
56
57
58
int n;
const int mod = 1e9 + 7;
char choice[4] = {'r', 'e', 'd'};
bool is(string &arr, int l, int r) {
while (l <= r) {
if (arr[l] == arr[r]) {
l++;
r--;
continue;
} else {
return false;
}
}
return true;
}
int dfs(int n, int x, string &arr) {
if (x > n) {
int cnt = 0;
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
if (is(arr, l, r)) {
cnt++;
}
if (cnt > 1) {
return 0;
}
}
}
return cnt == 1 ? 1 : 0;
}
int ans = 0;
for (int i = 0; i < 3; i++) {
arr.push_back(choice[i]);
ans += dfs(n, x + 1, arr);
arr.pop_back();
}
return ans;
}
int getans(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 3;
}
if (n == 3) {
return 18;
}
return (long long)6 * (n + 1) % mod;
}
void solve() {
// for (int i = 1; i <= 10; i++) {
// string arr = " ";
// cout << "长度为: " << i << " 答案: " << dfs(i, 1, arr) << endl;
// }
cin >> n;
cout << getans(n) << endl;
}
