题解：AT_abc415_c [ABC415C] Mixture

· · 题解

每次加一种药品后混合状态需安全。用状态掩码表示药品集合。

先标记危险状态，再从空集出发，逐层尝试添加未加入的药品，若新状态安全则标记可达，最终判断全集是否可达即可。

看不懂？没关系，插入代码！


#include <iostream>
#include <string>
using namespace std;
// 函数功能：判断N种药品能否按规则全部混合
// 参数：N为药品数量，S为长度2^N-1的01串，标识各状态是否危险
bool s(int N, string S) {
    // f是全集掩码（二进制N位全1），表示所有药品都混合的状态
    int f= (1 << N) - 1;
    // is数组：is[mask]为true表示状态mask危险（S的第mask位是'1'）
    bool is[f + 1]={false} ;
    // 初始化危险状态：S的第i-1位对应状态i（i从1到f）
    for (int i = 1; i <= f; i++) {
        is[i] = (S[i-1] == '1');
    }
    // 若全集状态危险，直接无法混合所有药品，返回false
    if (is[f]) {
        return false;
    }
    // r数组：r[mask]为true表示状态mask可通过合法操作达到
    bool r[f+1]={false};
    r[0] = true; // 初始状态：空瓶子（mask=0）是可达的
    // 遍历所有可能的状态mask
    for (int mask = 0; mask <= f; mask++) {
        if (!r[mask]) continue; // 跳过不可达的状态
        // 尝试添加第k种药品（k从0开始对应药品1~N）
        for (int k = 0; k < N; ++k) {
            // 检查mask是否未包含第k种药品（二进制第k位为0）
            if (!(mask & (1 << k))) {
                // 加入第k种药品后的新状态
                int neww = mask | (1 << k);
                // 若新状态安全，则标记为可达
                if (!is[neww]) {
                    r[neww] = true;
                }
            }
        }
    }
    // 返回全集状态是否可达（即能否混合所有药品）
    return r[f];
}
int main() {
    int T;
    cin >> T; // 读取测试用例数量
    while (T--) { // 处理每个测试用例
        int N;
        string S;
        cin >> N >> S; // 读取药品数量N和状态字符串S
        // 根据函数返回值输出Yes/No
        if(s(N, S)==true) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}
//拔出代码，这下懂了吧？