返回列表 發帖

Rank: 7Rank: 7Rank: 7
1# 跳轉到 » 倒序看帖
打印
tT
方浩葦發表於 2025-3-15 02:28 | 只看該作者

[作業繳交] 2025/03/15

1. APCS 實作題：
10503 - 4

2. APCS 觀念題：10510 - 12、13
收藏 分享

Rank: 1
2#
黃暐鈞發表於 2025-3-15 14:01 | 只看該作者
本帖最後由 黃暐鈞 於 2025-3-22 15:10 編輯

APCS 實作題 10503 - 4
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n;//人數
  4. int root;//根節點
  5. int res;
  6. int finalMaxChildDis;
  7. struct Node
  8. {
  9.     int parent=-1,h=0;
  10.     int maxChildDis=0,max=-1,sec=-1;
  11.     vector<int> child;
  12. };
  13. int main()
  14. {
  15.         cin>>n;
  16.         int finalMaxChildDis=-1;
  17.         Node node[n];//node資料庫_共n人
  18.         for(int i=0;i<n-1;i++)//n個人有n-1個連結
  19.         {
  20.             int p;//父節點
  21.             int c;//子節點
  22.             cin>>p>>c;
  23.             node[c].parent=p;//c屬於b->p屬於node[c].parent
  24.             node[p].child.push_back(c);//一個父節點可以同時有很多子節點->用vector存
  25.         }//建立關係

  27.         for(int i=0;i<n;i++)//n次
  28.         {
  29.             if(node[i].parent==-1)//該節點沒有設定父節點->最高->根節點
  30.             {
  31.                 root=i;
  32.             }
  33.             if(node[i].child.size()==0)//確認該節點的子節點數量:為0->最底部
  34.             {
  35.                 int h=0;
  36.                 int parent=node[i].parent;//額外定義 不影響node資料
  37.                 while(parent!=-1)//有父節點
  38.                 {
  39.                     h++;
  40.                     if(h>node[parent].h)
  41.                     {
  42.                         node[parent].h=h;//找最深
  43.                     }
  44.                     else
  45.                     {
  46.                         break;
  47.                     }
  48.                     parent=node[parent].parent;//繼續往上找
  49.                 }
  50.             }
  51.         }
  52.         for(int i=0;i<n;i++)//n次
  53.         {
  54.             if(node[i].child.size()>=2)//子節點數量>=2
  55.             {
  56.                 for(int j=0;j<node[i].child.size();j++)//重複'子節點數量'次
  57.                 {
  58.                     int childH=node[node[i].child[j]].h;//取出子節點的深度
  59.                     if(childH>node[i].max)//找最深
  60.                     {
  61.                         node[i].sec=node[i].max;//找第二深(可能介於兩個最大之間)
  62.                         node[i].max=childH;
  63.                     }
  64.                     else if(childH>node[i].sec)//介於兩個最大之間->更新第二大
  65.                     {
  66.                         node[i].sec=childH;
  67.                     }
  68.                 }
  69.                 node[i].maxChildDis=node[i].max+node[i].sec+2;//計算總距離
  70.                 if(node[i].maxChildDis>finalMaxChildDis)//比較並更新
  71.                 {
  72.                     finalMaxChildDis=node[i].maxChildDis;
  73.                 }
  74.             }
  75.         }
  76.         if(node[root].h>finalMaxChildDis)//根節點距離最遠 不用找另外的子節點距離and+2
  77.         {
  78.             res=node[root].h;
  79.         }
  80.         else
  81.         {
  82.             res=finalMaxChildDis;
  83.         }
  84.     cout<<res;
  85. }

  87. /*
  88. 8
  89. 0 1
  90. 0 2
  91. 0 3
  92. 7 0
  93. 1 4
  94. 1 5
  95. 3 6
  96. */

  98. /*
  99. 4
  100. 0 1
  101. 0 2
  102. 2 3
  103. */
複製代碼
APCS 觀念題：10510 - 12、13
12.(A)
13.(C)

TOP

Rank: 1
3#
郭博鈞發表於 2025-3-15 15:31 | 只看該作者
本帖最後由 郭博鈞 於 2025-3-18 20:46 編輯

1. APCS 實作題：
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int root;
  4. int finalmaxchilddis,res;
  5. struct Node
  6. {
  7. int parent=-1,h=0;
  8. int maxchilddis=-1,max=-1,sec=-1;
  9. vector<int> child;
  10. };
  11. int main()
  12. {
  13.   int n;
  14.   while(cin>>n)
  15.   {
  16.       Node node[n];
  17.       finalmaxchilddis=-1;
  18.       for(int i=0;i<n-1;i++)
  19.       {
  20.           int p,c;
  21.           cin>>p>>c;
  22.           node[c].parent=p;
  23.           node[p].child.push_back(c);
  24.       }
  25.       for(int i=0;i<n;i++)
  26.       {
  27.           if(node[i].parent==-1)
  28.           {
  29.               root=i;
  30.           }
  31.           if(node[i].child.size()==0)
  32.           {
  33.               int h=0;
  34.               int parent=node[i].parent;
  35.               while(parent!=-1)
  36.               {
  37.                   h++;
  38.                   if(h>node[parent].h)
  39.                     node[parent].h=h;
  40.                   else
  41.                     break;
  42.                   parent=node[parent].parent;
  43.               }
  44.           }
  45.       }
  46.       for(int i=0;i<n;i++)
  47.       {
  48.           if(node[i].child.size()>=2)
  49.           {
  50.               for(int j=0;j<node[i].child.size();j++)
  51.               {
  52.                   int childh=node[node[i].child[j]].h;
  53.                   if(childh>node[i].max)
  54.                   {
  55.                       node[i].sec=node[i].max;
  56.                       node[i].max=childh;
  57.                   }
  58.                   else if(childh>node[i].sec)
  59.                       node[i].sec=childh;
  60.               }
  61.               node[i].maxchilddis=node[i].max+node[i].sec+2;
  62.               if(node[i].maxchilddis>finalmaxchilddis)
  63.               {
  64.                   finalmaxchilddis=node[i].maxchilddis;
  65.               }
  66.           }
  67.       }
  68.       if(node[root].h>finalmaxchilddis)
  69.         res=node[root].h;
  70.       else
  71.         res=finalmaxchilddis;
  72.       cout<<res<<endl;
  73.   }
  74.     return 0;
  75. }
複製代碼
2. APCS 觀念題：10510 - 12、13
B
A

TOP

Rank: 1
4#
許浩浩發表於 2025-3-21 20:42 | 只看該作者
本帖最後由 許浩浩 於 2025-3-22 07:16 編輯

1. APCS 實作題：
10503 - 4
  1. #include<bits/stdc++.h>
  2. using namespace std;

  4. int n,root;
  5. int res,finalMaxChildDis;

  7. struct Node
  8. {
  9.     int parent=-1,h=0;
  10.     int maxChildDis=-1,max=-1,sec=-1;
  11.     vector<int> child;
  12. };

  14. int main()
  15. {
  16.     cin.tie(0);
  17.     cin.sync_with_stdio(0);

  19.     while(cin>>n)
  20.     {
  21.         finalMaxChildDis=-1;
  22.         Node node[n];

  24.         for(int i=0;i<n-1;i++)
  25.         {
  26.             int p,c;
  27.             cin>>p>>c;
  28.             node[c].parent=p;
  29.             node[p].child.push_back(c);
  30.         }

  32.         for(int i=0;i<n;i++)
  33.         {
  34.             if(node[i].parent==1)
  35.                 root=i;

  37.             if(node[i].child.size()==0)
  38.             {
  39.                 int h=0;
  40.                 int parent=node[i].parent;

  42.                 while(parent!=-1)
  43.                 {
  44.                     h++;

  46.                     if(h>node[parent].h)
  47.                         node[parent].h=h;
  48.                     else
  49.                         break;
  50.                     parent=node[parent].parent;
  51.                 }
  52.             }
  53.         }

  55.         for(int i=0;i<n;i++)
  56.         {
  57.             if(node[i].child.size()>=2)
  58.             {
  59.                 for(int j=0;j<node[i].child.size();j++)
  60.                 {
  61.                     int childH=node[node[i].child[j]].h;
  62.                     if(childH>node[i].max)
  63.                     {
  64.                         node[i].sec=node[i].max;
  65.                         node[i].max=childH;
  66.                     }
  67.                     else if(childH>node[i].sec)
  68.                         node[i].sec=childH;
  69.                 }
  70.                 node[i].maxChildDis=node[i].max+node[i].sec+2;

  72.                 if(node[i].maxChildDis>finalMaxChildDis)
  73.                     finalMaxChildDis=node[i].maxChildDis;
  74.             }
  75.         }
  76.         if(node[root].h>finalMaxChildDis)
  77.             res=node[root].h;
  78.         else
  79.             res=finalMaxChildDis;

  81.         cout<<res<<endl;
  82.     }

  84.     return 0;
  85. }
複製代碼
2. APCS 觀念題：10510 - 12、13
  1. (B) (B)
複製代碼

TOP

Rank: 1
5#
江家同發表於 2025-3-21 23:21 | 只看該作者
1. APCS 實作題：
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,root;
  4. int res,finalMaxChildDis;
  5. struct Node
  6. {
  7.     int parent=-1,h=0;
  8.     int maxChildDis=-1,max=-1,sec=-1;
  9.     vector<int>child;
  10. };
  11. int main()
  12. {
  13.     cin.tie(0);
  14.     cin.sync_with_stdio(0);
  15.     while(cin>>n)
  16.     {
  17.         finalMaxChildDis=-1;
  18.         Node node[n];
  19.         for(int i=0;i<n-1;i++)
  20.         {
  21.             int p,c;
  22.             cin>>p>>c;
  23.             node[c].parent=p;
  24.             node[p].child.push_back(c);
  25.         }
  26.         for(int i=0;i<n;i++)
  27.         {
  28.             if(node[i].parent==-1)
  29.                 root=i;
  30.             if(node[i].child.size()==0)
  31.             {
  32.                 int h=0;
  33.                 int parent=node[i].parent;
  34.                 while(parent!=-1)
  35.                 {
  36.                     h++;
  37.                     if(h>node[parent].h)
  38.                         node[parent].h=h;
  39.                     else
  40.                         break;
  41.                     parent=node[parent].parent;
  42.                 }
  43.             }
  44.         }
  45.         for(int i=0;i<n;i++)
  46.         {
  47.             if(node[i].child.size()>=2)
  48.             {
  49.                 for(int j=0;j<node[i].child.size();j++)
  50.                 {
  51.                     int childH=node[node[i].child[j]].h;
  52.                     if(childH>node[i].max)
  53.                     {
  54.                         node[i].sec=node[i].max;
  55.                         node[i].max=childH;
  56.                     }
  57.                     else if(childH>node[i].sec)
  58.                         node[i].sec=childH;
  59.                 }
  60.                 node[i].maxChildDis=node[i].max+node[i].sec+2;
  61.                 if(node[i].maxChildDis>finalMaxChildDis)
  62.                     finalMaxChildDis=node[i].maxChildDis;
  63.             }
  64.         }
  65.         if(node[root].h>finalMaxChildDis)
  66.             res=node[root].h;
  67.         else
  68.             res=finalMaxChildDis;
  69.         cout<<res<<endl;
  70.     }
  71.     return 0;
  72. }
複製代碼
2. APCS 觀念題：
10510 - 12
(B)
10510 - 13
(B)

TOP

返回列表