H:::::::::::::::::::小朋友崇拜圈（DFS）
题目描述
班里 NN 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为 1,2,3,⋯N。
输入描述
输入第一行，一个整数 N（3<N<105）。
接下来一行 N 个整数，由空格分开。
输出描述
要求输出一个整数，表示满足条件的最大圈的人数。
输入输出样例
示例
输入
9 3 4 2 5 3 8 4 6 9
输出
4
样例解释
如下图所示，崇拜关系用箭头表示，红色表示不在圈中。
显然，最大圈是[2 4 5 3] 构成的圈。
运行限制
最大运行时间：1s
最大运行内存: 256M
#include <iostream> using namespace std; int a[300005]; bool vis[300005]; int n; bool p; int ans; void dfs(int x,int y,int an){ if(x==y && an>1){ ans=max(ans,an); return; } if(!vis[x]){ vis[x]=1; dfs(a[x],y,an+1); vis[x]=0; } } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ p=false; dfs(i,i,0); } cout<<ans; return 0; }
I:::::::::::::::::::出差（Dijkstra）
问题描述
A 国有 N 个城市, 编号为 1…N 。小明是编号为 1 的城市中一家公司的员 工, 今天突然接到了上级通知需要去编号为 N 的城市出差。
由于疫情原因, 很多直达的交通方式暂时关闭, 小明无法乘坐飞机直接从 城市 1 到达城市 N, 需要通过其他城市进行陆路交通中转。小明通过交通信息 网, 查询到了M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的 时间。
同样由于疫情原因, 小明到达一个城市后需要隔离观察一段时间才能离开 该城市前往其他城市。通过网络, 小明也查询到了各个城市的隔离信息。(由于 小明之前在城市 1 , 因此可以直接离开城市 1 , 不需要隔离）
由于上级要求, 小明希望能够尽快赶到城市 N, 因此他求助于你, 希望你 能帮他规划一条路线, 能够在最短时间内到达城市 N 。
输入格式
第 1 行: 两个正整数 N,M,N 表示 A 国的城市数量, M 表示末关闭的路 线数量
第 2 行: N 个正整数, 第 i 个整数 Ci 表示到达编号为 i 的城市后需要隔离 的时间
第 3…M+2 行: 每行 3 个正整数,u,v,c, 表示有一条城市 u 到城市 v 的 双向路线仍然开通着, 通过该路线的时间为 c
输出格式
第 1 行: 1 个正整数, 表示小明从城市 1 出发到达城市 N 的最短时间（到 达城市 N, 不需要计算城市 N 的隔离时间）
样例输入
4 4 5 7 3 4 1 2 4 1 3 5 2 4 3 3 4 5
样例输出
13
样例说明
评测用例规模与约定
运行限制
最大运行时间：1s
最大运行内存: 512M
#include <iostream> #include <cstring> #include <cmath> using namespace std; int n,m; //n个城市，m条路线 int geli[10005]; //到每个城市的隔离时间 int luxian[10005][10005]; int juli[10005]; //到一点的最短距离 bool vis[10005]; int dj(){ memset(juli,0x3f3f3f3f,sizeof(juli)); juli[1]=0; //距离起点为0 geli[1]=0; //出自己城市不隔离 geli[n]=0; //到达终点不需要隔离 for(int i=1;i<=n;i++){ int s=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&((s==-1)||(juli[j]<juli[s]))){ s=j; } } vis[s]=1; for(int j=1;j<=n;j++){ juli[j]=min(juli[j],juli[s]+luxian[s][j]+geli[s]); } } return juli[n]; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>geli[i]; } memset(luxian,0x3f3f3f3f,sizeof(luxian)); //无穷大 for(int i=1;i<=n;i++){ luxian[i][i]=0; //自己到自己为0 } for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c; luxian[a][b]=luxian[b][a]=min(c,luxian[a][b]); } int ans=dj(); cout<<ans; return 0; }
J:::::::::::::::::::百亿富翁（单调栈）
题目描述
这天小明买彩票中了百亿奖金，兴奋的他决定买下蓝桥公司旁的一排连续的楼房。
已知这排楼房一共有 N 栋，编号分别为 1∼N，第 ii 栋的高度为 hi。
好奇的小明想知道对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个（若不存在则输出 −1）。但由于楼房数量太多，小明无法用肉眼直接得到答案，于是他花了 1 个亿来请你帮他解决问题，你不会拒绝的对吧？
输入描述
第 1 行输入一个整数 N，表示楼房的数量。
第 2 行输入 N 个整数（相邻整数用空格隔开），分别为h1,h2,...,hN，表示楼房的高度。
1≤N≤7×105，1≤hi≤109。
输出描述
输出共两行。
第一行输出 N 个整数，表示每栋楼左边第一栋比自己高的楼的编号。
第二行输出 N 个整数，表示每栋楼右边第一栋比自己高的楼的编号。
输入输出样例
示例 1
输入
5 3 1 2 5 4
输出
-1 1 1 -1 4 4 3 4 -1 -1
#include <iostream> #include <stack> using namespace std; int n; long long a[700005]; stack<int> st; int l[700005]; int r[700005]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ while(st.size() && a[st.top()]<=a[i]) st.pop(); if(st.size()){ l[i]=st.top(); }else{ l[i]=-1; } st.push(i); } while(!st.empty()){ st.pop(); } for(int i=n;i>=1;i--){ while(st.size() && a[st.top()]<=a[i]) st.pop(); if(st.size()){ r[i]=st.top(); }else{ r[i]=-1; } st.push(i); } for(int i=1;i<=n;i++){ cout<<l[i]<<' '; } cout<<endl; for(int i=1;i<=n;i++){ cout<<r[i]<<' '; } return 0; }
