# 2022/01/09 APCS 題解 + 心得&檢討
###### tags: `資訊雙週計畫` 第1~2週


## 題解

### ==第一題：程式交易 [題目連結](https://zerojudge.tw/ShowProblem?problemid=h081)==

* 枚舉每天的股票價格，如果可以賣就賣，可以買就買。
* 複雜度：$O(n)$

:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0), cin.tie(0);
const int MAXN = 105;

int n, d, ans;
int a[MAXN];

int main() {

    FAST;

    cin >> n >> d;

    for (int i = 0; i < n; i++) 
        cin >> a[i];

    // now 紀錄現在的上一次的買（賣）的股票 
    //  z  紀錄現在是否有股票
    int now = a[0], have = 1;

    for (int i = 0; i < n; i++) {
        if (have == 1 && a[i] >= now+d) {            // 可以賣出
            ans += a[i]-now;                      // 利潤
            now = a[i];
            have = 0;
        } else if (have == 0 && a[i] <= now-d){      // 可以買進
            now = a[i];
            have = 1;
        }
    }

    cout << ans;
    
    return 0;

}

:::

---

### ==第二題：贏家預測 [題目連結](https://zerojudge.tw/ShowProblem?problemid=h082)==

* 按照順序進行戰鬥，並更新每人戰鬥後的戰鬥力、應變力。下一次的戰鬥順序在對戰時記錄誰贏誰輸，並將贏的放入*win*，輸的放進*nnnwin*，完成所有戰鬥再將戰鬥順序更新。lose [ *i* ]紀錄 第*i*人輸了幾次，所以當 lose [ *i* ] *= m* 時，他將不能在戰鬥，總人數減一。當最終只剩下一人時，輸出答案。
* 複雜度：$O(nm)$

:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0), cin.tie(0);
using ll = long long;
const ll MAXN = 1005;

ll n, m;
ll s[MAXN], t[MAXN], f[MAXN], lose[MAXN], len;
ll win[MAXN], nnnwin[MAXN], w, l;

void fight(ll i, ll j) {

    ll a = s[i], b = t[i];
    ll c = s[j], d = t[j];

    if (a*b >= c*d) {            // i贏下比賽

        s[i] = a+c*d/(2*b);
        t[i] = b+c*d/(2*a);

        s[j] = c+c/2;
        t[j] = d+d/2;

        if (++lose[j] == m) {    // j輸的次數達到上限
            win[w] = i;
            w++;
            n--;
        } else {
            win[w] = i;
            nnnwin[l] = j;
            w++;
            l++;
        }

    } else {                     // j贏下比賽
        
        s[i] = a+a/2;
        t[i] = b+b/2;

        s[j] = c+a*b/(2*d);
        t[j] = d+a*b/(2*c);

        if (++lose[i] == m) {    // i輸的次數達到上限
            win[w] = j;
            w++;
            n--;
        } else {
            win[w] = j;
            nnnwin[l] = i;
            w++;
            l++;
        }

    }

    return ;

}

void solve() {

    while (n > 1) {
        len = n;        // 戰鬥人數
        w = 0, l = 0;

        for (int i = 1; i < len; i+=2) {    // 兩兩戰鬥開始
            fight(f[i-1], f[i]);
        }

        if (len%2) win[w] = f[len-1], w++;   // 最後一人沒有人可以戰鬥算勝方

        // 更新下一次戰鬥的順序
        for (int i = 0; i < w; i++) f[i] = win[i];    
        for (int i = 0; i < l; i++) f[i+w] = nnnwin[i];

    }

    cout << f[0]+1;

    return ;

}

int main() {
    
    FAST;

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++) cin >> f[i], f[i]--;

    solve();
    
    return 0;

}

:::

---

### ==第三題：數位占卜 [題目連結](https://zerojudge.tw/ShowProblem?problemid=h083)==

* 枚舉所有的字串，並且從字串中間位置+1開始枚舉作為第二個字串的開頭，如果兩字串前綴相等，就可以查詢是否有可以形成兩個相等的字串，查詢時用set的find來查找。
* 複雜度：$O(m\ len\ log(m))$ ⇒ $len$ 為字串長度

:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0), cin.tie(0);
using ll = long long;
const ll MAXN = 5e4+4;

ll m, len, ans;
string s[MAXN];
set<string> w;

bool check(ll p, ll t, ll q) {        // 判斷第一個和第二個字串前綴是否相同

    for (int i = 0; i < q; i++)
        if (s[p][i] != s[p][i+t]) 
            return 0;
    
    return 1;

}

void solve() {

    for (int i = 0; i < m; i++) {    // 枚舉所有字串

        len = s[i].size();
        if (len == 1) continue;       // 字串長度1無法分解

        for (int j = len/2+len%2; j < len; j++) {
            // 判斷字串前綴是否相同，相同查詢是否有對應字串可以組成兩個相同字串
            if ( check(i, j, len-j) && 
                w.find( s[i].substr(len-j, 2*j-len ) ) != w.end() ) {
                ans++;
            }
        }

    }

    cout << ans;

    return ;

}

int main() {
    
    FAST;

    cin >> m;

    for (int i = 0; i < m; i++)
        cin >> s[i], w.insert(s[i]);

    solve();
    
    return 0;

}

:::

---

### ==第四題：牆上海報 [題目連結](https://zerojudge.tw/ShowProblem?problemid=h084)==

* 因為高度越低，連續的範圍越大，也就是可以掛更多海報；相對的高度越高，則掛的海報就較少。根據上述，因為符合單調性，因此可以對答案做2分搜，找出最大值。
* 複雜度：$O( (n+k)\ log(max(h)) )$

:::spoiler code

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(0), cin.tie(0);
#define eb emplace_back
const int MAXN = 2e5+5;

int n, k, mx;
int h[MAXN], w[MAXN];

bool check(int x) {

    int now = 0;
    vector<int> v;
    
    for (int i = 0; i < n; i++) {
        if (h[i] >= x) {
            now++;
        } else if (now != 0) {
            v.eb(now);
            now = 0;
        }
    }
    if (now != 0) v.eb(now);

    int i = 0;
    for (int j = 0; i < k && j < v.size(); j++) {
        while (i < k && w[i] <= v[j]) {
            v[j] -= w[i];
            i++;
        }
    }
    if (i >= k) return 1;
    else return 0;

}

void solve() {

    int L = 1, R = mx;    // 值域 = [1,mx]

    // 對答案2分搜
    while (L < R) {

        int mid = (L+R)>>1;
        if (L == mid) break;

        if (check(mid)) {    // 判斷 高度mid 是否可以放置所有海報
            L = mid;
        } else {
            R = mid-1;
        }

    }

    if (check(L+1)) cout << L+1;
    else cout << L;

    return ;

}

int main() {
    
    FAST;

    cin >> n >> k;

    for (int i = 0; i < n; i++) cin >> h[i], mx = max(mx, h[i]);
    for (int i = 0; i < k; i++) cin >> w[i];

    solve();
    
    return 0;

}

:::

## 心得 & 檢討

歷屆APCS成績：

:::info
| | 觀念題 | 實作題 |
| -------- | -------- | -------- |
| 2021/01/09 | 四級分（72） | 二級分（90） |
| 2021/09/05 | 四級分（88） | 三級分（220）|
| 2021/11/07 | 四級分（88） | 三級分（155）|
| 2022/01/09 | **五級分（96）** | **三級分（220）** |
:::

### 觀念
觀念的部分我第一節考的時後寫太慢了，所以不小心猜了2題:cry:，雖然是有排除一些不可能的選項後才猜的，希望那題不算分或我猜對了。好險第二節我找回狀態，30分鐘就寫完了，所以就在檢查一次，結果發現有一題我知道答案是B卻寫成C，真的是好險有檢查喔。

總之，希望這次觀念會有5級分，我不想要再拿88分（4級分頂）:angry:。

### 實作

這次的實作真的是超級簡單:scream:，考試時的想法都是正確的，Zerojudge的題目出來後就立刻測試，果然全部都AC，但是可惜這不是在考試當下。

考試當下，pA一下子就秒殺掉，接下來想說先去解個算法的題目，直接跳pC，雖然想到了我上面題解的想法，但是我不太相信自己，以為複雜度會爛掉，所以寫個20分暴力解就跳回pB了:cry:。pB很顯然的比上次簡單許多，但是自己應該是太少寫這種很麻煩的題目，所以bug就一大堆，寫完後，至少花了1個半小時debug吧？:tired_face:到最後剩10分鐘時總算把所有的bug清掉，然後決定去看看pD長什麼樣子，沒想到他居然比pC還要簡單很多，就直接對答案二分搜就可以了。要是先看到pD再看 pB pC，我這次就穩實作四級分了qq。所以這次預估實作只有三級分（220分）。

總之，這次就算是學了個教訓吧！有實力拿「實作5」的我這次可能只有3級分，這兩個分數真的差很多啊，沒辦法把握這麼好的一次機會真的可惜。下次還是乖乖的把所有題目看完，排好難度後再寫。

特殊選才前，還有6月和10月的兩次的APCS，希望能夠好好把握6月的APCS，因為10月考完後，成績公布時應該有些學校都已經面試完了。所以希望6月的APCS能夠盡量達到<font color="#f00">**觀念5實作4以上**</font>的成績。加油！！！:muscle::muscle::muscle:

（題外話：寫完這篇剛好是我生日ㄝ01/12:laughing:，17歲快樂～）

## 成績公布日～

終於公布了！雖然說這次實作很可惜，但是好險，觀念題有96，五級分，算是沒有白考了這次APCS。希望下次六月能夠不要燒雞，至少拿到實作四級，拚五級！加油！