What a Ridiculous Election UVALive

题目链接：

E - What a Ridiculous Election

UVALive - 7672

题目大意：

12345 可以经过若干次操作转换为其它五位数。

操作分三种，分别为：

操作1：交换相邻两数
操作2：选择一位 +1，若大于 9 ，则对 10 取模。
操作3：选择一位 *2 ，若大于 9，则对 10 取模。
其中操作 2 最大进行 3 次，操作 3 最多进行 2 次。

对于给定的五位数，求 12345 在满足限制条件情况下，最少通过几步操作可以转换为目标五位数。若不可能，则输出 -1 。

具体思路：bfs，需要从12345作为起点向其他点跑，把所有情况都算出来、不能输入一个数作为起点。

a[i][j][k]代表12345变成i需要操作二j次，操作三k次，每一次输出遍历j和k就可以了。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 # define inf 0x3f3f3f3f

 const int maxn = 1e5+;

 int a[maxn][][];

 int sto[];

 struct node

 {

     int num;

     int add;

     int dou;

     int step;

     node() {}

     node(int xx,int yy,int zz,int kk)

     {

         num=xx;

         add=yy;

         dou=zz;

         step=kk;

     }

 };

 int cal()

 {

     int ans=;

     for(int i=; i<=; i++)

     {

         ans=ans*+sto[i];

     }

     return ans;

 }

 void chuan(int n)

 {

     sto[]=n%;

     n/=;

     sto[]=n%;

     n/=;

     sto[]=n%;

     n/=;

     sto[]=n%;

     n/=;

     sto[]=n%;

     n/=;

     for(int i=; i<=; i++)

     {

         swap(sto[i],sto[-i+]);

     }

 }

 void bfs()

 {

     queue<node>q;

     q.push(node(,,,));

     a[][][]=;

     int tmp;

     while(!q.empty())

     {

         node top=q.front();

         q.pop();

         chuan(top.num);

         if(top.add+<=)

         {

             for(int j=; j<=; j++)

             {

                 tmp=sto[j];

                 sto[j]++;

                 sto[j]%=;

                 int tt=cal();

                 if(a[tt][top.add+][top.dou]==inf)

                     q.push(node(tt,top.add+,top.dou,top.step+)),a[tt][top.add+][top.dou]=top.step+;

                 sto[j]=tmp;

             }

         }

         if(top.dou+<=)

         {

             for(int j=; j<=; j++)

             {

                 tmp=sto[j];

                 sto[j]<<=;

                 sto[j]%=;

                 int tt=cal();

                 if(a[tt][top.add][top.dou+]==inf)

                 {

                     q.push(node(tt,top.add,top.dou+,top.step+)),a[tt][top.add][top.dou+]=top.step+;

                 }

                 sto[j]=tmp;

             }

         }

         for(int j=; j<; j++)

         {

             swap(sto[j],sto[j+]);

             int tt=cal();

             if(a[tt][top.add][top.dou]==inf)

             {

                 q.push(node(tt,top.add,top.dou,top.step+)),a[tt][top.add][top.dou]=top.step+;

             }

             swap(sto[j],sto[j+]);

         }

     }

 }

 int main()

 {

     memset(a,inf,sizeof(a));

     bfs();

   //  chuan(12345);

     int n;

     int ttt ;

     while(~scanf("%d",&n))

     {

         int minn = inf;

         for(int i=; i<=; i++)

         {

             for(int j=; j<=; j++)

             {

                 minn = min( minn, a[n][i][j] );

             }

         }

         printf("%d\n",minn==inf ? - : minn);

     }

     return ;

 }

”

巴特西

What a Ridiculous Election UVALive - 7672 （BFS）

E - What a Ridiculous Election

最新文章

热门文章