APCS【2022年1月】題解整理

題解整理

ZeroJudge

1. h081: 程式交易
2. h082: 贏家預測
3. h083: 數位占卜
4. h084: 牆上海報

P1：股票買入賣出

輸入 n 天的股票價、正整數 d。
第 1 天規定要買入。
如果手上有 1 張股票，且「該天的股票價」比「上次的買入價」高 d 以上，就賣出。
如果手上有 0 張股票，且「該天的股票價」比「上次的賣出價」少 d 以上，就買入。
利潤 = 賣出 – 買入，如果手上持有股票卻未賣出，則利潤為 0。
求總利潤為多少？

#include <iostream>
using namespace std;
int main(){
    int n, d, ans=0;
    cin >> n >> d;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    int have=1, in=a[0], out=0;
    for(int i=1; i<n; i++){
        if(have==1 && a[i]-in>=d){
            out = a[i];
            ans += out-in;
            have=0;
        }else if(have==0 && out-a[i]>=d){
            in = a[i];
            have=1;
        }
    }
    cout << ans << '\n';
}

P2：兩兩對戰

輸入 n 位選手，每個人有戰力值 a 和應變力 b。
給定選手出場順序，第1位和第2位pk，第3位和第4位pk，以此類推。
(若選手為奇數，也就是最後一位沒對手，則他此回合中是贏方)
透過以下方式分出贏方、輸方：
(待補)
如果某選手輸了 m 次，則淘汰退出。
新的選手出場順序：所有組的贏方 + 所有組的輸方。
一直進行新的回合，直到剩下一名勝利者。
求最後的勝利者是誰？

P3：字串拆半

輸入 n 個字串。
如果字串 a 和字串 b 串聯起來，可以切成左右相同的兩半，則答案數+1。
求答案為多少？
有以下性質：(題目給的)
1. a+b = b+a，只需計算一次。
2. 如果有可能是答案，a 和 b 的長度絕對不一樣。
3. 如果有可能是答案，且 a 比較長，則 b 是 a 的子字串。

P4：柱子上的海報

輸入 n 個柱子，每根高度為 h[i]。
像是：
0 1 0 0 0
1 1 0 0 1
1 1 0 1 1
1 1 1 1 1
有 k 個海報，高度為 1，寬度為 w[i]。
我們想把 k 個海報按照順序掛在柱子上，且每個海報都一樣高，而且越高越好！
求最高可以掛多高？