luoguP1132 数字生成游戏

裸的bfs。

别的题解大多用字符串,但也可以直接截取数字。

使用除法和取模可以分裂整数,乘法和加法可以合并。

举个栗子:

3141592631415926 这个8位整数从第四位(从左往右数)后面截成两个整数

先把这个数除以1000( 10(841)10^{(8-4-1)})得到前面那一个整数是 31413141

再取模10000( 108410^{8-4} ) ,得到后面的是 59265926

合并也很简单,比如上面的两个数 3141×104+5926=31410000+5926=314159263141 \times 10^4 + 5926 = 31410000 + 5926=31415926

用这两个基本操作就可以实现题目中的所有操作。

数字截取法时间复杂度较优(每个操作 O(log(n))O(log(n)) 级别比隔壁字符串 O(n)O(n) 要好上那么一点,但常数较大)。

询问次数很多,可以预处理所有可能变换出的数,每次 O(1)O(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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int powerOf10(int power) {//快速幂计算10的power次方 O(log n)
if(power == 0) return 1;
int res = 1, tmp = powerOf10(power >> 1);
if(power & 1) return tmp * tmp * 10;
return tmp * tmp;
}
inline int digit(int x) {//计算数字位数 O(log10(n))
int res = 0;
while(x > 0) {
x /= 10;
res++;
}
return res;
}
inline int get(int base, int pos) {//获取base下标为pos的数字 O(log n)
int db = digit(base);
if(pos < 0 || pos >= db) return 1;//防越界 这样不需要在bfs里特判
return base / powerOf10(digit(base) - pos - 1) % 10;
}
inline int swap(int base, int x, int y) {//交换base下标为x和y的数字 O(log n)
int px = powerOf10(digit(base) - x - 1), py = powerOf10(digit(base) - y - 1);//x,y后是10的几次方
int nx = get(base, x), ny = get(base, y);//x,y位置上对应的数
base -= nx * px;//减掉原位置的数
base -= ny * py;
base += nx * py;//互换位置加回去
base += ny * px;
return base;
}
inline int insert(int base, int pos, int x) {//在base下标pos的前方插入x O(log n)
int pivot = powerOf10(digit(base) - pos), pre = base / pivot, post = base % pivot;//找分割点并将base拆分成pre,post两部分
int pdpost = powerOf10(digit(post));
return pre * pdpost * 10 + x * pdpost + post;//合并时加入x
}
inline int erase(int base, int pos) {//删除base下标pos位置的数字 O(log n)
int pivot = powerOf10(digit(base) - pos - 1), pre = base / pivot, post = base % pivot;//分割
pre /= 10;//删除前部分最后一个数字(指定数字)
return pre * powerOf10(digit(post)) + post;//合并
}
int mem[1000010], start, n, dstart;
queue<int> q;
inline void update(int cur, int nxt) {//更新mem(答案)数组
if(mem[nxt] == -1) {//因为是bfs而且“代价”是1,所以每个点第一次搜到的就是最优解
mem[nxt] = mem[cur] + 1;
q.push(nxt);
}
}
void bfs() {
q.push(start);
memset(mem, -1, sizeof(mem));
mem[start] = 0;
while(q.size()) {//标准广搜模板
int cur = q.front();
q.pop();
int d = digit(cur);
if(d == 1) continue;//如果位数=1,那么什么也做不了
for(int i = 0; i < d; i++) {//交换操作
for(int j = i + 1; j < d; j++) {
int nxt = swap(cur, i, j);
update(cur, nxt);
}
}
for(int i = 0; i < d; i++) {//删除操作
int nxt = erase(cur, i);
update(cur, nxt);
}
if(d < dstart)//注意“位数不能超过起始位数”的条件
for(int i = 1; i < d; i++) {//插入操作
for(int j = get(cur, i - 1) + 1; j < get(cur, i); j++) {
int nxt = insert(cur, i, j);
update(cur, nxt);
}
}
}
}
int main() {
cin >> start >> n;
dstart = digit(start);
bfs();//预处理
while(n--) {
int target;
cin >> target;
cout << mem[target] << endl;
}
system("pause");
return 0;
}

luoguP1132 数字生成游戏
https://www.d0j1a1701.cc/p/876839c7/
作者
d0j1a_1701
发布于
2021年2月26日
许可协议
CC-BY-SA