Peienwu's Blog

Hello world

0%

APCS題解：2021年1月

發表於 分類於 Valine：
文章字數： 4.4k 所需閱讀時間 ≈ 4 分鐘


第一次考APCS，拿到觀念4級、實作3級，希望在下一次可以更進步！（我是大廢廢

110/01 實作題第一題 購買力

APCS的第一題都是應該要秒殺的，也順利拿到100分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int n,d,cost = 0,total = 0;

signed main(){ 
    ios;
    cin>>n>>d;
    int arr[3];
    for(int i=0;i<n;i++){
        cin>>arr[0]>>arr[1]>>arr[2];
        sort(arr, arr+3);
        if(arr[2]-arr[0]>=d){
            total++;
            cost +=((arr[0]+arr[1]+arr[2])/3);
        }
    }
    cout<<total<<" "<<cost<<endl;
}

110/01 實作題第二題 流量

這一題的題序有點複雜，看了幾次之後才看懂。但重點是在考試的時候沒有想到要怎麼合併流量，所以只用了一維陣列計算最小值，因此只有拿到50分…
這是完整版的程式碼，主要是透過創建一個陣列r[i][j]，表示從城市i出發到城市j的總流量，再利用陣列r計算費用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
using namespace std;
int N,M,K,s[50][50],r[50][50];

signed main(){
    ios;
    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>s[i][j];
        }
    }
    int ans = 1e8;
    
    for(int k=0;k<K;k++){
        memset(r, 0, sizeof(r));
        
        for(int q=0;q<N;q++){
            int p;//第i個伺服器架設在p城市
            cin>>p;
            for(int j=0;j<M;j++)r[p][j]+=s[q][j];
        }
        //如果第0個跟第1個伺服器都架設在1的位置，則將流量相加，得到陣列r
        int sum = 0;
        for(int q=0;q<M;q++){//0<p<M
            for(int j=0;j<M;j++){
                if(q==j)sum+=r[q][j];
                else if(r[q][j]<=1000)sum+=3*r[q][j];
                else sum+=(r[q][j]-1000)*2+3000;
            }
        }
        ans = min(ans,sum);
    }
    cout<<ans<<endl;
}

110/01 實作題第三題 切割費用

這一題雖然在考試中有想到利用二元樹的方法，於是開了一個陣列儲存樹的節點（前段時間寫了一些線段樹，所以用了這個方法！）但我沒有注意到這不是一棵完滿二元樹，不會平衡啊！把範例測資丟上去對了，結果半分都沒有拿到:cry:，以後必須注意！
用std::set搭配 next(),prev() 指標，找出鄰近的切割點之差，就可以AC了！


在 set 中使用insert() 函式會回傳pair 在使用的時候要變成：

1
auto pos = s.insert(arr[i]).first;

這是考試送出的0分程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int n,L,ans = 0;
int seg[1000000] = {0};

void build(int val,int cur){
    if(seg[cur]==0){
        seg[cur] = val;
        return;
    }
    if(val>seg[cur])build(val, 2*cur+2);
    else build(val, 2*cur+1);
}//建立一個會爆掉的二元樹
void func(int val,int cur){
    int up = L,low = 0;
    if(seg[cur]==val){
        ans+=up-low;
        return;
    }
    while(seg[cur]!=val){
        if(val>seg[cur]){
            low = seg[cur];
            cur = 2*cur+2;
        }
        else{
            up = seg[cur];
            cur = 2*cur+1;
        }
    }
    ans+=up-low;
}

signed main(){
    ios;    
    cin>>n>>L;
    int arr[n];
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        arr[b-1] = a;
    }
    for(int i=0;i<n;i++)build(arr[i], 0);
    for(int i=0;i<n;i++)func(arr[i], 0);
    cout<<ans<<endl;
}

這是正解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int n,l,arr[200000];

signed main(){
    ios;
    cin>>n>>l;
    set<int> s = {0,l};
    for(int i=0;i<n;i++){
        int ind,pos;cin>>pos>>ind;
        arr[ind-1] = pos;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        auto pos = s.insert(arr[i]).first;
        ans+= *next(pos)- *prev(pos);
    }
    cout<<ans<<endl;
}

110/01 實作題第四題 飛黃騰達

這是一題我在考試中根本沒有碰的題目（能力不足），聽到別人是說這是一題經典的LIS，所以寒假就開始了解動態規劃的題目。這一題關鍵是先把x座標排列好（可以想成是LIS中的數列順序），然後依照y座標做LIS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
using namespace std;
int n;

signed main(){
    ios;
    cin>>n;
    pair<int, int> P[n];
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        P[i] = make_pair(x, y);
    }
    sort(P, P+n);//利用pair排序，會先依照x排序，如果x相同，則照y排序
    vector<int>ans;//儲存LIS
    ans.push_back(P[0].second);
    for(int i=1;i<n;i++){
        int now = P[i].second;
        if(now>=ans.back())ans.push_back(now);
        else{
            int ind = upper_bound(ans.begin(),ans.end(),now)-ans.begin();
            ans[ind] = now;
        }
    }
    cout<<ans.size()<<endl;
}

這裡有一點跟LIS不一樣，它不需要嚴格遞增，因此在第20使用 >= ，還有第22行使用upper_bound也是因為不需要嚴格遞增（如果要插入的值在LIS裡面就已經有了，兩者都可以保留，所以用upper_bound，取第一個大於它的數值更改掉。

心得

第一次參加APCS拿到4,3的成績，雖然沒有很好（這一次還是比較簡單的題目！），但還是在預期之內。希望透果補足一些不足的地方，下一次會有更好的成績！

  1. IDE環境不熟悉
    平常都是在mac上打程式，而所有的比賽都只有windows的codeblocks，有時候debug的內容不小被我關掉就叫不出來，耗費許多時間。
    解決方法：下載codeblocks來好好熟悉一下
  2. 題目練習不夠多
    在考試之前大多是聽別人講怎麼做，實際練習題目的量太少，所以在實際的競賽中就寫不出東西。
    解決方法：每週固定寫一個主題的題目，反覆練習讓自己對這個主題更熟悉+寫APCS考古題。
  3. 懂得東西太少
    本次第三題就是很好的例子，自己寫二元樹出一堆問題，不如用std內建的set還比較快！雖然一直都知道set的存在，但實際的競賽中就不知道怎麼用。
    解決方法：資訊之芽好好學！
  4. 實戰經驗不足
    這應該是參加過的第三場正式的競賽（或檢定），以後就慢慢累積比賽的經驗
    解決方法：參加線上程式競賽，練手感。
  5. 打字速度太慢
    打字速度慢就拖慢整體的寫扣時間，必須加強！
    解決方法：每天花10分鐘碰碰鍵盤，利用網路上打字練習加快打字速度。