2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game

这篇具有很好参考价值的文章主要介绍了2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game

题目大意

有一棵有 n n n个节点的树,小 S S S和小 R R R在树上各有一条链。小 S S S的链的起点为 S a S_a Sa,终点为 T a T_a Ta;小 R R R的链起点为 S b S_b Sb,终点为 T b T_b Tb

S S S和小 R R R在各自的链来回移动(就是从起点到终点,再回到起点,进行多次来回),一个单位时间移动一条边。求出两人最早相遇的位置(这个位置必须是一个点,而不是一条边),若不可能相遇,输出 − 1 -1 1

t t t组数据。

1 ≤ t ≤ 500 , 2 ≤ n , m ≤ 3 × 1 0 3 1\leq t\leq 500,2\leq n,m\leq 3\times 10^3 1t500,2n,m3×103

数据保证 n n n值超过 400 400 400的数据组数不超过 20 20 20

数据保证 m m m值超过 400 400 400的数据组数不超过 20 20 20


题解

因为 n n n比较小,所以我们可以枚举两条链上的每一个点。

对于同时在两条链上的点 x x x,我们可以得出从小 S S S到达 x x x的时间为 2 k 1 ⋅ d i s ( S a , T a ) + d i s ( S a , x ) 2k_1\cdot dis(S_a,T_a)+dis(S_a,x) 2k1dis(Sa,Ta)+dis(Sa,x) 2 k 2 ⋅ d i s ( S a , T a ) + d i s ( T a , x ) 2k_2\cdot dis(S_a,T_a)+dis(T_a,x) 2k2dis(Sa,Ta)+dis(Ta,x),其中 k 1 , k 2 k_1,k_2 k1,k2都为非负整数。

同理,小 R R R到达 x x x的时间为 2 k 3 ⋅ d i s ( S a , T a ) + d i s ( S a , x ) 2k_3\cdot dis(S_a,T_a)+dis(S_a,x) 2k3dis(Sa,Ta)+dis(Sa,x) 2 k 4 ⋅ d i s ( S a , T a ) + d i s ( T a , x ) 2k_4\cdot dis(S_a,T_a)+dis(T_a,x) 2k4dis(Sa,Ta)+dis(Ta,x),其中 k 3 , k 4 k_3,k_4 k3,k4都为非负整数。

两两联立成形为 a x + b x = c ax+bx=c ax+bx=c的二元一次方程,然后用扩展欧几里得算法求出最小非负整数解即可。

时间复杂度为 O ( n m log ⁡ n ) O(nm\log n) O(nmlogn)。因为 n , m n,m n,m较大的数据组数比较少,而且跑不满,时限有 5 s 5s 5s,所以是可以过的。文章来源地址https://www.toymoban.com/news/detail-598365.html

code

#include<bits/stdc++.h>
using namespace std;
int tq,n,m,s1,s2,t1,t2,dt,fa[5005],dep[5005],dfn[5005],low[5005];
int ans,bz,ls,lt,tot=0,d[10005],l[10005],r[10005],z[5005],w[5005][2];
void add(int xx,int yy){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u,int f){
	fa[u]=f;
	dep[u]=dep[f]+1;
	dfn[u]=++dt;
	for(int i=r[u];i;i=l[i]){
		if(d[i]==f) continue;
		dfs(d[i],u);
	}
	low[u]=dt;
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y]) x=fa[x];
	while(x!=y){
		x=fa[x];y=fa[y];
	}
	return x;
}
bool in(int x,int y){
	return dfn[y]<=dfn[x]&&dfn[x]<=low[y];
}
void exgcd(int &x,int &y,int &d,int a,int b){
	if(b==0){
		x=1;y=0;d=a;
		return;
	}
	exgcd(x,y,d,b,a%b);
	int t=x;x=y;y=t-a/b*y;
}
void dd(int now,int w1,int w2){
	int a=2*ls,b=-2*lt,c=w2-w1,x,y,d,vk;
	c=(c%(2*lt)+2*lt)%(2*lt);
	exgcd(x,y,d,a,b);
	if(c%d) return;
	x*=c/d;y*=c/d;
	int p=a/d,q=b/d;
	if(x<0){
		vk=ceil((-1.0*x)/q);
		x+=vk*q;y-=vk*p;
	}
	else if(x>=0){
		vk=x/q;
		x-=vk*q;y+=vk*p;
	}
	if(a*x+w1<ans){
		ans=a*x+w1;
		bz=now;
	}
}
int main()
{
	scanf("%d",&tq);
	while(tq--){
		scanf("%d%d",&n,&m);
		for(int i=1,x,y;i<n;i++){
			scanf("%d%d",&x,&y);
			add(x,y);add(y,x);
		}
		dfs(1,0);
		for(int o=1;o<=m;o++){
			scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
			int vs=lca(s1,t1),vt=lca(s2,t2);
			if(dep[vs]>dep[vt]){
				swap(s1,s2);
				swap(t1,t2);
				swap(vs,vt);
			}
			if(!in(s1,vt)&&!in(t1,vt)){
				printf("-1\n");
				continue;
			}
			ans=1e9;bz=-1;
			ls=dep[s1]+dep[t1]-2*dep[vs],lt=dep[s2]+dep[t2]-2*dep[vt];
			for(int p=s1;;p=fa[p]){
				w[p][0]=dep[s1]-dep[p];
				w[p][1]=2*ls-(dep[s1]-dep[p]);
				z[p]=o;
				if(p==vs) break;
			}
			for(int p=t1;p!=vs;p=fa[p]){
				w[p][0]=ls-(dep[t1]-dep[p]);
				w[p][1]=ls+(dep[t1]-dep[p]);
				z[p]=o;
			}
			for(int p=s2;;p=fa[p]){
				if(z[p]==o){
					int k1=dep[s2]-dep[p],k2=2*lt-(dep[s2]-dep[p]);
					dd(p,w[p][0],k1);dd(p,w[p][0],k2);
					dd(p,w[p][1],k1);dd(p,w[p][1],k2);
				}
				if(p==vt) break;
			}
			for(int p=t2;p!=vt;p=fa[p]){
				if(z[p]==o){
					int k1=lt-(dep[t2]-dep[p]),k2=lt+(dep[t2]-dep[p]);
					dd(p,w[p][0],k1);dd(p,w[p][0],k2);
					dd(p,w[p][1],k1);dd(p,w[p][1],k2);
				}
			}
			printf("%d\n",bz);
		}
		tot=dt=0;
		for(int i=1;i<=n;i++){
			r[i]=fa[i]=dep[i]=z[i]=0;
			dfn[i]=low[i]=0;
		}
	}
	return 0;
}

到了这里,关于2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • (杭电多校)2023“钉耙编程”中国大学生算法设计超级联赛(4)

    1003 Simple Set Problem 双指针的思想,双端队列 先从小到大排个序 一个一个放到双端队列里,一边放一边维护集合个数为k个 利用滑动窗口,当滑动窗口中集合个数为k时,只需算出滑动窗口最后一个数减去第一个数,然后每次取min就行了 AC代码:  1006 PSO  两两组合 期望=所有组合的边

    2024年02月15日
    浏览(48)
  • 2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game

    2023“钉耙编程”中国大学生算法设计超级联赛(1)Hide-And-Seek Game 题目大意 有一棵有 n n n 个节点的树,小 S S S 和小 R R R 在树上各有一条链。小 S S S 的链的起点为 S a S_a S a ​ ,终点为 T a T_a T a ​ ;小 R R R 的链起点为 S b S_b S b ​ ,终点为 T b T_b T b ​ 。 小 S S S 和小 R R

    2024年02月16日
    浏览(46)
  • 2023年度第四届全国大学生算法设计与编程挑战赛(春季赛)

     A 题目描述        有一个长为 n (1le n le 1000)n (1≤n≤1000) 的序列,序列上的元素两两不同。你需要用最少的操作步数翻转这个序列。        每次操作你需要给出三个数 i,j,k(1le ile j k le n)i,j,k(1≤i≤jk≤n),交换序列中下标属于 [i,j][i,j] 的元素与下标属于 [j+1,k][j+

    2024年02月08日
    浏览(128)
  • 2023年天府杯全国大学生数学建模竞赛B题中国环境问题的治理解题全过程

       问题背景:    随着经济的快速发展和人口的持续增长,中国的环境问题已经成为了一个急需解决的重要问题。这些环境问题不仅对人们的健康和生活质量产生了巨大的影响,还对生态系统和生态平衡造成了极大的破坏。近年来,中国政府积极推动环保事业的发展,通

    2024年02月08日
    浏览(47)
  • 2023年四川大学生程序设计竞赛-K.倒转乾坤

    Cuber QQ 现在手上有两个圆环,其中小圆环的直径是 d,大圆环的直径是 2d 。他将小圆环放在大圆环内, 并让小圆环紧贴大圆环内壁进行无滑动的滚动。   Cuber QQ 总是喜欢动态的美,他在小圆环上等间隔地标记了 n 个点,他想知道在小圆环贴着大圆环运动一周后,他所

    2024年02月16日
    浏览(59)
  • 【电子设计大赛】2023 年全国大学生电子设计竞赛 仪器和主要元器件清单

    1. 仪器设备清单 直流稳压电源(具有恒流/恒压模式自动切换功能,0~30V/3A,双路) 数字示波器(100MHz, 双通道) 函数发生器(50 MHz,双通道) 射频信号源(500MHz,-100dBm~0dBm,具有射频输出开关功能) 矢量网络分析仪(1GHz) 频谱分析仪(1GHz) 频率计(500MHz) 功率分析仪

    2024年02月15日
    浏览(91)
  • 2023 年第五届河南省 CCPC 大学生程序设计竞赛

    Problem A. 小水獭游河南 ∣ a ∣ ≤ ∣ Σ ∣ = 26 ,暴力枚举 a 判断 b 是否为是回文串即可,时间复杂度 O ( ∣ Σ ∣ ∣ s ∣ ) 。 |a| ≤ |Σ| = 26,暴力枚举 a 判断 b 是否为是回文串即可,时间复杂度 O(|Σ||s|)。 ∣ a ∣ ≤ ∣Σ∣ = 26 ,暴力枚举 a 判断 b 是否为是回文串即可,时间复

    2024年02月03日
    浏览(84)
  • 2023年第十五届“中国电机工程学会杯”全国大学生电工数学建模竞赛题目 A题:电采暖负荷参与电力系统功率调节的技术经济分析

    建设以新能源为主体的新型电力系统是应对全球气候变化挑战的重要举措。高比例新能源接入导致电力系统调节能力稀缺,亟需开发新的调节资源,如火电深度调峰、建设抽水蓄能电站、配置储能和挖掘负荷中的调节能力等。现代电力负荷中含有较大比重的温控型负荷(如空

    2024年02月06日
    浏览(47)
  • 【毕业设计】基于springboot的大学生综合素质测评系统——2023最新推荐

    【毕业设计】基于springboot大学生综测管理系统 🥇 个人主页 :@MIKE笔记 🥈 文章专栏 :毕业设计源码合集 ⛄ 联系博主: wx: mikenote 项目名 文章地址 💹下载 基于springboot的 大学生综合素质测评管理系统 http://t.csdn.cn/smVjL v1.0 // v2.0 基于springboot + vue 微信小程序文创平台商城

    2024年02月06日
    浏览(73)
  • 第五届湖北省大学生程序设计竞赛(HBCPC 2023)vp赛后补题

    思路: 数位dp,如果我们暴力的计算的状态的话,显然就是记录每个数字出现几次。但是显然这样难以发挥数位dp的记忆化功效,因为只有出现次数相同,你是什么数字,实际是无所谓的。所以我们尝试记录每个出现次数有多少个数字 尝试打表发现,结果只有1477种 所以,对

    2024年02月07日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包