題目描述

小明完成了這樣一個數字生成游戲，對于一個不包含00的數字ss來說，有以下33種生成新的數的規則：

1. 將ss的任意兩位對換生成新的數字，例如143143可以生成314,413,134314,413,134；

2. 將ss的任意一位刪除生成新的數字，例如143143可以生成14,13,4314,13,43

3. 在ss的相鄰兩位之間s_i,s_{i + 1}si?,si+1?之間插入一個數字x，x需要滿足s_i<x<s_{i + 1}si?<x<si+1?。例如143143可以生成1243,13431243,1343，但是不能生成1143,15431143,1543等。

現在小明想知道，在這個生成法則下，從ss開始，每次生成一個數，可以用然后用新生成的數生成另外一個數，不斷生成直到生成tt至少需要多少次生成操作。

另外，小明給規則33又加了一個限制，即生成數的位數不能超過初始數ss的位數。若ss是143143，那么12431243與13431343都是無法生成的；若ss為14431443，那么可以將ss刪除變為143143，再生成12431243或13431343。

輸入輸出格式

輸入格式：

第一行包含11個正整數，為初始數字ss。

第二行包含一個正整數mm，為詢問個數。

接下來mm行，每行一個整數tt（tt不包含00），表示詢問從ss開始不斷生成數字到tt最少要進行多少次操作。任兩個詢問獨立，即上一個詢問生成過的數到下一個詢問都不存在，只剩下初始數字ss。

輸出格式：

共mm行，每行一個正整數，對每個詢問輸出最少操作數，如果無論如果無論也變換不成，則輸出-1?1。

輸入輸出樣例

輸入樣例#1： 復制

143
3
134
133
32

輸出樣例#1： 復制

1
-1
4

說明

143143 ->134134

133133無法得到

143143 -> 1313 -> 123123 ->2323->3232

對于20%20%的數據，s < 100s<100；
對于40%40%的數據，s < 1000s<1000；
對于40%40%的數據，m < 10m<10；
對于60%60%的數據，s < 10000s<10000；
對于100%100%的數據，s < 100000,m ≤ 50000s<100000,m≤50000。

---

爆搜
沒了

---

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long longusing namespace std;
queue <int>q;
int i,m,n,j,k,a[2000011],b[2000011],s,f[10001],sdf,cnt;int zh(int *a,int k)
{int ans=0;for(int i=k;i>=1;i--)ans=ans*10+a[i];cnt+=1;return ans;
}void bfs()
{b[s]=1;q.push(s);while(q.size()){int s=q.front(); q.pop();int k=s,l=0;while(k) l+=1,f[l]=k%10,k/=10;for(int k=s,i=1,d=10;i<=l;i++,d*=10){int t=k/d*d/10, x=k%(d/10);int y=t+x;if(!b[y]) b[y]=1, a[y]=a[s]+1, q.push(y);}if(l!=n){for(int k=s,i=1,d=10;i<l;i++,d*=10){int t=k/d, x=k%d, z=k/d%10; int y=k%d/(d/10);for(int j=z+1; j<y;j++){int r=t*d*10+j*d+x;                     if(!b[r]) b[r]=1, a[r]=a[s]+1, q.push(r);}}}for(int i=1;i<=l;i++)for(int j=1;j<=l;j++){if(f[i]==f[j]) continue;swap(f[i],f[j]);int r=zh(f,l);if(!b[r]) b[r]=1, a[r]=a[s]+1, q.push(r);swap(f[i],f[j]);}}
}int main()
{scanf("%d",&s);k=s; while(k) k/=10, n+=1;bfs();scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d",&k);if(!b[k]) printf("-1\n");else printf("%d\n",a[k]);}
}

轉載于:https://www.cnblogs.com/ZUTTER/p/9881535.html

總結

以上是生活随笔為你收集整理的P1132 数字生成游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。