標題: [作業繳交] 2025/03/15 [打印本頁]

---

作者: 方浩葦    時間: 2025-3-15 02:28     標題: [作業繳交] 2025/03/15

1. APCS 實作題：
10503 - 4

2. APCS 觀念題：10510 - 12、13

---

作者: 黃暐鈞    時間: 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.         }//建立關係
    
26. 
    
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. }
    
86. 
    
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. */
    
97. 
    
98. /*
    
99. 4
    
100. 0 1
     
101. 0 2
     
102. 2 3
     
103. */

複製代碼

APCS 觀念題：10510 - 12、13
12.(A)
13.(C)

---

作者: 郭博鈞    時間: 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

---

作者: 許浩浩    時間: 2025-3-21 20:42

本帖最後由 許浩浩 於 2025-3-22 07:16 編輯

1. APCS 實作題：
10503 - 4

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n,root;
   
5. int res,finalMaxChildDis;
   
6. 
   
7. struct Node
   
8. {
   
9.     int parent=-1,h=0;
   
10.     int maxChildDis=-1,max=-1,sec=-1;
    
11.     vector<int> child;
    
12. };
    
13. 
    
14. int main()
    
15. {
    
16.     cin.tie(0);
    
17.     cin.sync_with_stdio(0);
    
18. 
    
19.     while(cin>>n)
    
20.     {
    
21.         finalMaxChildDis=-1;
    
22.         Node node[n];
    
23. 
    
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.         }
    
31. 
    
32.         for(int i=0;i<n;i++)
    
33.         {
    
34.             if(node[i].parent==1)
    
35.                 root=i;
    
36. 
    
37.             if(node[i].child.size()==0)
    
38.             {
    
39.                 int h=0;
    
40.                 int parent=node[i].parent;
    
41. 
    
42.                 while(parent!=-1)
    
43.                 {
    
44.                     h++;
    
45. 
    
46.                     if(h>node[parent].h)
    
47.                         node[parent].h=h;
    
48.                     else
    
49.                         break;
    
50.                     parent=node[parent].parent;
    
51.                 }
    
52.             }
    
53.         }
    
54. 
    
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;
    
71. 
    
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;
    
80. 
    
81.         cout<<res<<endl;
    
82.     }
    
83. 
    
84.     return 0;
    
85. }

複製代碼

2. APCS 觀念題：10510 - 12、13

1. (B) (B)

複製代碼

---

作者: 江家同    時間: 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)

---

歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)

Powered by Discuz! 7.2