免费制作网站用什么做,asp 网站建设教程,wordpress腾讯云插件,公司网页链接1001 Hide-And-Seek Game (hdu.edu.cn)
题意#xff1a;
给定一棵树和两条路径#xff0c;每条路径都有起点和终点#xff0c;起始时起点有人#xff0c;每隔一秒都会往终点走一步#xff0c;会从起点走向终点再会起点这样不断地周期性地走#xff0c;让你求一点#…1001 Hide-And-Seek Game (hdu.edu.cn)
题意
给定一棵树和两条路径每条路径都有起点和终点起始时起点有人每隔一秒都会往终点走一步会从起点走向终点再会起点这样不断地周期性地走让你求一点使得两个人能在这点相遇且花的时间最少 思路
首先答案一定是两条路径相交的点中的一个因此可以把一条路径标记一下然后对于另一条路径去check是否重合
对于树链的操作只需要求出LCA分成两部分暴力跳即可
找出重合的点即可能是答案的点之后需要处理怎么样才能使时间最少 比赛的时候只是分成四种情况讨论并没有解方程赛后调了很久也没有全对但是只是几个数据没过也根本调不出来
那就这样吧反正大部分都对了 Code
#include bits/stdc.h#define int long longusing namespace std;const int mxn3e310;
const int mxe3e310;
const int Inf1e18;struct ty{int to,next;
}edge[mxe2];int N,M,Q,u,v,s1,t1,s2,t2,k1,k2;
int tot0;
int a[mxn];
int head[mxn],dep[mxn],F[mxn][33];void add(int u,int v){edge[tot].tov;edge[tot].nexthead[u];head[u]tot;
}
void G_init(){tot0;for(int i0;iN;i){head[i]-1;dep[i]0;for(int j0;j30;j) F[i][j]0;}
}
void dfs(int u,int fa){dep[u]dep[fa]1;F[u][0]fa;for(int j1;j30;j) F[u][j]F[F[u][j-1]][j-1];for(int ihead[u];~i;iedge[i].next){if(edge[i].tofa) continue;dfs(edge[i].to,u);}
}
int lca(int u,int v){if(dep[u]dep[v]) swap(u,v);for(int j30;j0;j--){if(dep[F[u][j]]dep[v]){uF[u][j];}}if(uv) return u;for(int j30;j0;j--){if(F[u][j]!F[v][j]){uF[u][j];vF[v][j];}}return F[u][0];
}
int dist(int u,int v){return dep[u]dep[v]-2*dep[lca(u,v)];
}
int exgcd(int a,int b,int k1,int k2){if(!b){k11;k20;return a;}int dexgcd(b,a%b,k2,k1);k2-(a/b)*k1;return d;
}
void solve(){cinNM;G_init();for(int i1;iN-1;i){cinuv;add(u,v);add(v,u);}dfs(1,0);while(M--){cins1t1s2t2;int Glca(s1,t1);int s11s1,t11t1;if(dep[s11]dep[t11]) swap(s11,t11);int curs11;mapint,int mp;//链上的点int L10,L20;while(cur!G){mp[cur]1;L1;curF[cur][0];}curt11;while(cur!G){mp[cur]1;L1;curF[cur][0];}mp[G]1;//L1;int s22s2,t22t2;if(dep[s22]dep[t22]) swap(s22,t22);curs22;int G2lca(s22,t22);vectorint V;//路径交点while(cur!G2){L2;if(mp.count(cur)) V.push_back(cur);curF[cur][0];}curt22;while(cur!G2){L2;if(mp.count(cur)) V.push_back(cur);curF[cur][0];}if(mp.count(G2)) V.push_back(G2);//L2;if(V.empty()){cout-1\n;continue;}setpairint,int ansv;for(auto x:V){//13int D1exgcd(2*L1,-2*L2,k1,k2);int N2dist(s2,x)-dist(s1,x);k1k1*N2/D1;if(N2%D10){k1k1*N2/D1;//包含0这个解不需要%rransv.insert({dist(s1,x)2*k1*L1,x});}//14int D2exgcd(2*L1,-2*L2,k1,k2);int N3L2dist(t2,x)-dist(s1,x);k1k1*N3/D2;if(N3%D20){k1k1*N3/D2;ansv.insert({dist(s1,x)2*k1*L1,x});}//23int D3exgcd(2*L1,-2*L2,k1,k2);int N4dist(s2,x)-L1-dist(x,t1);k1k1*N4/D3;if(N4%D30){k1k1*N4/D3;ansv.insert({L1dist(x,t1)2*k1*L1,x});}//24int D4exgcd(2*L1,-2*L2,k1,k2);int N5L2dist(t2,x)-L1-dist(x,t1);k1k1*N5/D4;if(N5%D40){k1k1*N5/D4;ansv.insert({L1dist(x,t1)2*k1*L1,x});}}if(ansv.empty()) cout-1\n;else{cout(*ansv.begin()).second\n;}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __1;cin__;while(__--)solve();return 0;
} 标程
#includecstdio
#includealgorithm
#includecmath
#define M 5005
using namespace std;
struct E{int to,nx;
}edge[M1];
int tot,head[M];
void Addedge(int a,int b){edge[tot].tob;edge[tot].nxhead[a];head[a]tot;
}
int sz[M],son[M],top[M],dep[M];
int Dfn[M],Low[M],tot_dfs;
int fa[M];
void dfs(int now){Dfn[now]tot_dfs;sz[now]1;son[now]0;for(int ihead[now];i;iedge[i].nx){int nxtedge[i].to;if(nxtfa[now])continue;fa[nxt]now;dep[nxt]dep[now]1;dfs(nxt);sz[now]sz[nxt];if(sz[son[now]]sz[nxt])son[now]nxt;}Low[now]tot_dfs;
}
void dfs_top(int now){if(son[now]){top[son[now]]top[now];dfs_top(son[now]);}for(int ihead[now];i;iedge[i].nx){int nxtedge[i].to;if(nxtfa[now]||nxtson[now])continue;top[nxt]nxt;dfs_top(nxt);}
}
int LCA(int a,int b){while(top[a]!top[b]){if(dep[top[a]]dep[top[b]])bfa[top[b]];else afa[top[a]];}return dep[a]dep[b]?a:b;
}
bool In(int x,int y){return Dfn[y]Dfn[x]Dfn[x]Low[y];
}
int mark[M];
struct Point{int a,b;
};
Point Data[M][2];
int exgcd(int a,int b,int x,int y){int da; if(b0) x1,y0; else{dexgcd(b,a%b,y,x),y-a/b*x;}return d;
}
int Get_ans(Point p1,Point p2){int valp2.b-p1.b;val%p2.a;while(val0)valp2.a;while(valp2.a)val-p2.a;int ap1.a,b-p2.a;int x,y,dexgcd(a,b,x,y);if(val%d!0)return 1e9;x*val/d;y*val/d;int pb/d,qa/d;if(x0){int kceil((1.0-x)/p);xp*k,y-q*k;}else if(x0){int k(x-1)/p;x-p*k,yq*k;}return a*xp1.b;
}
int main(){int T;scanf(%d,T);while(T--){int n,m;tot0;scanf(%d%d,n,m);tot_dfs0;for(int i1;in;i)head[i]mark[i]0;for(int i1;in;i){int a,b;scanf(%d%d,a,b);Addedge(a,b);Addedge(b,a);}dfs(1);top[1]1;dfs_top(1);for(int step1;stepm;step){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);if(ac){printf(%d\n,a);continue;}int x1LCA(a,b),x2LCA(c,d);if(dep[x1]dep[x2]){swap(a,c);swap(b,d);swap(x1,x2);}if(!In(a,x2)!In(b,x2)){puts(-1);continue;}int d1dep[a]dep[b]-2*dep[x1],d2dep[c]dep[d]-2*dep[x2];int pa;while(1){Data[p][0](Point){2*d1,dep[a]-dep[p]};Data[p][1](Point){2*d1,2*d1-(dep[a]-dep[p])};mark[p]step;if(px1)break;pfa[p];}pb;while(p!x1){Data[p][0](Point){2*d1,d1-(dep[b]-dep[p])};Data[p][1](Point){2*d1,d1(dep[b]-dep[p])};mark[p]step;pfa[p];}int ans_val1e9,ans-1;pc;while(1){Point p1(Point){2*d2,dep[c]-dep[p]};Point p2(Point){2*d2,2*d2-(dep[c]-dep[p])};if(mark[p]step){int res1e9;resmin(min(Get_ans(p1,Data[p][0]),Get_ans(p1,Data[p][1])),min(Get_ans(p2,Data[p][0]),Get_ans(p2,Data[p][1])));if(resans_val){ans_valres;ansp;}}if(px2)break;pfa[p];}pd;while(p!x2){Point p1(Point){2*d2,d2-(dep[d]-dep[p])};Point p2(Point){2*d2,d2(dep[d]-dep[p])};if(mark[p]step){int res1e9;resmin(min(Get_ans(p1,Data[p][0]),Get_ans(p1,Data[p][1])),min(Get_ans(p2,Data[p][0]),Get_ans(p2,Data[p][1])));if(resans_val){ans_valres;ansp;}}pfa[p];}printf(%d\n,ans);}}return 0;
}
