APCS. 2019/02/16

2019/02/19 APCS實作題詳解及範例程式

pA

無確切題目敘述及輸入格式。

pB

Description

給定一個長度為$n(1<n\le10^5)$的01字串，計算最長與最短的連續1長度。
接著有$k(1 \le k \le 2*10^4)$次操作，每次將一個0改成1。
對於每次操作，輸出當前最長與最短的連續1長度(包括一開始輸入的)。

Solution

題目中有特別說到保證連續1的長度不超過$10^4$，所以可以用線性做法，不過這裡是考慮到當沒有這個限制時，應該怎麼做。

使用Disjoint Set(並查集)紀錄連通塊(相鄰的1為同一塊)，接著用multiset紀錄每個連通塊的大小。
對於每次輸入，把該點的兩邊(注意要考慮到可能只有一邊是1的可能)的大小在multiset中去掉，然後用Disjoint Set合併，再將新的大小插入到multiset裡面。
輸出的時候輸出set中最大最小值即可。

時間複雜度：$O(n + klogn)$

Code

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

const int maxn = 10010;
int n, k;
int in[maxn];
multiset<int> s;
struct disjoint_set {
    int parent[maxn];
    int size[maxn];
    void init() {
        for (int i = 0; i <= maxn; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    int find(int i) {
        if (i == parent[i])
            return i;
        return parent[i] = find(parent[i]);
    }
    void connect(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        s.erase(s.find(size[pa]));
        s.erase(s.find(size[pb]));
        size[pa] += size[pb];
        parent[pb] = pa;
        s.insert(size[pa]);
    }
}ds;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    ds.init();
    for (int i = 1; i <= n; i++) {
        cin >> in[i];
        if (in[i])
            s.insert(1);
    }
    for (int i = 2; i <= n; i++) {
        if (in[i - 1] && in[i]) {
            ds.connect(i - 1, i);
        }
    }
    cout << *s.begin() << ' ' << *s.rbegin() << '\n';
    while (k--) {
        int i;
        cin >> i;
        ds.size[i] = 1;
        s.insert(1);
        if (i > 1 && in[i - 1])
            ds.connect(i - 1, i);
        if (i < n && in[i + 1])
            ds.connect(i, i + 1);
        in[i] = 1;
        cout << *s.begin() << ' ' << *s.rbegin() << '\n';
    }
    return 0;
}

pC

Description

給你三個數值函數f,g,h的定義，變數數目各為1,2,3，且保證均為一次函數。輸入一個三者的合成函數但所有括號與逗點都被空白取代，計算該合成函數的值。題目中提示可以用遞迴，並保證不必使用大數運算。

Solution

遞迴做下去。
由於我沒有f,g,h的係數，所以在程式中會標示為$f0, g0, g1, h0, h1, h2$代表各個係數。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f0, g[2], h[3];
ll toll(string &s) {
    ll re = 0;
    for (char &i : s) {
        re *= 10;
        re += i - '0';
    }
    return re;
}
ll calc(char cmd) {
    string s;
    ll re = 0;
    if (cmd == 'f') {
        cin >> s;
        if (isdigit(s[0]))
            re = f0 * toll(s);
        else
            re = f0 * calc(s[0]);
    }else if (cmd == 'g') {
        for (int i = 0; i < 2; i++) {
            cin >> s;
            if (isdigit(s[0]))
                re += g[i] * toll(s);
            else
                re += g[i] * calc(s[0]);
        }
    }else
        for (int i = 0; i < 3; i++) {
            cin >> s;
            if (isdigit(s[0]))
                re += h[i] * toll(s);
            else
                re += h[i] * calc(s[0]);
        }
    return re;
}
void init() {
    // 測試用係數
    f0 = 2;
    g[0] = 1, g[1] = 2;
    h[0] = 1, h[1] = 3, h[2] = 4;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // init();
    char cmd;
    cin >> cmd;
    cout << calc(cmd) << '\n';
    return 0;
}

pD

Description

給定$n(1<n<2*10^5)$，及長度為$n$的陣列a和b$(0 \le a[i], b[i] \le 10^7)$。
$S(i)=i-max(j)-1 使得 a[i]+b[i]<a[j] 且 j<i (若j不存在，則j=0)$。
求$\sum_{i=1}^n S(i)$為何。

Solution

從前面做到後面，假設當前index為$i$，則可以刪掉一些在$i$之前「不可能為答案」的數字。
這樣講解有點抽象，從下面的圖片比較容易懂：
考慮$a[1]\text{~}a[5]$，可以發現$a[2]和a[4]$不可能為答案，因為$a[5]$比這兩個數字都還大。
所以可以把灰色部分砍掉，維護一個「遞減陣列」。
而有了這個遞減陣列，就可以利用$a[6]+b[6]$去二分搜，找出最大的j滿足條件。

不過到這裡還沒完，假設$S(i)$算完了，那應該要想辦法把$a[i]$加入該陣列。對於一個現成的遞減陣列，要怎麼加入新的元素？
一直檢查該陣列的後面，如果小於$a[i]$，則pop掉，否則就把$a[i]$加到最後面即可。

時間複雜度：$O(nlogn)$

注意：因為upper_bound預設是用在「遞增陣列」，並非遞減。所以我這裡在upper_bound時使用rbegin和rend，是因為我是維護一個遞減數列，但是upper_bound只適用遞增數列，所以就用反向的iterator來處理。

Code

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

typedef long long ll;
const int maxn = 200010;
int a[maxn], b[maxn];
int n;
ll ans;
struct node {
    int num, index;
    node() {}
    node (int a, int b) {
        num = a, index = b;
    }
    bool operator< (const node &b) const {
        return num < b.num;
    }
};
vector<node> arr;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++) {
        auto ptr = upper_bound(arr.rbegin(), arr.rend(), node(a[i] + b[i], 0));
        if (ptr == arr.rend())
            ans += i - 1;
        else
            ans += i - ptr->index - 1;
        while (!arr.empty() && arr.back().num < a[i])
            arr.pop_back();
        arr.push_back({a[i], i});
    }
    cout << ans << '\n';
    return 0;
}