【题解】洛谷P1132 数字生成游戏

裸的bfs。

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

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

举个栗子：

把 $31415926$ 这个8位整数从第四位（从左往右数）后面截成两个整数

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

再取模10000( $10^{8-4}$ ) ，得到后面的是 $5926$ 。

合并也很简单，比如上面的两个数 $3141 \times 10^4 + 5926 = 31410000 + 5926=31415926$ 。

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

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

询问次数很多，可以预处理所有可能变换出的数，每次 $O(1)$ 查询。

#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;
}