P1132 数字生成游戏网页链接P1132 数字生成游戏题目描述小明完成了这样一个数字生成游戏对于一个不包含0 00的数字s ss来说有以下3 33种生成新的数的规则将s ss的任意两位对换生成新的数字例如143 143143可以生成341 , 413 , 134 341,413,134341,413,134将s ss的任意一位删除生成新的数字例如143 143143可以生成14 , 13 , 43 14,13,4314,13,43在s ss的相邻两位之间s i , s i 1 s_i,s_{i 1}si,si1之间插入一个数字x xxx xx需要满足s i x s i 1 s_ixs_{i 1}sixsi1。例如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 ttt tt不包含0 00表示询问从s ss开始不断生成数字到t tt最少要进行多少次操作。任两个询问独立即上一个询问生成过的数到下一个询问都不存在只剩下初始数字s ss。输出格式共m mm行每行一个正整数对每个询问输出最少操作数如果无论如果无论也变换不成则输出− 1 -1−1。输入输出样例 #1输入 #1143 3 134 133 32输出 #11 -1 4说明/提示样例解释143 → 134 143\to 134143→134133 133133无法得到143 → 13 → 123 → 23 → 32 143\to13\to123\to23\to32143→13→123→23→32数据范围对于20 % 20\%20%的数据s 100 s 100s100对于40 % 40\%40%的数据s 1000 s 1000s1000对于40 % 40\%40%的数据m 10 m 10m10对于60 % 60\%60%的数据s 10000 s 10000s10000对于100 % 100\%100%的数据s 100000 , m ≤ 50000 s 100000,m \leq 50000s100000,m≤50000。解题思路本题是有限状态空间上的最短路径搜索问题。给定一个不含0 00的初始数字s ss通过三种操作交换任意两位、删除任意一位、在相邻两位间插入满足大小关系的数字生成新数字且生成数字的位数不能超过初始数字的位数。由于所有数字均不含0 00且位数有限s 100000 s 100000s100000最多 5 位所有可能生成的数字数量很少最多约9 5 59049 9^5 590499559049个因此可以从初始数字s ss出发使用 BFS 预处理出到达所有可达数字的最少操作次数然后对每个询问直接查表输出。1. 问题等价转化状态定义每个不含0 00的整数即为一个状态。初始状态为s ss。状态转移从当前数字c u r curcur出发可以执行三种操作生成新数字交换选择任意两位交换生成新数字。删除若当前位数 1 11删除任意一位生成新数字。插入若当前位数 初始位数L LL在任意相邻两位s i , s i 1 s_i, s_{i1}si,si1之间插入一个整数x xx满足s i x s i 1 s_i x s_{i1}sixsi1生成新数字。目标对于每个询问t tt求从s ss到t tt的最少操作次数即最短路径长度。若不可达则输出− 1 -1−1。关键观察所有操作都不产生0 00且位数不超过L LL因此状态空间封闭且有限可以预先搜索所有可达状态。2. 算法实现BFS 预处理输入与初始化读入初始数字字符串s记录其长度L s.length()并将s转换为整数start。创建距离数组d[M]M 1000000足够全部初始化为-1表示未访问。d[start] 0将start入队。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更新距离并入队。回答询问读入询问个数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^49192939495≈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[M10]记录最短距离queuell q用于 BFS。bfs(st)函数memset(d, -1, sizeof(d))d[st] 0q.push(st)。循环取出队首cur转为字符串tlen t.length()。交换for i0..len-1, ji1..len-1交换后转整数k若未访问则更新距离并入队。删除若len 1for i0..len-1删除后转整数k更新。插入若len lfor i1..len-1for c t[i-1]1; c t[i]; c插入后转整数k更新。主函数scanf(%s%lld, ch, m)读入初始数字和询问数s chl s.length()。调用bfs(atoi(ch))。循环m次读入x输出d[x]。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;string s;charch[7];ll m,l,x;ll d[M10];queuellq;voidbfs(ll st){memset(d,-1,sizeof(d));d[st]0;q.push(st);ll k;while(!q.empty()){ll curq.front();q.pop();string tto_string(cur);ll lent.length();for(ll i0;ilen;i){for(ll ji1;jlen;j){string ut;swap(u[i],u[j]);kstoi(u);if(!~d[k]){d[k]d[cur]1;q.push(k);}}}for(ll i0;ilenlen1;i){string ut;u.erase(i,1);kstoi(u);if(!~d[k]){d[k]d[cur]1;q.push(k);}}if(lenl)continue;for(ll i1;ilen;i){for(charct[i-1]1;ct[i];c){string ut;u.insert(i,1,c);kstoi(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);sch;ls.length();bfs(atoi(ch));for(ll i1;im;i){scanf(%lld,x);printf(%lld\n,d[x]);}return0;}
