APCS【2022年1月】題解整理

題解整理

題解連結作者
觀念題 HackMD演算法海牛
C++ 實作題(全) HackMD謝一
C++ P2 P3 P4Yui Huang
Python P1 P2 P3 P4吳邦一
Java P4 PIXNET阿祁

ZeroJudge

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

P1:股票買入賣出

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

//author: 培哥
#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    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 個海報按照順序掛在柱子上,且每個海報都一樣高,而且越高越好!
求最高可以掛多高?

APCS 2022/1/9, APCS 2022.1.9, APCS 2022/01/09, APCS 2022.01.09, APCS 111/01, APCS 111.01, APCS 11101

分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。