c824的簡單版

思考：這題無法像正常背包一樣處理，因為是2ⁱ，i<=10⁹，所有資料類型都處理不了；但可以發現：大小都是2ⁿ，n=0,1,2,⋯⋯可以從這裡下手。

解題重點：可以將2個小的合併成1個大的，因為2ⁱ + 2ⁱ = 2ⁱ⁺¹ 可以用這個方法去dp。

解題步驟C++

1.宣告vector<long long> w[m+1]

2.w[a].push_back(b)

3.sort(w[i].begin(),w[i],end(),greater<>()) //讓大的排到前面

4.w[i+1].push_back(w[i][j]+w[i][j+1]) //核心步驟

5.cout << w[m][最大的方法]

然後如果有人知道c824怎麼AC拜託教一下我，感恩

c824的簡單版

思考：這題無法像正常背包一樣處理，因為是2ⁱ，i<=10⁹，所有資料類型都處理不了；但可以發現：大小都是2ⁿ，n=0,1,2,⋯⋯可以從這裡下手。

解題重點：可以將2個小的合併成1個大的，因為2ⁱ + 2ⁱ = 2ⁱ⁺¹ 可以用這個方法去dp。

解題步驟C++

1.宣告vector w[m+1]

2.w[a].push_back(b)

3.sort(w[i].begin(),w[i],end(),greater<>()) //讓大的排到前面

4.w[i+1].push_back(w[i][j]+w[i][j+1]) //核心步驟

5.cout << w[m][最大的方法]

 

然後如果有人知道c824怎麼AC拜託教一下我，感恩

C824 0.1s解法

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

// ======================================================================
// 自定義 Fast I/O (快速輸入) 區塊
// 由於 cin 甚至 scanf 在面對百萬級別的測資時仍嫌太慢，
// 這裡直接使用 fread 將資料整塊讀入記憶體緩衝區 (Buffer)，再手動解析字元轉成數字。
// ======================================================================
inline char readchar() {
    static const int BUF_SIZE = 1 << 16; // 64KB 的緩衝區
    static char buf[BUF_SIZE];
    static int pos = 0, len = 0;
    if (pos == len) {
        pos = 0;
        len = fread(buf, 1, BUF_SIZE, stdin); // 一次讀取一大塊
        if (len == 0) return EOF; // 讀到檔尾
    }
    return buf[pos++];
}

// 快速讀取 int
inline bool read_int(int &x) {
    char c = readchar();
    while (c != EOF && (c < '0' || c > '9')) c = readchar();
    if (c == EOF) return false;
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readchar();
    }
    return true;
}

// 快速讀取 long long (因為物品價值 b 可能很大)
inline bool read_ll(long long &x) {
    char c = readchar();
    while (c != EOF && (c < '0' || c > '9')) c = readchar();
    if (c == EOF) return false;
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readchar();
    }
    return true;
}
// ======================================================================

// 定義物品結構
struct Item {
    int a;       // 重量為 2^a
    long long b; // 價值為 b
    
    // 自定義排序規則：
    // 1. 優先按照重量指數 a 「由小到大」排序 (因為我們要從底層慢慢往上合併)
    // 2. 若重量相同，則按照價值 b 「由大到小」排序 (貪心策略：價值大的優先配對)
    bool operator<(const Item& other) const {
        if (a != other.a) return a < other.a;
        return b > other.b;
    }
};

int main() {
    int n, m;
    if (!read_int(n)) return 0;
    if (!read_int(m)) return 0;

    vector<Item> items;
    items.reserve(n); // 預先分配記憶體，避免 vector 動態擴容耗時
    
    for (int i = 0; i < n; ++i) {
        int a;
        long long b;
        read_int(a);
        read_ll(b);
        
        // 【關鍵過濾】：背包總容量只有 2^M。
        // 如果單一物品的重量 2^a 已經大於 2^M (即 a > M)，那絕對放不進去，直接丟棄不存。
        if (a <= m) {
            items.push_back({a, b});
        }
    }

    // 依照我們定義的規則排序 (a 升序，b 降序)
    sort(items.begin(), items.end());

    // U 陣列用來儲存「當前層級 (curr_level)」所有可用的物品價值。
    // 裡面的元素會隨時保持「由大到小」排序。
    vector<long long> U;
    int curr_level = -1; // 記錄目前處理到 2 的幾次方

    int i = 0;
    while (i < items.size()) {
        int next_level = items[i].a; // 下一批真實物品所在的層級

        // 如果 U 裡面已經有東西，我們需要把 U 裡面的物品一路「合併升級」到 next_level
        if (curr_level != -1) {
            // 當還沒到達目標層級，且 U 裡面至少有 2 個物品可以配對時
            while (curr_level < next_level && U.size() > 1) {
                curr_level++;
                vector<long long> next_U;
                next_U.reserve((U.size() + 1) / 2);
                
                // 【貪心合併】：因為 U 已經降序排列，
                // 我們把第 1 大和第 2 大合併、第 3 大和第 4 大合併...
                // 這樣可以確保合成出來的 2^(curr_level) 虛擬物品價值最大化。
                for (size_t j = 0; j < U.size(); j += 2) {
                    if (j + 1 < U.size()) {
                        next_U.push_back(U[j] + U[j+1]); // 兩個合併成一個
                    } else {
                        next_U.push_back(U[j]);          // 落單的直接晉級 (相當於跟價值 0 合併)
                    }
                }
                U = move(next_U); // 使用 move 轉移所有權，避免複製陣列的 O(N) 耗時
            }
            
            // 【跳躍空層優化】：
            // 如果 U 裡面只剩 1 個物品，它永遠無法再跟別人配對了。
            // 它的重量會一直翻倍直到 next_level，但價值不會變。
            // 為了避免 M 很大 (如 10^9) 時 while 迴圈跑太久 (TLE)，我們直接把層級跳到 next_level。
            if (curr_level < next_level && U.size() == 1) {
                curr_level = next_level;
            }
        } else {
            // 初始狀態，直接跳到第一個物品的層級
            curr_level = next_level;
        }

        // 收集所有屬於 next_level 的真實物品
        int start_i = i;
        while (i < items.size() && items[i].a == next_level) {
            i++;
        }

        // 【合併排序 (Merge)】：
        // 現在我們有兩批物品都在 next_level：
        // 1. U：從底層一路合併上來的虛擬物品 (已降序)
        // 2. items[start_i ... i-1]：原本就生在這個層級的真實物品 (已降序)
        // 我們使用類似 Merge Sort 的雙指標法，將它們合併成一個新的降序陣列。
        vector<long long> merged;
        merged.reserve(U.size() + (i - start_i));
        int p1 = 0, p2 = start_i;
        
        while (p1 < U.size() && p2 < i) {
            if (U[p1] >= items[p2].b) {
                merged.push_back(U[p1++]);
            } else {
                merged.push_back(items[p2++].b);
            }
        }
        // 把剩下的元素塞進去
        while (p1 < U.size()) merged.push_back(U[p1++]);
        while (p2 < i) merged.push_back(items[p2++].b);

        U = move(merged); // 更新 U 為合併後的結果
    }

    // 當所有真實物品都處理完後，U 裡面可能還有很多物品。
    // 我們必須繼續把它們兩兩合併，直到達到背包的最終限制層級 M。
    if (curr_level != -1) {
        while (curr_level < m && U.size() > 1) {
            curr_level++;
            vector<long long> next_U;
            next_U.reserve((U.size() + 1) / 2);
            for (size_t j = 0; j < U.size(); j += 2) {
                if (j + 1 < U.size()) {
                    next_U.push_back(U[j] + U[j+1]);
                } else {
                    next_U.push_back(U[j]);
                }
            }
            U = move(next_U);
        }
    }

    // 最終輸出結果
    if (U.empty()) {
        // 如果連一個合法的物品都沒有
        printf("0\n");
    } else {
        // 因為背包容量是 2^M，在層級 M 我們「最多只能挑選 1 個」物品。
        // 而 U 陣列是降序排列的，所以 U[0] 就是我們能湊出的最大總價值。
        printf("%lld\n", U[0]);
    }

    return 0;
}

c824的簡單版

思考：這題無法像正常背包一樣處理，因為是2ⁱ，i<=10⁹，所有資料類型都處理不了；但可以發現：大小都是2ⁿ，n=0,1,2,⋯⋯可以從這裡下手。

解題重點：可以將2個小的合併成1個大的，因為2ⁱ + 2ⁱ = 2ⁱ⁺¹ 可以用這個方法去dp。

解題步驟C++

1.宣告vector w[m+1]

2.w[a].push_back(b)

3.sort(w[i].begin(),w[i],end(),greater<>()) //讓大的排到前面

4.w[i+1].push_back(w[i][j]+w[i][j+1]) //核心步驟

5.cout << w[m][最大的方法]

 

然後如果有人知道c824怎麼AC拜託教一下我，感恩

C824 0.1s解法

#include
#include
#include
#include

using namespace std;

// ======================================================================
// 自定義 Fast I/O (快速輸入) 區塊
// 由於 cin 甚至 scanf 在面對百萬級別的測資時仍嫌太慢，
// 這裡直接使用 fread 將資料整塊讀入記憶體緩衝區 (Buffer)，再手動解析字元轉成數字。
// ======================================================================
inline char readchar() {
    static const int BUF_SIZE = 1 << 16; // 64KB 的緩衝區
    static char buf[BUF_SIZE];
    static int pos = 0, len = 0;
    if (pos == len) {
        pos = 0;
        len = fread(buf, 1, BUF_SIZE, stdin); // 一次讀取一大塊
        if (len == 0) return EOF; // 讀到檔尾
    }
    return buf[pos++];
}

// 快速讀取 int
inline bool read_int(int &x) {
    char c = readchar();
    while (c != EOF && (c < '0' || c > '9')) c = readchar();
    if (c == EOF) return false;
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readchar();
    }
    return true;
}

// 快速讀取 long long (因為物品價值 b 可能很大)
inline bool read_ll(long long &x) {
    char c = readchar();
    while (c != EOF && (c < '0' || c > '9')) c = readchar();
    if (c == EOF) return false;
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readchar();
    }
    return true;
}
// ======================================================================

// 定義物品結構
struct Item {
    int a;       // 重量為 2^a
    long long b; // 價值為 b
    
    // 自定義排序規則：
    // 1. 優先按照重量指數 a 「由小到大」排序 (因為我們要從底層慢慢往上合併)
    // 2. 若重量相同，則按照價值 b 「由大到小」排序 (貪心策略：價值大的優先配對)
    bool operator<(const Item& other) const {
        if (a != other.a) return a < other.a;
        return b > other.b;
    }
};

int main() {
    int n, m;
    if (!read_int(n)) return 0;
    if (!read_int(m)) return 0;

    vector items;
    items.reserve(n); // 預先分配記憶體，避免 vector 動態擴容耗時
    
    for (int i = 0; i < n; ++i) {
        int a;
        long long b;
        read_int(a);
        read_ll(b);
        
        // 【關鍵過濾】：背包總容量只有 2^M。
        // 如果單一物品的重量 2^a 已經大於 2^M (即 a > M)，那絕對放不進去，直接丟棄不存。
        if (a <= m) {
            items.push_back({a, b});
        }
    }

    // 依照我們定義的規則排序 (a 升序，b 降序)
    sort(items.begin(), items.end());

    // U 陣列用來儲存「當前層級 (curr_level)」所有可用的物品價值。
    // 裡面的元素會隨時保持「由大到小」排序。
    vector U;
    int curr_level = -1; // 記錄目前處理到 2 的幾次方

    int i = 0;
    while (i < items.size()) {
        int next_level = items[i].a; // 下一批真實物品所在的層級

        // 如果 U 裡面已經有東西，我們需要把 U 裡面的物品一路「合併升級」到 next_level
        if (curr_level != -1) {
            // 當還沒到達目標層級，且 U 裡面至少有 2 個物品可以配對時
            while (curr_level < next_level && U.size() > 1) {
                curr_level++;
                vector next_U;
                next_U.reserve((U.size() + 1) / 2);
                
                // 【貪心合併】：因為 U 已經降序排列，
                // 我們把第 1 大和第 2 大合併、第 3 大和第 4 大合併...
                // 這樣可以確保合成出來的 2^(curr_level) 虛擬物品價值最大化。
                for (size_t j = 0; j < U.size(); j += 2) {
                    if (j + 1 < U.size()) {
                        next_U.push_back(U[j] + U[j+1]); // 兩個合併成一個
                    } else {
                        next_U.push_back(U[j]);          // 落單的直接晉級 (相當於跟價值 0 合併)
                    }
                }
                U = move(next_U); // 使用 move 轉移所有權，避免複製陣列的 O(N) 耗時
            }
            
            // 【跳躍空層優化】：
            // 如果 U 裡面只剩 1 個物品，它永遠無法再跟別人配對了。
            // 它的重量會一直翻倍直到 next_level，但價值不會變。
            // 為了避免 M 很大 (如 10^9) 時 while 迴圈跑太久 (TLE)，我們直接把層級跳到 next_level。
            if (curr_level < next_level && U.size() == 1) {
                curr_level = next_level;
            }
        } else {
            // 初始狀態，直接跳到第一個物品的層級
            curr_level = next_level;
        }

        // 收集所有屬於 next_level 的真實物品
        int start_i = i;
        while (i < items.size() && items[i].a == next_level) {
            i++;
        }

        // 【合併排序 (Merge)】：
        // 現在我們有兩批物品都在 next_level：
        // 1. U：從底層一路合併上來的虛擬物品 (已降序)
        // 2. items[start_i ... i-1]：原本就生在這個層級的真實物品 (已降序)
        // 我們使用類似 Merge Sort 的雙指標法，將它們合併成一個新的降序陣列。
        vector merged;
        merged.reserve(U.size() + (i - start_i));
        int p1 = 0, p2 = start_i;
        
        while (p1 < U.size() && p2 < i) {
            if (U[p1] >= items[p2].b) {
                merged.push_back(U[p1++]);
            } else {
                merged.push_back(items[p2++].b);
            }
        }
        // 把剩下的元素塞進去
        while (p1 < U.size()) merged.push_back(U[p1++]);
        while (p2 < i) merged.push_back(items[p2++].b);

        U = move(merged); // 更新 U 為合併後的結果
    }

    // 當所有真實物品都處理完後，U 裡面可能還有很多物品。
    // 我們必須繼續把它們兩兩合併，直到達到背包的最終限制層級 M。
    if (curr_level != -1) {
        while (curr_level < m && U.size() > 1) {
            curr_level++;
            vector next_U;
            next_U.reserve((U.size() + 1) / 2);
            for (size_t j = 0; j < U.size(); j += 2) {
                if (j + 1 < U.size()) {
                    next_U.push_back(U[j] + U[j+1]);
                } else {
                    next_U.push_back(U[j]);
                }
            }
            U = move(next_U);
        }
    }

    // 最終輸出結果
    if (U.empty()) {
        // 如果連一個合法的物品都沒有
        printf("0\n");
    } else {
        // 因為背包容量是 2^M，在層級 M 我們「最多只能挑選 1 個」物品。
        // 而 U 陣列是降序排列的，所以 U[0] 就是我們能湊出的最大總價值。
        printf("%lld\n", U[0]);
    }

    return 0;
}

附圖