[双向BFS]CodeForces 995E Number Clicker

港控/mmm° 2021-11-02 08:16 225阅读 0赞

题面

[http://codeforces.com/contest/995/problem/E][http_codeforces.com_contest_995_problem_E]

题解

双向BFS

输出路径 可以往回算 也可以存一下上一个数

求可行方案 可以两个方向交替BFS

1 #include<cstdio>
      2 #include<map>
      3 #include<queue>
      4 using namespace std;
      5 long long u,v,mod;
      6   
      7 map<int,pair<int,int> > s,t;
      8 queue<pair<int,pair<int,int> >  > p,q;
      9 inline long long ksm(long long a,long long x)
     10  {
        long long re=1;
     11   while(x)
     12    {
        if(x&1) re=re*a%mod;
     13       
     14     x>>=1;
     15     a=a*a%mod;
     16    }
     17   return re; 
     18  }
     19 void sprint(int x,int op)
     20  {
        if(op==0) return;
     21   int pre=0;
     22   if(op==1) pre=(x-1+mod)%mod; 
     23   if(op==2) pre=(x+1)%mod;      
     24   if(op==3) pre=ksm(x,mod-2)%mod;  
     25   sprint(pre,s[pre].second);
     26     
     27   printf("%d ",op);
     28  } 
     29   
     30 void tprint(int x,int op)
     31  {
        if(op==0) return;
     32     
     33   int pre=0;
     34   if(op==1) { printf("2 "); pre=(x-1+mod)%mod; }
     35   if(op==2) { printf("1 "); pre=(x+1)%mod;     }      
     36   if(op==3) { printf("3 "); pre=ksm(x,mod-2)%mod;}
     37   tprint(pre,t[pre].second);
     38  } 
     39 int main()
     40  {      
     41  scanf("%lld%lld%lld",&u,&v,&mod);
     42       
     43  p.push(make_pair(u,make_pair(0,0))); s[u]=make_pair(0,0);
     44  q.push(make_pair(v,make_pair(0,0))); t[v]=make_pair(0,0);   
     45       
     46  while(1)   
     47   {
     48     if(!p.empty())
     49      {pair<int,pair<int,int> > x=p.front(); p.pop();
     50        
     51       //printf("%d %d %d\n",x.first,x.second.first,x.second.second);
     52         
     53       if(t.find(x.first)!=t.end())
     54         {printf("%d\n",x.second.first+t[x.first].first);
     55            
     56          sprint(x.first,x.second.second);
     57            
     58          tprint(x.first,t[x.first].second);
     59            
     60          return 0;
     61         }
     62           
     63       pair<int,pair<int,int> > y=x; y.second.first++;
     64         
     65        y.first=(x.first+1)%mod;        y.second.second=1;
     66       if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}  
     67      
     68       y.first=(x.first-1+mod)%mod;    y.second.second=2;
     69       if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}
     70         
     71       if(x.first!=0)
     72        {y.first=ksm(x.first,mod-2)%mod; y.second.second=3;
     73         if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}
     74        }
     75      }
     76        
     77      if(!q.empty())
     78      {pair<int,pair<int,int> > x=q.front(); q.pop();
     79        
     80       //printf("%d %d %d\n",x.first,x.second.first,x.second.second);
     81         
     82       if(s.find(x.first)!=s.end())
     83          {printf("%d\n",x.second.first+s[x.first].first);
     84             
     85           sprint(x.first,s[x.first].second);
     86            
     87           tprint(x.first,x.second.second);
     88             
     89           return 0;
     90          }
     91         
     92       pair<int,pair<int,int> > y=x; y.second.first++;
     93         
     94       y.first=(x.first+1)%mod;       y.second.second=1;
     95       if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);} 
     96         
     97       y.first=(x.first-1+mod)%mod;   y.second.second=2;
     98       if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);}
     99         
    100       if(x.first!=0)
    101       { y.first=ksm(x.first,mod-2)%mod;y.second.second=3;
    102         if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);}
    103       }
    104      }  
    105       
    106   }     
    107 return 0;
    108  }

求操作数最少方案 要两个方向按层BFS 两个方向各自第i层状态数不一定相等

1 #include<cstdio>
      2 #include<map>
      3 #include<queue>
      4 using namespace std;
      5 long long u,v,mod;
      6   
      7 map<int,pair<int,int> > s,t;
      8 queue<pair<int,pair<int,int> >  > p,q;
      9 inline long long ksm(long long a,long long x)
     10  {
        long long re=1;
     11   while(x)
     12    {
        if(x&1) re=re*a%mod;
     13       
     14     x>>=1;
     15     a=a*a%mod;
     16    }
     17   return re; 
     18  }
     19 void sprint(int x,int op)
     20  {
        if(op==0) return;
     21   int pre=0;
     22   if(op==1) pre=(x-1+mod)%mod; 
     23   if(op==2) pre=(x+1)%mod;      
     24   if(op==3) pre=ksm(x,mod-2)%mod;  
     25   sprint(pre,s[pre].second);
     26     
     27   printf("%d ",op);
     28  } 
     29   
     30 void tprint(int x,int op)
     31  {
        if(op==0) return;
     32     
     33   int pre=0;
     34   if(op==1) { printf("2 "); pre=(x-1+mod)%mod; }
     35   if(op==2) { printf("1 "); pre=(x+1)%mod;     }      
     36   if(op==3) { printf("3 "); pre=ksm(x,mod-2)%mod;}
     37   tprint(pre,t[pre].second);
     38  } 
     39 int main()
     40  {      
     41  scanf("%lld%lld%lld",&u,&v,&mod);
     42       
     43  p.push(make_pair(u,make_pair(0,0))); s[u]=make_pair(0,0);
     44  q.push(make_pair(v,make_pair(0,0))); t[v]=make_pair(0,0);   
     45       
     46  while(1)   
     47   { int ceng=p.front().second.first;
     48     while(!p.empty() && ceng==p.front().second.first)
     49      {pair<int,pair<int,int> > x=p.front(); p.pop();
     50        
     51       //printf("%d %d %d\n",x.first,x.second.first,x.second.second);
     52         
     53       if(t.find(x.first)!=t.end())
     54         {printf("%d\n",x.second.first+t[x.first].first);
     55            
     56          sprint(x.first,x.second.second);
     57            
     58          tprint(x.first,t[x.first].second);
     59            
     60          return 0;
     61         }
     62           
     63       pair<int,pair<int,int> > y=x; y.second.first++;
     64         
     65        y.first=(x.first+1)%mod;        y.second.second=1;
     66       if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}  
     67      
     68       y.first=(x.first-1+mod)%mod;    y.second.second=2;
     69       if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}
     70         
     71       if(x.first!=0)
     72        {y.first=ksm(x.first,mod-2)%mod; y.second.second=3;
     73         if(s.find(y.first)==s.end()) {s[y.first]=y.second;  p.push(y);}
     74        }
     75      }
     76       
     77      while(!q.empty() && ceng==q.front().second.first)
     78      {pair<int,pair<int,int> > x=q.front(); q.pop();
     79        
     80       //printf("%d %d %d\n",x.first,x.second.first,x.second.second);
     81         
     82       if(s.find(x.first)!=s.end())
     83          {printf("%d\n",x.second.first+s[x.first].first);
     84             
     85           sprint(x.first,s[x.first].second);
     86            
     87           tprint(x.first,x.second.second);
     88             
     89           return 0;
     90          }
     91         
     92       pair<int,pair<int,int> > y=x; y.second.first++;
     93         
     94       y.first=(x.first+1)%mod;       y.second.second=1;
     95       if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);} 
     96         
     97       y.first=(x.first-1+mod)%mod;   y.second.second=2;
     98       if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);}
     99         
    100       if(x.first!=0)
    101       { y.first=ksm(x.first,mod-2)%mod;y.second.second=3;
    102         if(t.find(y.first)==t.end()) {t[y.first]=y.second;  q.push(y);}
    103       }
    104      }  
    105       
    106   }     
    107 return 0;
    108  }

转载于:https://www.cnblogs.com/YuXiaoze/p/11274321.html

[http_codeforces.com_contest_995_problem_E]: http://codeforces.com/contest/995/problem/E