7-9.小字辈
思路：建立一个类，并且类中存有其父节点，其地位，其儿子节点（因为儿子节点有很多，所以要用vector进行存储），通过-1这个祖先节点进行查找。首先找到-1这个祖先节点，并且读入其他位置的父节点，与此同时其父节点中儿子节点也有此节点————>然后进行递归查找，以类为类型建立队列，祖先节点进队列，然后for循环给其儿子节点的地位+1，并且让其儿子节点进行入队列，自己出队列，直到队列空————>找到地位的最大值，输出结果
代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 #include<cstring> 6 #include<set> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 const int maxx=1e5+10; 11 struct num{ 12 int father; 13 int rankk; 14 vector<int> son; 15 }a[maxx]; 16 int dfs(int x){ 17 queue<num> s; 18 s.push(a[x]); 19 num Q; 20 while(!s.empty()){ 21 Q=s.front(); 22 for(int i=0;i<Q.son.size();i++){ 23 a[Q.son[i]].rankk=Q.rankk+1; 24 s.push(a[Q.son[i]]); 25 } 26 s.pop(); 27 } 28 return Q.rankk; 29 } 30 int main(){ 31 int t; 32 scanf("%d",&t); 33 int temp; 34 int nus; 35 for(int i=1;i<=t;i++){ 36 scanf("%d",&a[i].father); 37 if(a[i].father==-1){ 38 temp=i; 39 a[i].rankk=1; 40 }else{ 41 a[a[i].father].son.push_back(i); 42 } 43 } 44 int mm=dfs(temp); 45 printf("%d\n",dfs(temp)); 46 int flag=0; 47 48 for(int i=1;i<=t;i++){ 49 if(a[i].rankk==mm&&flag==0){ 50 printf("%d",i); 51 flag=1; 52 }else if(a[i].rankk==mm){ 53 printf(" %d",i); 54 } 55 } 56 }
7-12 深入虎穴
思路：首先题目说不存在两条路通向同一扇门，说明本题的图是一棵树。入口唯一，所以入度为 0 的那个点既是树的根节点。然后求一下树中每一个节点的深度，深度最大的那个点即为距离入口最远的那扇门。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int maxn = 100010; 6 int head[maxn], Next[maxn], ver[maxn]; 7 int vis[maxn], d[maxn], degree[maxn]; 8 int n, k, tot; 9 int ans, maxx; 10 void add(int x, int y){//数组模拟邻接表 11 ver[++tot] = y, Next[tot] = head[x]; 12 head[x] = tot; 13 } 14 void dfs(int x){ 15 vis[x] = 1; 16 for(int i = head[x]; i; i = Next[i]){ 17 int y = ver[i]; 18 if(!vis[y]){ 19 d[y] = d[x] + 1; 20 dfs(y); 21 } 22 } 23 } 24 int main(){ 25 cin >> n; 26 for(int i = 1; i <= n; i++){ 27 cin >> k; 28 int x; 29 for(int j = 0; j < k; j++){ 30 cin >> x; 31 degree[x]++; 32 add(i, x);// i -> x 的有向边 33 } 34 } 35 int rt = 1; 36 for(int i = 1; i <= n; i++){ 37 if(!degree[i]){//入度为0的那个点为入口，即根节点 38 rt = i; 39 break; 40 } 41 } 42 d[rt] = 1;//初始化根节点的深度为1 43 dfs(rt); 44 for(int i = 1; i <= n; i++){//寻找深度最大的那个点 45 if(d[i] > maxx) { 46 maxx = d[i]; 47 ans = i; 48 } 49 } 50 cout << ans << endl; 51 return 0; 52 }
思路：就是从1-1.0/n遍历一遍找到最小的就可以
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<queue> 5 #include<map> 6 #include<cmath> 7 #include<cstring> 8 9 using namespace std; 10 const int N = 500007, M = 5000007; 11 const ll INF = 1e14; 12 13 int n, m; 14 ll a[N]; 15 16 int main(){ 17 scanf("%d", &n); 18 for(int i = 1; i <= n; ++ i){ 19 scanf("%lld", &a[i]); 20 } 21 ll ans = INF ; 22 int t = pow(INF, 1.0 / n); 23 sort(a + 1, a + 1 + n); 24 for(int c = 1; c <= t; ++ c){ 25 ll sum = 0, tmp = 1;//c^0 26 for(int i = 1; i <= n; ++ i){ 27 sum += abs(a[i] - tmp); 28 tmp *= c; 29 } 30 ans = min(ans, sum); 31 } 32 printf("%lld\n", ans); 33 return 0; 34 }
原文：https://www.cnblogs.com/bonel/p/13875251.html
