Submission #1308630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308630		orzorzorz	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	585 ms	21844 KiB

snake_escaping

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 全域陣列，大小為 2^20 (每個約 4MB)
// A: 儲存原始毒性值
// dp_sub: 儲存子集和 (Subset Sum)
// dp_super: 儲存超集和 (Superset Sum)
int A[1 << 20];
int dp_sub[1 << 20];
int dp_super[1 << 20];

int main() {
    // 優化 I/O 操作速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L, Q;
    if (!(cin >> L >> Q)) return 0;

    string S;
    cin >> S;

    int N = 1 << L;
    
    // 初始化陣列
    for (int i = 0; i < N; ++i) {
        A[i] = S[i] - '0';
        dp_sub[i] = A[i];
        dp_super[i] = A[i];
    }

    // 1. 建構 SOS DP (子集和)
    // dp_sub[mask] = 所有 i 是 mask 的子集的 A[i] 之和
    for (int i = 0; i < L; ++i) {
        for (int mask = 0; mask < N; ++mask) {
            if (mask & (1 << i)) {
                dp_sub[mask] += dp_sub[mask ^ (1 << i)];
            }
        }
    }

    // 2. 建構 SOS DP (超集和)
    // dp_super[mask] = 所有 i 是 mask 的超集的 A[i] 之和
    for (int i = 0; i < L; ++i) {
        // 從大到小枚舉，或者直接檢查第 i 位是否為 0
        for (int mask = N - 1; mask >= 0; --mask) {
            if (!(mask & (1 << i))) {
                dp_super[mask] += dp_super[mask | (1 << i)];
            }
        }
    }

    char T[25]; 
    for (int q = 0; q < Q; ++q) {
        cin >> T;
        
        int mask0 = 0; // 必須是 '0' 的位置集合 (Set A)
        int mask1 = 0; // 必須是 '1' 的位置集合 (Set B)
        int maskQ = 0; // 是 '?' 的位置集合 (Set C)
        
        int c0 = 0, cQ = 0; 
        
        // 解析詢問字串 T
        // 注意：題目通常定義 T[0] 對應最高位 (2^(L-1)) 或最低位，需根據題目調整
        // 這裡假設 T[0] 對應最高位 2^(L-1)
        for (int i = 0; i < L; ++i) {
            int bit = L - 1 - i;
            if (T[i] == '0') {
                mask0 |= (1 << bit);
                c0++;
            } else if (T[i] == '1') {
                mask1 |= (1 << bit);
            } else {
                maskQ |= (1 << bit);
                cQ++;
            }
        }

        int ans = 0;

        // 策略 1: '?' 很少 -> 暴力枚舉 '?'
        if (cQ <= 6) {
            // 枚舉 maskQ 的所有子遮罩 (submask)
            for (int s = maskQ; ; s = (s - 1) & maskQ) {
                // 索引值 = 固定的 1 (mask1) + 當前 '?' 變成的 1 (s)
                ans += A[mask1 | s];
                if (s == 0) break;
            }
        } 
        // 策略 2: '0' 很少 -> 對 '0' 使用排容原理 (搭配超集和)
        else if (c0 <= 6) {
            // 基礎：mask1 必須是 1。maskQ 隨意。mask0 "應該" 是 0。
            // dp_super[mask1] 給出 mask1 位元為 1 的所有和 (此時 mask0 可能是 0 或 1)。
            // 我們需要扣除那些 mask0 中某些位元變成 1 的情況。
            for (int s = mask0; ; s = (s - 1) & mask0) {
                int val = dp_super[mask1 | s];
                // 如果 s 中有奇數個 1，則減去；偶數個則加上 (排容原理)
                if (__builtin_popcount(s) & 1) ans -= val;
                else ans += val;
                
                if (s == 0) break;
            }
        } 
        // 策略 3: '1' 很少 -> 對 '1' 使用排容原理 (搭配子集和)
        else { // 隱含條件：c1 <= 6
            // 基礎：mask0 必須是 0。maskQ 隨意。mask1 "應該" 是 1。
            // dp_sub[mask1 | maskQ] 給出 mask0 位元為 0 的所有和 (此時 mask1 可能是 0 或 1)。
            // 我們需要扣除那些 mask1 中某些位元變成 0 的情況。
            for (int s = mask1; ; s = (s - 1) & mask1) {
                // 我們將 s 中的位元關掉 (強制變為 0)
                // 查詢的 mask 變為 (mask1 去掉 s) | maskQ
                int val = dp_sub[(mask1 ^ s) | maskQ];
                
                if (__builtin_popcount(s) & 1) ans -= val;
                else ans += val;
                
                if (s == 0) break;
            }
        }
        
        cout << ans << "\n";
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25