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