【FOJ2207 11月月赛C】【DFS栈性质应用 离线处理】以撒的结合 从x到y路径上的第k个点 询问众多

2024-01-15 23:08
文章标签 路径 应用 处理 结合 dfs 离线 性质 众多 询问 个点 foj2207

本文主要是介绍【FOJ2207 11月月赛C】【DFS栈性质应用 离线处理】以撒的结合 从x到y路径上的第k个点 询问众多，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 Problem 2207 以撒的结合

Accept: 30    Submit: 98
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

小茗同学最近在认真地准备比赛，所以经常玩以撒的结合。

《以撒的结合》是一款由Edmund McMillen，Florian Himsl 开发，并由Edmund McMillen最早于2011年09月29日发行的一款2D平面角色扮演、动作冒险类的独立游戏。游戏的角色将在有着能够提升能力的道具与特殊技能的半RPG世界中闯荡。

——来自百度百科

小茗同学在打BOSS前，费掉了很多HP。在地图的一些房间里有补充HP的红心，然而小茗同学受到了看不见地图的诅咒。凭借不知道哪里来的记忆，小茗同学记得某个有红心的房间在房间A与房间B的路上的第K个房间里。为了简化问题，我们把地图看成一棵树。小茗同学想知道A到B的第K个房间号为多少，由于小茗同学很累，所以现在这个任务交给你了。

 Input

第一行是一个整数T(T<=10)，表示有T组测试数据。

每组数据的第一行为两个整数n m(0<n<=1000,0<m<=n*n),分别表示房间个数和询问次数。

接下来n-1行，每行两个整数u v(0<u、v<=n，且u≠v),表示地图上房间u和房间v有一条路径。

最后是m行，每行三个整数u v k，表示询问房间u到房间v的路径上的第k个房间。

输入数据保证合法，即k不超过u、v的最短距离。

 Output

对于每组数据，首先第一行先输出“Case #x:“ ，其中x是从1开始，表示数据组号，接下来m行，每行输出相应的房间号。

 Sample Input

16 31 22 42 51 33 64 6 41 6 24 5 3

 Sample Output

Case #1:335

 Source

FOJ有奖月赛-2015年11月



【FOJ2207 11月月赛C】【DFS栈性质应用 离线处理】以撒的结合 从x到y路径上的第k个点 询问众多 DFS AC

#include<stdio.h> 
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=1010,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int n,m,x,y,k;
int st,top,tim;
vector<int>a[N];
int first[N][N];int id;
struct query
{int k,o,nxt;
}q[N*N];
int e[N],s[N],ans[N*N];
void dfs(int x)
{e[x]=tim;s[++top]=x;for(int z=first[st][x];z;z=q[z].nxt){int k=q[z].k;int o=q[z].o;ans[o]=s[k];}first[st][x]=0;for(int i=a[x].size()-1;~i;--i){int y=a[x][i];if(e[y]!=tim)dfs(y);}--top;
}
int main()
{scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d%d",&n,&m);if(n>1000||m>n*n)return 0;for(int i=1;i<=n;i++)a[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}id=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&k);++id;q[id].k=k;q[id].o=i;q[id].nxt=first[x][y];first[x][y]=id;}for(st=1;st<=n;st++){++tim;dfs(st);}printf("Case #%d:\n",casei);for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}
/*
【trick&&吐槽】
1，不看数据规模就做真的是好蠢好蠢，数据规模也是对做法的提示。
2，dfs上有很多精妙的性质和应用。
3，lca问题我竟然忘记了要把双向边都放进去+_+，然而竟然能过样例，天哪【题意】
给你一棵树，树上有n（1e3）个点。
我们有m个询问，m最大为n*n。
对于每个询问，给你（x，y，k），问你从x到y上的第k个房间的是多少。【类型】
LCA or 树链剖分？NO！正解是栈性质dfs！【分析】
这题我一看到是树结构，立马想到树链剖分或者是LCA这样O(mlogn)的做法。
然而m实在是太大了，这个做法只会造成TLE >_<
正解是怎么做呢？DFS！
我们用vector存下所有询问（x，y，k）
[哇哇哇，vector太大也会导致TLE！换成链表模式就AC了>_<]
然后从每个点开始dfs，用栈存下所有点。
如果遇到（x，y，k）的询问，我们就直接记录答案为目前从x开始dfs的栈中第k个点。
这样就可以AC喽~【时间复杂度&&优化】
O(n^2)*/

【FOJ2207 11月月赛C】【DFS栈性质应用 离线处理】以撒的结合 从x到y路径上的第k个点 询问众多 LCA TLE

#include<stdio.h> 
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=1010,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int n,m,x,y,k;
vector<int>a[N];
int d[N];
int f[N][12];
int b[12];
void dfs(int x)
{for(int i=a[x].size()-1;~i;--i){int y=a[x][i];if(y==f[x][0])continue;f[y][0]=x;d[y]=d[x]+1;dfs(y);}
}
void LCAinit()
{for(int j=1;b[j]<n;j++){for(int i=1;i<=n;i++)if(~f[i][j-1]){f[i][j]=f[f[i][j-1]][j-1];}}
}
int DX,DY;
int LCA(int x,int y)
{int i,j;if(d[x]<d[y])swap(x,y);for(i=0;b[i]<=d[x];i++);i--;for(j=i;d[x]>d[y];j--)if(d[x]-b[j]>=d[y])x=f[x][j];if(x==y)return x;for(j=i;f[x][0]!=f[y][0];j--)if(f[x][j]!=f[y][j]){x=f[x][j];y=f[y][j];}return f[x][0];
}
int find(int x,int dis)
{int i;for(i=0;b[i]<=dis;i++);i--;while(dis){if(dis>=b[i]){x=f[x][i];dis-=b[i];}}return x;
}
int main()
{for(int i=0;i<=10;i++)b[i]=1<<i;scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)a[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}MS(f,-1);f[1][0]=0;d[1]=0;dfs(1);LCAinit();printf("Case #%d:\n",casei);while(m--){scanf("%d%d%d",&x,&y,&k);k--;int lca=LCA(x,y);int dx=d[x]-d[lca];int dy=d[y]-d[lca];int ans;if(dx>=k)ans=find(x,k);else{k-=dx;ans=find(y,dy-k);}printf("%d\n",ans);}}return 0;
}
/*
【trick&&吐槽】
1，不看数据规模就做真的是好蠢好蠢，数据规模也是对做法的提示。
2，dfs上有很多精妙的性质和应用。
3，lca问题我竟然忘记了要把双向边都放进去+_+，然而竟然能过样例，天哪【题意】
给你一棵树，树上有n（1e3）个点。
我们有m个询问，m最大为n*n。
对于每个询问，给你（x，y，k），问你从x到y上的第k个房间的是多少。【类型】
LCA or 树链剖分？NO！正解是栈性质dfs！【分析】
这题我一看到是树结构，立马想到树链剖分或者是LCA这样O(mlogn)的做法。
然而m实在是太大了，这个做法只会造成TLE >_<
正解是怎么做呢？DFS！
我们用vector存下所有询问（x，y，k）
[哇哇哇，vector太大也会导致TLE！换成链表模式就AC了>_<]
然后从每个点开始dfs，用栈存下所有点。
如果遇到（x，y，k）的询问，我们就直接记录答案为目前从x开始dfs的栈中第k个点。
这样就可以AC喽~【时间复杂度&&优化】
O(n^2)*/


这篇关于【FOJ2207 11月月赛C】【DFS栈性质应用 离线处理】以撒的结合 从x到y路径上的第k个点 询问众多的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/610501。

相关文章

电脑提示xlstat4.dll丢失怎么修复? xlstat4.dll文件丢失处理办法

电脑提示xlstat4.dll丢失怎么修复? xlstat4.dll文件丢失处理办法

《电脑提示xlstat4.dll丢失怎么修复?xlstat4.dll文件丢失处理办法》长时间使用电脑，大家多少都会遇到类似dll文件丢失的情况，不过，解决这一问题其实并不复杂，下面我们就来看看xls... 在Windows操作系统中，xlstat4.dll是一个重要的动态链接库文件，通常用于支持各种应用程序
阅读更多...
SQL Server数据库死锁处理超详细攻略

SQL Server数据库死锁处理超详细攻略

《SQLServer数据库死锁处理超详细攻略》SQLServer作为主流数据库管理系统,在高并发场景下可能面临死锁问题,影响系统性能和稳定性,这篇文章主要给大家介绍了关于SQLServer数据库死... 目录一、引言二、查询 Sqlserver 中造成死锁的 SPID三、用内置函数查询执行信息1. sp_w
阅读更多...
Java对异常的认识与异常的处理小结

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。（1）简单定义-什么是
阅读更多...
SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一：基础配置（直接关闭目标路径日志）方案二：结合 Spring Profile 按环境屏蔽关
阅读更多...
Golang 日志处理和正则处理的操作方法

Golang 日志处理和正则处理的操作方法

《Golang日志处理和正则处理的操作方法》：本文主要介绍Golang日志处理和正则处理的操作方法,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考... 目录1、logx日志处理1.1、logx简介1.2、日志初始化与配置1.3、常用方法1.4、配合defer
阅读更多...
springboot加载不到nacos配置中心的配置问题处理

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》：本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos
阅读更多...
Python使用Tkinter打造一个完整的桌面应用

Python使用Tkinter打造一个完整的桌面应用

《Python使用Tkinter打造一个完整的桌面应用》在Python生态中,Tkinter就像一把瑞士军刀,它没有花哨的特效,却能快速搭建出实用的图形界面,作为Python自带的标准库,无需安装即可... 目录一、界面搭建：像搭积木一样组合控件二、菜单系统：给应用装上“控制中枢”三、事件驱动：让界面“活”
阅读更多...
VSCode设置python SDK路径的实现步骤

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换（推荐方法）二、通过 settings.json 配置（项目级/全局）三、
阅读更多...
使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键
阅读更多...
如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

如何确定哪些软件是Mac系统自带的? Mac系统内置应用查看技巧

《如何确定哪些软件是Mac系统自带的?Mac系统内置应用查看技巧》如何确定哪些软件是Mac系统自带的？mac系统中有很多自带的应用，想要看看哪些是系统自带，该怎么查看呢？下面我们就来看看Mac系统内... 在MAC电脑上，可以使用以下方法来确定哪些软件是系统自带的：1.应用程序文件夹打开应用程序文件夹
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2