网站开发及服务合同模板,北京备案网站负责人,前端面试题,如皋网站定制解析
考虑一个三元组(x,y,z)(x,y,z)(x,y,z)#xff0c;看它能如何跳 要么是yyy往左右跳#xff0c;左右边界会变大 要么是两边往中间跳#xff0c;由于最多跨过一个棋子#xff0c;所以左右边界会变小 当三点等距时#xff0c;无法往中间跳 于是我们惊喜的发现#xff1…解析
考虑一个三元组(x,y,z)(x,y,z)(x,y,z)看它能如何跳 要么是yyy往左右跳左右边界会变大 要么是两边往中间跳由于最多跨过一个棋子所以左右边界会变小 当三点等距时无法往中间跳 于是我们惊喜的发现可以互相转移的状态形成了一个二叉树形结构 往中间跳的时候相当于跳父亲往两边跳相当于跳儿子
当且仅当两个状态的根相同时有解 又由于这个跳的操作是可逆的所以我们的问题就可以转化为两个点在树上的距离 于是我们就可以用类似倍增求LCA的思路解决本题
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e6100;
const double eps1e-6;
const int mod1333331;
inline ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return f*x;
}int n,m,p;
struct node{ll a,b,c;inline void solve(){if(bc) swap(b,c);if(ab) swap(a,b);if(bc) swap(b,c);return;}bool operator (const node u)const{return au.abu.bcu.c;}bool operator ! (const node u)const{return a!u.a||b!u.b||c!u.c;}
}u,v;
node walk(node o,ll lft){if(lft0) return o;ll d1o.b-o.a,d2o.c-o.b;if(d1d2) return o;if(d1d2){int kmin((d2-1)/d1,lft);o.ak*d1,o.bk*d1;return walk(o,lft-k);}else{int kmin((d1-1)/d2,lft);o.b-k*d2;o.c-k*d2;return walk(o,lft-k);}
}
int dep(node o){int st0,ed2e9;while(sted){int mid(sted)1;if(walk(o,mid1)walk(o,mid)) edmid;else stmid1;}return st;
}
void print(node o){printf((%lld %lld %lld)\n,o.a,o.b,o.c);return;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifu(node){read(),read(),read()};v(node){read(),read(),read()};u.solve(),v.solve();if(walk(u,2e9)!walk(v,2e9)) printf(NO\n);else{printf(YES\n);int aadep(u),bbdep(v);if(aabb) swap(u,v);int numabs(aa-bb);int ansnum;for(int k30;k0;k--){if(num(1k)) uwalk(u,1k),num-(1k);}if(uv){printf(%d\n,ans);return 0;}//printf(-- ans%d\n,ans);//print(u);print(v);for(int k30;k0;k--){node uuwalk(u,1k),vvwalk(v,1k);if(uuvv) continue;uuu;vvv;ans(1(k1));}printf(%d\n,ans2);}return 0;
}
/*4a1 22 31 33 4
*/
