企业官网建设流程全解析

P1132 数字生成游戏

网页链接

P1132 数字生成游戏

题目描述

小明完成了这样一个数字生成游戏，对于一个不包含0 00的数字s ss来说，有以下3 33种生成新的数的规则：

1. 将s ss的任意两位对换生成新的数字，例如143 143143可以生成341 , 413 , 134 341,413,134341,413,134；

2. 将s ss的任意一位删除生成新的数字，例如143 143143可以生成14 , 13 , 43 14,13,4314,13,43；

3. 在s ss的相邻两位之间s i , s i + 1 s_i,s_{i + 1}si​,si+1​之间插入一个数字x xx，x xx需要满足s i < x < s i + 1 s_i<x<s_{i + 1}si​<x<si+1​。例如143 143143可以生成1243 , 1343 1243,13431243,1343，但是不能生成1143 , 1543 1143,15431143,1543等。

现在小明想知道，在这个生成法则下，从s ss开始，每次生成一个数，可以用然后用新生成的数生成另外一个数，不断生成直到生成t tt至少需要多少次生成操作。

另外，小明给规则3 33又加了一个限制，即生成数的位数不能超过初始数s ss的位数。若s ss是143 143143，那么1243 12431243与1343 13431343都是无法生成的；若s ss为1443 14431443，那么可以将s ss删除变为143 143143，再生成1243 12431243或1343 13431343。

输入格式

第一行包含1 11个正整数，为初始数字s ss。

第二行包含一个正整数m mm，为询问个数。

接下来m mm行，每行一个整数t tt（t tt不包含0 00），表示询问从s ss开始不断生成数字到t tt最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字s ss。

输出格式

共m mm行，每行一个正整数，对每个询问输出最少操作数，如果无论如果无论也变换不成，则输出− 1 -1−1。

输入输出样例 #1

输入 #1

143 3 134 133 32

输出 #1

1 -1 4

说明/提示

样例解释

143 → 134 143\to 134143→134

133 133133无法得到

143 → 13 → 123 → 23 → 32 143\to13\to123\to23\to32143→13→123→23→32

数据范围

对于20 % 20\%20%的数据，s < 100 s < 100s<100；
对于40 % 40\%40%的数据，s < 1000 s < 1000s<1000；
对于40 % 40\%40%的数据，m < 10 m < 10m<10；
对于60 % 60\%60%的数据，s < 10000 s < 10000s<10000；
对于100 % 100\%100%的数据，s < 100000 , m ≤ 50000 s < 100000,m \leq 50000s<100000,m≤50000。

解题思路

本题是有限状态空间上的最短路径搜索问题。给定一个不含0 00的初始数字s ss，通过三种操作（交换任意两位、删除任意一位、在相邻两位间插入满足大小关系的数字）生成新数字，且生成数字的位数不能超过初始数字的位数。由于所有数字均不含0 00且位数有限（s < 100000 s < 100000s<100000，最多 5 位），所有可能生成的数字数量很少（最多约9 5 = 59049 9^5 = 5904995=59049个），因此可以从初始数字s ss出发，使用 BFS 预处理出到达所有可达数字的最少操作次数，然后对每个询问直接查表输出。

1. 问题等价转化

• 状态定义：每个不含0 00的整数即为一个状态。初始状态为s ss。
• 状态转移：从当前数字c u r curcur出发，可以执行三种操作生成新数字：
  1. 交换：选择任意两位交换，生成新数字。
  2. 删除：若当前位数> 1 >1>1，删除任意一位，生成新数字。
  3. 插入：若当前位数< <<初始位数L LL，在任意相邻两位s i , s i + 1 s_i, s_{i+1}si​,si+1​之间插入一个整数x xx，满足s i < x < s i + 1 s_i < x < s_{i+1}si​<x<si+1​，生成新数字。
• 目标：对于每个询问t tt，求从s ss到t tt的最少操作次数（即最短路径长度）。若不可达则输出− 1 -1−1。
• 关键观察：所有操作都不产生0 00，且位数不超过L LL，因此状态空间封闭且有限，可以预先搜索所有可达状态。

2. 算法实现（BFS 预处理）

1. 输入与初始化：
   • 读入初始数字字符串s，记录其长度L = s.length()，并将s转换为整数start。
   • 创建距离数组d[M]（M = 1000000足够），全部初始化为-1，表示未访问。
   • d[start] = 0，将start入队。
2. BFS 搜索：
   • 当队列非空时，取出队首数字cur，将其转换为字符串t，当前操作次数为d[cur]。
   • 交换操作：双重循环遍历所有位置对( i , j ) (i, j)(i,j)，交换t[i]和t[j]得到新字符串，转为整数k。若d[k] == -1，则d[k] = d[cur] + 1，入队。
   • 删除操作：若len > 1，遍历每个位置i ii，删除t[i]得到新字符串，转为整数k，同样更新距离并入队。
   • 插入操作：若len < L，遍历每对相邻位置( i − 1 , i ) (i-1, i)(i−1,i)，枚举插入字符c从t[i-1]+1到t[i]-1，在位置i ii插入c得到新字符串，转为整数k，更新距离并入队。
3. 回答询问：
   • 读入询问个数m，对于每个询问t，直接输出d[t]（若为-1则表示不可达）。

3. 复杂度分析

• 状态数：最多为所有不含0 00且位数不超过L LL的数字个数。L ≤ 5 L \le 5L≤5，总数约9 1 + 9 2 + 9 3 + 9 4 + 9 5 ≈ 6.6 × 10 4 9^1 + 9^2 + 9^3 + 9^4 + 9^5 \approx 6.6 \times 10^491+92+93+94+95≈6.6×104。
• 每个状态的转移：
  • 交换：O ( L 2 ) O(L^2)O(L2)，L ≤ 5 L \le 5L≤5，最多 10 次。
  • 删除：O ( L ) O(L)O(L)，最多 5 次。
  • 插入：O ( L × 9 ) O(L \times 9)O(L×9)，最多 45 次。
  • 总转移次数约60 6060次，状态总数约6.6 × 10 4 6.6 \times 10^46.6×104，总运算量约4 × 10 6 4 \times 10^64×106，非常小。
• 时间复杂度：O ( 状态数 × L 2 ) O(\text{状态数} \times L^2)O(状态数×L2)，实际运行极快。
• 空间复杂度：距离数组d大小约10 6 10^6106，字符串操作临时空间很小，满足限制。

总结

本题利用数字位数少、状态空间有限的特点，通过 BFS 从初始数字出发预处理所有可达数字的最短操作次数。三种操作的实现直接模拟题意，注意插入操作需要判断位数限制和大小关系。最后对每个询问O ( 1 ) O(1)O(1)查表输出，高效且简洁。

代码简要说明

• 全局变量：string s存储初始数字字符串，char ch[7]用于读取，ll m, l分别为询问数和初始位数，ll d[M+10]记录最短距离，queue<ll> q用于 BFS。
• bfs(st)函数：
  • memset(d, -1, sizeof(d))，d[st] = 0，q.push(st)。
  • 循环取出队首cur，转为字符串t，len = t.length()。
  • 交换：for i=0..len-1, j=i+1..len-1，交换后转整数k，若未访问则更新距离并入队。
  • 删除：若len > 1，for i=0..len-1，删除后转整数k，更新。
  • 插入：若len < l，for i=1..len-1，for c = t[i-1]+1; c < t[i]; c++，插入后转整数k，更新。
• 主函数：
  • scanf("%s%lld", ch, &m)读入初始数字和询问数，s = ch，l = s.length()。
  • 调用bfs(atoi(ch))。
  • 循环m次，读入x，输出d[x]。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;string s;charch[7];ll m,l,x;ll d[M+10];queue<ll>q;voidbfs(ll st){memset(d,-1,sizeof(d));d[st]=0;q.push(st);ll k;while(!q.empty()){ll cur=q.front();q.pop();string t=to_string(cur);ll len=t.length();for(ll i=0;i<len;i++){for(ll j=i+1;j<len;j++){string u=t;swap(u[i],u[j]);k=stoi(u);if(!~d[k]){d[k]=d[cur]+1;q.push(k);}}}for(ll i=0;i<len&&len>1;i++){string u=t;u.erase(i,1);k=stoi(u);if(!~d[k]){d[k]=d[cur]+1;q.push(k);}}if(len==l)continue;for(ll i=1;i<len;i++){for(charc=t[i-1]+1;c<t[i];c++){string u=t;u.insert(i,1,c);k=stoi(u);if(!~d[k]){d[k]=d[cur]+1;q.push(k);}}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%s%lld",ch,&m);s=ch;l=s.length();bfs(atoi(ch));for(ll i=1;i<=m;i++){scanf("%lld",&x);printf("%lld\n",d[x]);}return0;}