程式碼：(前綴和、後綴和、前綴奇數數量序列、後綴奇數數量序列、two pointers)

#include <iostream>
using namespace std;
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long arr[n], pre[n], suf[n], pre_odd[n], suf_odd[n];

    cin >> arr[0];
    pre[0] = arr[0];
    pre_odd[0] = arr[0]%2;

    for (int i = 1 ; i < n ; i ++) {
        cin >> arr[i];
        pre[i] = arr[i] + pre[i-1];
        pre_odd[i] = pre_odd[i-1] + arr[i]%2;
    }

    suf[n-1] = arr[n-1];
    suf_odd[n-1] = arr[n-1]%2;

    for (int i = n-2 ; i > 0 ; i --) {
        suf[i] = arr[i] + suf[i+1];
        suf_odd[i] = suf_odd[i+1] + arr[i]%2;
    }

    int left, right;
    long long sum = 0, odd_cnt = 0, best = 0;
    for (left = -1 ; left < n ; left ++) {
        for (right = n ; right > left ; right --) {
            if (left == -1 && right == n) continue;
            if (left == -1) {
                if (suf[right] > k) break;
                if (suf_odd[right] * 2 == n - right) best = max(best, suf[right]);
            } else if (right == n) {
                if (pre[left] > k) break;
                if (pre_odd[left] * 2 == left+1) best = max(best, pre[left]);
            } else {
                sum = pre[left] + suf[right];
                odd_cnt = pre_odd[left] + suf_odd[right];
                if (sum > k) break;
                if (odd_cnt * 2 == left+1+n-right) best = max(best, sum);
            }
        }
    }

    cout << best;
    return 0;
}

結果：NA(20%)，測資 #4 及之後都出現 記憶體區段錯誤

請問為何會RE？？

程式碼：(前綴和、後綴和、前綴奇數數量序列、後綴奇數數量序列、two pointers)

#include
using namespace std;
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long arr[n], pre[n], suf[n], pre_odd[n], suf_odd[n];

    cin >> arr[0];
    pre[0] = arr[0];
    pre_odd[0] = arr[0]%2;

    for (int i = 1 ; i < n ; i ++) {
        cin >> arr[i];
        pre[i] = arr[i] + pre[i-1];
        pre_odd[i] = pre_odd[i-1] + arr[i]%2;
    }

    suf[n-1] = arr[n-1];
    suf_odd[n-1] = arr[n-1]%2;

    for (int i = n-2 ; i > 0 ; i --) {
        suf[i] = arr[i] + suf[i+1];
        suf_odd[i] = suf_odd[i+1] + arr[i]%2;
    }

    int left, right;
    long long sum = 0, odd_cnt = 0, best = 0;
    for (left = -1 ; left < n ; left ++) {
        for (right = n ; right > left ; right --) {
            if (left == -1 && right == n) continue;
            if (left == -1) {
                if (suf[right] > k) break;
                if (suf_odd[right] * 2 == n - right) best = max(best, suf[right]);
            } else if (right == n) {
                if (pre[left] > k) break;
                if (pre_odd[left] * 2 == left+1) best = max(best, pre[left]);
            } else {
                sum = pre[left] + suf[right];
                odd_cnt = pre_odd[left] + suf_odd[right];
                if (sum > k) break;
                if (odd_cnt * 2 == left+1+n-right) best = max(best, sum);
            }
        }
    }

    cout << best;
    return 0;
}

結果：NA(20%)，測資 #4 及之後都出現 記憶體區段錯誤

請問為何會RE？？

RE問題已解決（將陣列宣告於全域），但是TLE，請問怎麼辦？

程式碼：(前綴和、後綴和、前綴奇數數量序列、後綴奇數數量序列、two pointers)

#include
using namespace std;
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long arr[n], pre[n], suf[n], pre_odd[n], suf_odd[n];

    cin >> arr[0];
    pre[0] = arr[0];
    pre_odd[0] = arr[0]%2;

    for (int i = 1 ; i < n ; i ++) {
        cin >> arr[i];
        pre[i] = arr[i] + pre[i-1];
        pre_odd[i] = pre_odd[i-1] + arr[i]%2;
    }

    suf[n-1] = arr[n-1];
    suf_odd[n-1] = arr[n-1]%2;

    for (int i = n-2 ; i > 0 ; i --) {
        suf[i] = arr[i] + suf[i+1];
        suf_odd[i] = suf_odd[i+1] + arr[i]%2;
    }

    int left, right;
    long long sum = 0, odd_cnt = 0, best = 0;
    for (left = -1 ; left < n ; left ++) {
        for (right = n ; right > left ; right --) {
            if (left == -1 && right == n) continue;
            if (left == -1) {
                if (suf[right] > k) break;
                if (suf_odd[right] * 2 == n - right) best = max(best, suf[right]);
            } else if (right == n) {
                if (pre[left] > k) break;
                if (pre_odd[left] * 2 == left+1) best = max(best, pre[left]);
            } else {
                sum = pre[left] + suf[right];
                odd_cnt = pre_odd[left] + suf_odd[right];
                if (sum > k) break;
                if (odd_cnt * 2 == left+1+n-right) best = max(best, sum);
            }
        }
    }

    cout << best;
    return 0;
}

結果：NA(20%)，測資 #4 及之後都出現 記憶體區段錯誤

請問為何會RE？？

RE問題已解決（將陣列宣告於全域），但是TLE，請問怎麼辦？

在尋找答案時，使用雙層for-loop，時間複雜度為O(n^2)，但n很大，所以用n log n的二分搜。

具體實作

我的方法是先把每個奇偶數量和位置存成map，枚舉右邊數字的後綴和所對應到的右座標，在利用最大值k以及最右邊為對應位置-1進行二分搜，還有考慮只選其中一邊的情形。

參考答案

程式碼：(前綴和、後綴和、前綴奇數數量序列、後綴奇數數量序列、two pointers)

#include
using namespace std;
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long arr[n], pre[n], suf[n], pre_odd[n], suf_odd[n];

    cin >> arr[0];
    pre[0] = arr[0];
    pre_odd[0] = arr[0]%2;

    for (int i = 1 ; i < n ; i ++) {
        cin >> arr[i];
        pre[i] = arr[i] + pre[i-1];
        pre_odd[i] = pre_odd[i-1] + arr[i]%2;
    }

    suf[n-1] = arr[n-1];
    suf_odd[n-1] = arr[n-1]%2;

    for (int i = n-2 ; i > 0 ; i --) {
        suf[i] = arr[i] + suf[i+1];
        suf_odd[i] = suf_odd[i+1] + arr[i]%2;
    }

    int left, right;
    long long sum = 0, odd_cnt = 0, best = 0;
    for (left = -1 ; left < n ; left ++) {
        for (right = n ; right > left ; right --) {
            if (left == -1 && right == n) continue;
            if (left == -1) {
                if (suf[right] > k) break;
                if (suf_odd[right] * 2 == n - right) best = max(best, suf[right]);
            } else if (right == n) {
                if (pre[left] > k) break;
                if (pre_odd[left] * 2 == left+1) best = max(best, pre[left]);
            } else {
                sum = pre[left] + suf[right];
                odd_cnt = pre_odd[left] + suf_odd[right];
                if (sum > k) break;
                if (odd_cnt * 2 == left+1+n-right) best = max(best, sum);
            }
        }
    }

    cout << best;
    return 0;
}

結果：NA(20%)，測資 #4 及之後都出現 記憶體區段錯誤

請問為何會RE？？

RE問題已解決（將陣列宣告於全域），但是TLE，請問怎麼辦？

在尋找答案時，使用雙層for-loop，時間複雜度為O(n^2)，但n很大，所以用n log n的二分搜。

具體實作

我的方法是先把每個奇偶數量和位置存成map，枚舉右邊數字的後綴和所對應到的右座標，在利用最大值k以及最右邊為對應位置-1進行二分搜，還有考慮只選其中一邊的情形。

參考答案

突然想到似乎可以壓成O(n)，連前綴都不用，結果範例測資就出錯了

#include <iostream>
#define MAXN 300001
using namespace std;
long long arr[MAXN];
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    long long n, k, selected = 0, cnt, odd_cnt = 0, best = 0;
    cin >> n >> k;
    cnt = n;

    for (int i = 0 ; i < n ; i ++) {
        cin >> arr[i];
        selected += arr[i];
        odd_cnt += arr[i]%2;
    }

    int left = -1, right = 0;
    while (left < n) {
        if (selected > k) {
            if (right == n-1) break;
            right ++;
            selected -= arr[right-1];
            odd_cnt -= arr[right-1]%2;
            cnt --;
        } else {
            if (odd_cnt*2 == cnt) best = max(best, selected);
            left ++;
            selected += arr[left];
            odd_cnt += arr[left]%2;
            cnt ++;
        }
    }

    cout << best;
    return 0;
}

請問為甚麼？？

程式碼：(前綴和、後綴和、前綴奇數數量序列、後綴奇數數量序列、two pointers)

#include
using namespace std;
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    long long arr[n], pre[n], suf[n], pre_odd[n], suf_odd[n];

    cin >> arr[0];
    pre[0] = arr[0];
    pre_odd[0] = arr[0]%2;

    for (int i = 1 ; i < n ; i ++) {
        cin >> arr[i];
        pre[i] = arr[i] + pre[i-1];
        pre_odd[i] = pre_odd[i-1] + arr[i]%2;
    }

    suf[n-1] = arr[n-1];
    suf_odd[n-1] = arr[n-1]%2;

    for (int i = n-2 ; i > 0 ; i --) {
        suf[i] = arr[i] + suf[i+1];
        suf_odd[i] = suf_odd[i+1] + arr[i]%2;
    }

    int left, right;
    long long sum = 0, odd_cnt = 0, best = 0;
    for (left = -1 ; left < n ; left ++) {
        for (right = n ; right > left ; right --) {
            if (left == -1 && right == n) continue;
            if (left == -1) {
                if (suf[right] > k) break;
                if (suf_odd[right] * 2 == n - right) best = max(best, suf[right]);
            } else if (right == n) {
                if (pre[left] > k) break;
                if (pre_odd[left] * 2 == left+1) best = max(best, pre[left]);
            } else {
                sum = pre[left] + suf[right];
                odd_cnt = pre_odd[left] + suf_odd[right];
                if (sum > k) break;
                if (odd_cnt * 2 == left+1+n-right) best = max(best, sum);
            }
        }
    }

    cout << best;
    return 0;
}

結果：NA(20%)，測資 #4 及之後都出現 記憶體區段錯誤

請問為何會RE？？

RE問題已解決（將陣列宣告於全域），但是TLE，請問怎麼辦？

在尋找答案時，使用雙層for-loop，時間複雜度為O(n^2)，但n很大，所以用n log n的二分搜。

具體實作

我的方法是先把每個奇偶數量和位置存成map，枚舉右邊數字的後綴和所對應到的右座標，在利用最大值k以及最右邊為對應位置-1進行二分搜，還有考慮只選其中一邊的情形。

參考答案

突然想到似乎可以壓成O(n)，連前綴都不用，結果範例測資就出錯了

#include
#define MAXN 300001
using namespace std;
long long arr[MAXN];
int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    long long n, k, selected = 0, cnt, odd_cnt = 0, best = 0;
    cin >> n >> k;
    cnt = n;

    for (int i = 0 ; i < n ; i ++) {
        cin >> arr[i];
        selected += arr[i];
        odd_cnt += arr[i]%2;
    }

    int left = -1, right = 0;
    while (left < n) {
        if (selected > k) {
            if (right == n-1) break;
            right ++;
            selected -= arr[right-1];
            odd_cnt -= arr[right-1]%2;
            cnt --;
        } else {
            if (odd_cnt*2 == cnt) best = max(best, selected);
            left ++;
            selected += arr[left];
            odd_cnt += arr[left]%2;
            cnt ++;
        }
    }

    cout << best;
    return 0;
}

請問為甚麼？？

可以打註解或說明一下想法嗎