APCS 2022/1/9

作者:

Q1. 程式交易

題目連結：h081: 1. 程式交易 – 高中生程式解題系統

想法

第一天先買，維護一個 bool 變數，分為有持股與無持股兩種情況。

  1. 有持股->若當前價格>=當初買的價格(tp)+D，賣掉，tp 改為當前股價
  2. 無持股->若當前價格<=當初賣的價格(tp)-D，買起來，tp 改為當前股價

細節

若交易結束仍持有股票，則不考慮該股票買進的成本 -> 賣掉的時候再加上獲利

實作

#include<bits/stdc++.h>
using namespace std;

bool iss=true;
int n,sum,d,tp;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>d>>tp;

    for(int i=1;i<n;++i){
        int now;
        cin>>now;
        if(iss && tp+d<=now){
            sum+=now-tp;
            tp=now;
            iss=false;
        }else if(!iss && tp-d>=now){
            tp=now;
            iss=true;
        }
    }

    cout<<sum<<"\n";
}

Q2. 贏家預測

題目連結：h082. 2. 贏家預測 – 高中生程式解題系統

想法

將輸贏判斷抽象化，方便除錯。其餘依照題目用 vector 模擬即可。

實作

#include<bits/stdc++.h>
using namespace std;

#define siz(v) ((int)v.size())
using ll=long long;

struct player{
//  s, t, fail times
    ll s,t,f;
};

player ps[1005];
int n,m;

bool battle(int a,int b){
    bool ret=(ps[a].s*ps[a].t)>=(ps[b].s*ps[b].t);
    if(ret){
        ll tps=ps[a].s+(ps[b].s*ps[b].t)/(2*ps[a].t);
        ll tpt=ps[a].t+(ps[b].s*ps[b].t)/(2*ps[a].s);
        ps[a].s=tps;
        ps[a].t=tpt;

        ps[b].s+=ps[b].s>>1;
        ps[b].t+=ps[b].t>>1;
        ps[b].f++;
    }else{
        ll tps=ps[b].s+(ps[a].s*ps[a].t)/(2*ps[b].t);
        ll tpt=ps[b].t+(ps[a].s*ps[a].t)/(2*ps[b].s);
        ps[b].s=tps;
        ps[b].t=tpt;

        ps[a].s+=ps[a].s>>1;
        ps[a].t+=ps[a].t>>1;
        ps[a].f++;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>ps[i].s;
    for(int i=1;i<=n;++i) cin>>ps[i].t;

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

    while(siz(bt)>1){
        vector<int> vt,fl;
        for(int i=0;i<siz(bt);i+=2){
            if(i==siz(bt)-1){
                vt.emplace_back(bt[i]);
            }else{
                if(battle(bt[i],bt[i+1])){
                    vt.emplace_back(bt[i]);
                    if(ps[bt[i+1]].f<m) fl.emplace_back(bt[i+1]);
                }else{
                    if(ps[bt[i]].f<m) fl.emplace_back(bt[i]);
                    vt.emplace_back(bt[i+1]);
                }
            }
        }

        while(bt.size()) bt.pop_back();

        for(auto i:vt) bt.emplace_back(i);
        for(auto i:fl) bt.emplace_back(i);
    }

    cout<<bt.front();
}

Q3. 數位占卜

題目連結：h083. 3. 數位占卜 – 高中生程式解題系統

前言

這是我唯一沒有滿分的題目，要用 set<long long> 陣列，還要 rolling hash 。
參考資料：2022 01/09 APCS 題解 – HackMD

實作

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll MOD=2147483647;
const ll X=29;

// pwt[i]=29^i%MOD
// inv[i]=pwt[i] 在 MOD 的反元素
ll pwt[105],inv[105];
// hash value
ll h[50010][105];
// 原始資料
string s[50010];
// 對於長度為 i 的字串的 hash 值
set<ll> ss[105];

// 快速冪
ll POW(ll a,ll x){
    ll ret=1;
    while(x>0){
        if(x&1) ret=ret*a%MOD;
        a=a*a%MOD;
        x>>=1;
    }
    return ret;
}

void build(){
    pwt[0]=inv[0]=1;
    for(int i=1;i<=101;i++){
//      X^i%MOD
        pwt[i]=X*pwt[i-1]%MOD;
//      模逆元
        inv[i]=POW(pwt[i],MOD-2);
    }
}

void hah(string &tp,ll p){
    int m=tp.size();
//  不加 1 的話 a, aa, aaa 會被視為相同
    h[p][0]=tp[0]-'a'+1;
    for(int i=1;i<m;++i){
        h[p][i]=(h[p][i-1]+(tp[i]-'a'+1)*pwt[i])%MOD;
    }
    ss[m].insert(h[p][m-1]);
}

// 第 p 個字串的 [l,r] hash 前綴和的值
ll query(ll p,ll l,ll r){
    return l==0 ? h[p][r] : (h[p][r]-h[p][l-1]+MOD)%MOD*inv[l]%MOD;
}

ll solve(int n){
    ll ans=0;
    for(int i=0;i<n;++i){
        ll m=s[i].size();
        for(int j=1;j<m;++j){
//          從中間開始
            if(j*2<=m) continue;
//          若第 i 個字串的 [0,m-j-1] 與 [j,m-1] 相同
            if(query(i,0,m-j-1)==query(i,j,m-1)){
//              尋找匹配字串，(j*2-m) 補齊字串長度
                if(ss[j*2-m].count(query(i,m-j,j-1)))
                    ans++;
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n;
    cin>>n;
    build();
    for(int i=0;i<n;++i){
        cin>>s[i];
        hah(s[i],i);
    }

    cout<<solve(n)<<"\n";
}

Q4. 牆上海報

題目連結：h084. 4. 牆上海報 – 高中生程式解題系統

想法

Greedy + 二分搜。避免有人不知道要搜什麼，是搜尋高度。因為從題目中我們可以發現 -> 越高的地方可以放東西的區間越來越破碎，也越來越少。且若 x 是可以放的下的高度，選 x\'< x 都不會更好(題目要求越高越好)。這樣就可以一次刪除一半的區間。

那 Greedy 呢？因為有規定擺放順序，因此能放就放，這個區間放不下就移至下個區間。沒有區間可以放就表示這個高度不合法。

實作

#include<bits/stdc++.h>
using namespace std;

int n,k;
int h[200010],bd[50010];

bool check(int x){
    int psum=0;
    vector<int> len;
    for(int i=1;i<=n;++i){
        if(h[i]>=x){
            psum++;
        }else{
            len.emplace_back(psum);
            psum=0;
        }
    }
//  0也無所謂
    len.emplace_back(psum);

    for(int i=1,j=0;i<=k;++i){
        while(len[j]<bd[i]){
            j++;
            if(j==len.size()) return false;
        }
        len[j]-=bd[i];
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>h[i];
    for(int i=1;i<=k;++i) cin>>bd[i];

    int l=0,r=1073741824;
    while(r-l>1){
        int mid=l+r>>1;
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }

    cout<<l<<"\n";
}

發佈留言