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";
}

APCS 2021/9/5

1. 對聯

  • A : 2, 4字平仄不同 && 2, 6平仄相同
  • B : 第一句最後一字仄,第二句則是平
  • C : 第一二句2, 4, 6 字分別平仄不同

input : 七言對聯 0->平, 1->仄

1
0 0 0 0 1 1 1
1 1 1 1 0 0 0

ouput : 違反ABC哪些個規則就輸出相對應的英文字母(ABC),若沒違反則輸出 "None"

A

2. 炸彈魔王

遊戲採回合制,回合開始時若魔王位於炸彈上則所有在同一格的魔王會連同炸彈一起消失,所有未消失的魔王會先在腳下放一顆炸彈,再依據方向向量(s, t)移動。移動到邊界外的魔王視為消失。 求所有魔王消失時還有未爆彈的地點數。

n,m,r,c <= 100, k<500, |s,t|<=10

input : 第一行 n, m, k 分別表示地圖長寬以及魔王數,接下來有 k 行每一行都有 r, c, s, t 分別表示魔王初始位置座標,以及移動向量。

3 3 2
1 2 0 -1
2 1 1 -2

output:

5

3. 幸運號碼

給一個陣列,依據以下步驟尋找答案。

  1. 找到區間最小值
  2. 依據最小值分為左右兩邊詢問
  3. 選擇區間和較小的一邊作為下個搜索區間 n<=300000

input :

6
3 2 1 5 4 7

output:

7

4. 美食

有 n 攤美食和 k 個人,每個人必須吃連續區段的攤位,且菜色不得重複。求最大可以被吃到的攤位數。

n<=1000000, k<=20, nk<=5000000, a[i]<100000

其他限制 50% k=1 100% none

input :

5 1
1 2 3 1 2

output:

3

C++ APCS實作題 2020/1 4 : 貨物分配

關於樹狀圖的應用

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

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
    if(a>=n) return w[a];
    w[a]=dfs(child[a][0])+dfs(child[a][1]);
    return w[a];
}

int findBox(int stw,int a){
    if(a>=n){
        return a;
    }
    if(w[child[a][0]]<=w[child[a][1]]){
        w[child[a][0]]+=stw;
        return findBox(stw,child[a][0]);
    }
    w[child[a][1]]+=stw;
    return findBox(stw,child[a][1]);
}

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

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

    for(int i=0;i<m;i++) cin>>st[i];

    for(int i=1;i<n;i++){
        int p,s,t;cin>>p>>s>>t;
        child[p][0]=s;child[p][1]=t;
    }
    int root=1;
    w[1]=dfs(root);
    for(int i=0;i<m;i++){
        cout<<findBox(st[i],root)<<" ";
    } 

    return 0;
}

C++ APCS實作題 2017/10 3 : 樹狀圖分析

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ,另外用了 height[] 來儲存高度以降低複雜度。

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
    height[a]=0;
    for(long long v:child[a]){
        dfs(v);
        height[a]=max(height[a],height[v]+1);
    }
    return;
}

int main(){
    cin>>n;
    For(i,1,n+1){
        long long chN;cin>>chN;
        For(j,0,chN){
            long long ch;cin>>ch;
            child[i].push_back(ch);
            p[ch]=i;
        }
    }
    int root;
    for(root=1;root<=n;root++){
        if(p[root]==0) break;
    }
    dfs(root);
    long long total=0;
    for(int i=1;i<=n;i++) total+=height[i];
    cout<<root<<"\n";
    cout<<total<<"\n";
    return 0;
}

C++ APCS 實作題 2020/7 3 : 圓環出口

計算前綴和以及二分搜,以下為程式碼

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

int main(){
    ios::sync_with_stdio(false);

    int n,m;cin>>n>>m;

    int q,pSum[200010];
    cin>>pSum[0];
    for(int i=1;i<n;i++){
        cin>>pSum[i];
        pSum[i]=pSum[i]+pSum[i-1];
    }
    int pos=0;
    for(int i=0;i<m;i++){
        cin>>q;
        if(pos!=0){
            if(q>(pSum[n-1]-pSum[pos-1])){
                q-=(pSum[n-1]-pSum[pos-1]);
                q%=pSum[n-1];
                pos=lower_bound(pSum,pSum+n,q)-pSum+1;
            }else{
                pos=lower_bound(pSum,pSum+n,q+pSum[pos-1])-pSum+1;
            }
        }else{
            q%=pSum[n-1];
            pos=lower_bound(pSum,pSum+n,q)-pSum+1;
        }
        pos%=n;
    }
    cout<<pos;
    return 0;
}

C++ APCS 實作題 2019/06/15 2 : 機器人走迷宮

有意點點類似 BFS ,不過一次只會有一個分支,以下是程式碼

#include<iostream>
#include<deque>

#define MAX 1000000
using namespace std;

struct step{
    long long x,y;
};

int main(){
    int n,m,min=MAX+1;
    cin>>n>>m;
    long long sum=0;
    step best;
    int mp[110][110]={MAX};

    for(int i=0;i<110;i++){
        for(int j=0;j<110;j++){
            mp[i][j]=MAX;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(min>mp[i][j]){
                min=mp[i][j];
                best.x=j;best.y=i;sum=min;
            } 
        }
    }

    deque<step> st;
    st.push_front(best);
    const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

    while(!st.empty()){
        step now=st.back();
        st.pop_back();

        min=MAX;

        mp[now.y][now.x]=MAX;
        for(int i=0;i<4;i++){
            step next;
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            if(mp[next.y][next.x]<min){
                min=mp[next.y][next.x];
                best.x=next.x;best.y=next.y;
            } 
        }
        if(min==MAX){
            continue;
        }else{
            sum+=mp[best.y][best.x];
            st.push_front(best);
        }

    }
    cout<<sum;
    return 0;
}

C++ APCS實作題 2021/1 4 : 飛黃騰達

經典的 LIS(最長遞增子序列)

但把 lower_bound() 改成 upper_bound() 就會過了。 (這點我也想了一下)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

pair<int,int> pt[200005];

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

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>pt[i].first>>pt[i].second;
    }
    sort(pt,pt+n);
    vector<int> v;
    for(int i=0;i<n;i++){
        auto a=upper_bound(v.begin(),v.end(),pt[i].second);
        if(a==v.end()) v.push_back(pt[i].second);
        else *a=pt[i].second;
    }
    cout<<v.size();
    return 0;
}

C++ APCS實作題 2017/3 3 : 數字龍捲風

題目連結:c292. APCS2017-0304-3數字龍捲風 – 高中生程式解題系統

#include<bits/stdc++.h>

int map[101][101];
bool visit[101][101]={false};

int main(){
    int n,r;
    std::cin>>n>>r;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            std::cin>>map[i][j];
        }
    }

    int row=n/2,col=n/2;
    for(int i=0;i<n*n;i++){
        visit[row][col]=true;
        std::cout<<map[row][col];

        switch(r){
            case 0:
//left
                col--;
                if(!visit[row-1][col]){
                    r++;
                }
                break;
            case 1:
//up
                row--;
                if(!visit[row][col+1]){
                    r++;
                }
                break;
            case 2:
//right
                col++;
                if(!visit[row+1][col]){
                    r++;
                }
                break;
            case 3:
//down
                row++;
                if(!visit[row][col-1]){
                    r=0;
                }
                break;
        }
    }
    return 0;
}

C++ APCS實作題 2021/1 3 : 切割費用

用到了 set 和 iterator

#include<bits/stdc++.h>
using namespace std;
struct data{
    int x,i;
};
data dt[200000];
bool cmp(data a,data b){
    return a.i<b.i;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;int L;
    cin>>n>>L;
    for(int i=0;i<n;i++){
        cin>>dt[i].x;
        cin>>dt[i].i;
    }
    sort(dt,dt+n,cmp);
    set<int> s;
    s.insert(0);
    s.insert(L);
    long long sum=0;
    set<int>::iterator ptrE=s.begin();
    set<int>::iterator ptrB=s.end();
    for(int i=0;i<n;i++){
        s.insert(dt[i].x);
        ptrE=s.lower_bound(dt[i].x);
        ptrE--;
        ptrB=ptrE;
        ptrE++;ptrE++;
        sum+= (*ptrE)-(*ptrB); 
    }
    cout<<sum;
    return 0;
}