本文共 5349 字，大约阅读时间需要 17 分钟。
题面
题解
双向BFS
输出路径 可以往回算 也可以存一下上一个数
求可行方案 可以两个方向交替BFS
1 #include 2 #include 3 #include 4 using namespace std; 5 long long u,v,mod; 6 7 map > s,t; 8 queue > > 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 > 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 > 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 > 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 > 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 2 #include 3 #include 4 using namespace std; 5 long long u,v,mod; 6 7 map > s,t; 8 queue > > 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 > 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 > 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 > 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 > 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