【树链+EXGCD】杭电多校第一场 A

这篇具有很好参考价值的文章主要介绍了【树链+EXGCD】杭电多校第一场 A。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1001 Hide-And-Seek Game (hdu.edu.cn)

题意:

给定一棵树和两条路径,每条路径都有起点和终点,起始时起点有人,每隔一秒都会往终点走一步,会从起点走向终点再会起点这样不断地周期性地走,让你求一点,使得两个人能在这点相遇且花的时间最少

【树链+EXGCD】杭电多校第一场 A,图论,数学,算法

 

思路:

首先答案一定是两条路径相交的点中的一个,因此可以把一条路径标记一下,然后对于另一条路径去check是否重合

对于树链的操作,只需要求出LCA,分成两部分,暴力跳即可

找出重合的点,即可能是答案的点之后,需要处理怎么样才能使时间最少

【树链+EXGCD】杭电多校第一场 A,图论,数学,算法

比赛的时候只是分成四种情况讨论,并没有解方程,赛后调了很久也没有全对,但是只是几个数据没过,也根本调不出来

那就这样吧,反正大部分都对了 (

Code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mxn=3e3+10;
const int mxe=3e3+10;
const int Inf=1e18;

struct ty{
	int to,next;
}edge[mxe<<2];

int N,M,Q,u,v,s1,t1,s2,t2,k1,k2;
int tot=0;
int a[mxn];
int head[mxn],dep[mxn],F[mxn][33];

void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void G_init(){
	tot=0;
	for(int i=0;i<=N;i++){
		head[i]=-1;
        dep[i]=0;
        for(int j=0;j<=30;j++) F[i][j]=0;
	}
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    F[u][0]=fa;
    for(int j=1;j<=30;j++) F[u][j]=F[F[u][j-1]][j-1];
    for(int i=head[u];~i;i=edge[i].next){
        if(edge[i].to==fa) continue;
        dfs(edge[i].to,u);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int j=30;j>=0;j--){
        if(dep[F[u][j]]>=dep[v]){
            u=F[u][j];
        }
    }
    if(u==v) return u;
    for(int j=30;j>=0;j--){
        if(F[u][j]!=F[v][j]){
            u=F[u][j];
            v=F[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){
        k1=1;k2=0;
        return a;
    }
    int d=exgcd(b,a%b,k2,k1);
    k2-=(a/b)*k1;
    return d;
}
void solve(){
	cin>>N>>M;
	G_init();
    for(int i=1;i<=N-1;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    while(M--){
        cin>>s1>>t1>>s2>>t2;
        int G=lca(s1,t1);
        int s11=s1,t11=t1;
        if(dep[s11]<dep[t11]) swap(s11,t11);
        int cur=s11;
        map<int,int> mp;
        //链上的点
        int L1=0,L2=0;
        while(cur!=G){
            mp[cur]=1;
            L1++;
            cur=F[cur][0];
        }
        cur=t11;
        while(cur!=G){
            mp[cur]=1;
            L1++;
            cur=F[cur][0];
        }
        mp[G]=1;
        //L1++;
        int s22=s2,t22=t2;
        if(dep[s22]<dep[t22]) swap(s22,t22);
        cur=s22;
        int G2=lca(s22,t22);
        vector<int> V;
        //路径交点
        while(cur!=G2){
            L2++;
            if(mp.count(cur)) V.push_back(cur);
            cur=F[cur][0];
        }
        cur=t22;
        while(cur!=G2){
            L2++;
            if(mp.count(cur)) V.push_back(cur);
            cur=F[cur][0];
        }
        if(mp.count(G2)) V.push_back(G2);
        //L2++;
        if(V.empty()){
            cout<<-1<<'\n';
            continue;
        }
        set<pair<int,int> > ansv;
        for(auto x:V){
            //1==3
            int D1=exgcd(2*L1,-2*L2,k1,k2);
            int N2=dist(s2,x)-dist(s1,x);
            k1=k1*N2/D1;
            if(N2%D1==0){
                k1=k1*N2/D1;
                //包含0这个解,不需要%r+r
                ansv.insert({dist(s1,x)+2*k1*L1,x});
            }
            //1==4
            int D2=exgcd(2*L1,-2*L2,k1,k2);
            int N3=L2+dist(t2,x)-dist(s1,x);
            k1=k1*N3/D2;
            if(N3%D2==0){
                k1=k1*N3/D2;
                ansv.insert({dist(s1,x)+2*k1*L1,x});
            }
            //2==3
            int D3=exgcd(2*L1,-2*L2,k1,k2);
            int N4=dist(s2,x)-L1-dist(x,t1);
            k1=k1*N4/D3;
            if(N4%D3==0){
                k1=k1*N4/D3;
                ansv.insert({L1+dist(x,t1)+2*k1*L1,x});
            }
            //2==4
            int D4=exgcd(2*L1,-2*L2,k1,k2);
            int N5=L2+dist(t2,x)-L1-dist(x,t1);
            k1=k1*N5/D4;
            if(N5%D4==0){
                k1=k1*N5/D4;
                ansv.insert({L1+dist(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;
}

 

标程:文章来源地址https://www.toymoban.com/news/detail-596546.html

#include<cstdio>
#include<algorithm>
#include<cmath>
#define M 5005
using namespace std;
struct E{
	int to,nx;
}edge[M<<1];
int tot,head[M];
void Addedge(int a,int b){
	edge[++tot].to=b;
	edge[tot].nx=head[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 i=head[now];i;i=edge[i].nx){
		int nxt=edge[i].to;
		if(nxt==fa[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 i=head[now];i;i=edge[i].nx){
		int nxt=edge[i].to;
		if(nxt==fa[now]||nxt==son[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]])b=fa[top[b]];
		else a=fa[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 d=a; if(b==0) x=1,y=0; else{
		d=exgcd(b,a%b,y,x),y-=a/b*x;
	}
	return d;
}
int Get_ans(Point p1,Point p2){
	int val=p2.b-p1.b;
	val%=p2.a;
	while(val<0)val+=p2.a;
	while(val>p2.a)val-=p2.a;
	int a=p1.a,b=-p2.a;
	int x,y,d=exgcd(a,b,x,y);
	if(val%d!=0)return 1e9;
	x*=val/d;y*=val/d;
	int p=b/d,q=a/d;
	if(x<0){
		int k=ceil((1.0-x)/p);
		x+=p*k,y-=q*k;
	}else if(x>=0){
		int k=(x-1)/p;
		x-=p*k,y+=q*k;
	}
	return a*x+p1.b;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		tot=0;
		scanf("%d%d",&n,&m);
		tot_dfs=0;
		for(int i=1;i<=n;i++)head[i]=mark[i]=0;
		for(int i=1;i<n;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 step=1;step<=m;step++){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(a==c){printf("%d\n",a);continue;}
			int x1=LCA(a,b),x2=LCA(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 d1=dep[a]+dep[b]-2*dep[x1],d2=dep[c]+dep[d]-2*dep[x2];
			int p=a;
			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(p==x1)break;
				p=fa[p];
			}
			p=b;
			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;
				p=fa[p];
			}
			
			int ans_val=1e9,ans=-1;
			p=c;
			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 res=1e9;
					res=min(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(res<ans_val){
						ans_val=res;
						ans=p;
					}
				}
				if(p==x2)break;
				p=fa[p];
			}
			p=d;
			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 res=1e9;
					res=min(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(res<ans_val){
						ans_val=res;
						ans=p;
					}
				}
				p=fa[p];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

到了这里,关于【树链+EXGCD】杭电多校第一场 A的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 23.8.8 杭电暑期多校7部分题解

    题目大意 有两个玩家和一棵树,初始状态玩家一和玩家二分别在两个点 x ,   y x,space y x ,   y ,每次操作可以走一个与当前点有连边并且双方都没走到过的点,问最后是谁赢 解题思路 因为不能走走过的点,因此每个人走的路径一定是一条链 很明显当玩家一不选择往与玩家二

    2024年02月13日
    浏览(36)
  • 题解 | #1005.List Reshape# 2023杭电暑期多校9

    签到题 按一定格式给定一个纯数字一维数组,按给定格式输出成二维数组。 读入初始数组字符串,将每个数字分离,按要求输出即可 参考代码为已AC代码主干,其中部分功能需读者自行实现

    2024年02月12日
    浏览(43)
  • 《蓝桥杯真题》:2021单片机省赛第一场(第十二 / 12届第一场)(另一种代码风格)

    注意: 代码实现方面 : ①注意控制温度参数temp_para范围 ②DAC输出时,注意写入的数字IIC_SendByte(temp)中temp范围在 0~255 ; 源文件修改方面 : ①官方给的iic.h中使用的时C51的头文件\\\"reg52.h\\\",我们需要 修改为 对应的15系列 头文件\\\"STC15F2K60S2.h\\\" ,这样才可以使用其中的一些特殊位寄

    2023年04月08日
    浏览(50)
  • 2022百度之星第一场初赛

    题目描述 题目思路 题目代码 2022百度之星第一场初赛题解

    2024年02月15日
    浏览(38)
  • 蓝桥杯 第一场算法双周赛题解(前五题)

    题目链接在此😁:第 1 场算法双周赛 - 蓝桥云课 为什么只有前5道题的题解呢?(懂的都懂~🤐) 考察:简单逻辑判断 问题描述 小蓝和小桥玩斗地主,小蓝只剩四张牌了,他想知道是否是“三带一”牌型。 所胃三带一”牌型,即四张手牌中,有三张牌一样,另外一张不与其

    2024年02月08日
    浏览(45)
  • 「蓝桥·算法双周赛」第一场公开赛【待补题填坑】

    给定四个字符,判断是否其中有三个相同,另一个与他们不同  二叉树性质问题,不了解二叉树也完全可以做。 要注意的是每次都从第一行的第一个点开始走,给一个字符串按照它走,输出最后的结果就行。 往左走坐标就变成了2*pos-1,往右就变成了2*pos 画个树理解一下就好

    2024年02月07日
    浏览(51)
  • AtCoder Beginner Contest 292 (A - E) 记录第一场ABC

    本来晚上在打Acwing周赛,最后一题Trie想不出来咋写,看群里有人说ABC要开始了,想着没打过ABC就去报了一下,感觉难度大概是cf的Div3到Div4之间吧,总共写了五个题,E题想复杂了快结束才交过。总的来说手速很重要。 题意:给一个字符串,要求把小写字母改成大写。 分析:

    2023年04月19日
    浏览(31)
  • 【蓝桥杯嵌入式】第十四届蓝桥杯嵌入式省赛[第一场]程序设计题以及详细题解

      今年的第一场比赛绝对np,官方将串口直接省掉了,将其替换成很多小功能,如:切换计时、频率均匀变化、锁机制等等,总的来说本届赛题的难度提升了不少。   本届试题需要用到的功能模块有 LCD 、 LED 、 按键 、 定时器输入捕获 、 定时器PWM输出 、 ADC获取 ,虽然这

    2023年04月17日
    浏览(83)
  • 第十二届蓝桥杯嵌入式省赛第一场真题(基于HAL库的巨简代码+超级详解)

    相关说明: 开发板:CT117E-M4(STM32G431RBT6) 开发环境: CubeMX+Keil5 涉及题目:第十二届蓝桥杯嵌入式省赛第一场真题 技巧:字符串比较 、字符串数组转移提取、for和return搭配使用、goto语句、利用%c和%s打印 CubeMX配置、主要函数代码及说明: 1.使能外部高速时钟: 2.配置时钟树:

    2023年04月11日
    浏览(50)
  • [蓝桥杯嵌入式]STM32G431——第十二届第一场省赛停车计费系统真题及程序设计代码详解

    最近,我报名了今年的蓝桥杯嵌入式比赛,为此刷了一下以往的真题。以下是我对十二届蓝桥杯省赛真题的一些思路和心得,还有一些具体代码的实现。 1、相关模块 第十二届比赛主要用到的模块包括:LED、KEY、LCD、TIM、USART 2、重难点分析 这道题主要目的是做一个停车管理

    2024年01月18日
    浏览(96)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包