HDU 1104 Remainder （BFS）-白红宇

HDU 1104 Remainder （BFS）

阅读量：4320 次

发布时间：2019-06-06

本文共 1228 字，大约阅读时间需要 4 分钟。

题目地址：

题意：给你一个n、m、k，有四种操作n+m,n-m,n*m,n%m，问你最少经过多少步，使得最后的结果=(初始n+1)%k

题解：很明显的BFS，然后我就很快写，果断RE，发现里面可能有负数，改了之后还是错了，看了discuss才发现原来要%mk，现在还是不是很懂为什么，这里discuss有人给出了解释——

解释一下为什么要%mk：

对于N来说，其中的过程会有N+m,N-m,以及N*m,按照正常的步骤来说，统一%K，但是因为有N%m的插足，

例如： (N+m-m*m%m)%k （从左到右依次执行，没有优先级）

(N%k+m%k-m%k*m%k%m%k)%k这两个是绝对不相等的

但是统一%mk是相等的，因为你%mk，是对所有的（）里的数进行的，而第二个式子中因为对除最后一个数外进行的事%mk，而其他数进行的仅是%k所以不相等。

AC代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #pragma comment(linker, "/STACK:16777216")using namespace std;typedef __int64 LL;const int N=1001005;const int M=555555;const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-7;int n,m,k,km;int ans;bool vis[N];struct xh{ int yu,step; string s;}w,e,q[N];//数组模拟队列void BFS(){ int he=0,ta=0; memset(vis,0,sizeof(vis)); w.yu=(n%km+km)%km; w.step=0; w.s=""; q[ta++]=w; vis[w.yu]=1; while(he!=ta) { e=q[he++]; if((e.yu%k+k)%k==ans) { cout<
                     
                      <
                      
                       >n>>k>>m) { if(n==0&&k==0&&m==0) break; km=k*m; ans=((n+1)%k+k)%k; BFS(); } return 0;}

转载于:https://www.cnblogs.com/james1207/p/3283493.html

你可能感兴趣的文章