AOJ 1037 Midnight Teatime

問題文, 制約

日本語なので省略

解法

構文解析＋全探索

まず、入力で与えられる文字列から木を構築する.
その木の内部節点にナンバリングする.

後は、内部節点の個数分(多くても8個)だけ、'A'を0, 'O'を1, 'X'を2として
全通り(例えば、内部節点が3個なら、000,001,….,222)試しカウントしていく.

コード

#include <bits/stdc++.h>

using namespace std;

int Tree[1<<12],m;
map<int,int> mp;
vector<int> order;
string::iterator it;

vector<int> getOrder(int x,int m){
    vector<int> res;
    while(x > 0){
        res.push_back(x%3);
        x /= 3;
    }
    while((int)res.size() != m){
        res.push_back(0);
    }
    return res;
}

int getBit(int v,vector<int> &bit){
    if(Tree[v] != -1){
        return bit[Tree[v]];
    }
    int S = -1;
    int l = getBit(2*v+1, bit);
    int r = getBit(2*v+2, bit);
    switch(order[mp[v]]){
    case 0:
        S = l & r;
        break;
    case 1:
        S = l | r;
        break;
    case 2:
        S = (l | r) - (l & r);
        break;
    };
    return S;
}

bool check(vector<int> &bit){
    return (getBit(0,bit) == (1<<4)-1);
}

int makeTree(int v){
    if(*it == '('){
        ++it;
        char cl = *it;
        int l = makeTree(2*v+1);
        if(isdigit(cl)){
            Tree[2*v+1] = l;
        }
        ++it;
        char cr = *it;
        int r = makeTree(2*v+2);
        if(isdigit(cr)){
            Tree[2*v+2] = r;
        }
        ++it;
    }else if(isdigit(*it)){
        int num = ((*it - '0') - 1);
        ++it;
        return num;
    }
    return -1;
}

void dfs(int v){
    if(Tree[v] == -1){
        mp[v] = m++;
        dfs(2*v+1);
        dfs(2*v+2);
    }
}

int main(){
    string s;
    while(getline(cin,s), s != "END"){
        int N,x;
        cin >> N;
        vector<int> bit(N, 0);
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < 4 ; j++){
                cin >> x;
                if(x == 1) bit[i] |= 1<<j;
            }
        }
        int res = 0;
        memset(Tree,-1,sizeof(Tree));
        it = s.begin();
        makeTree(0); m = 0; dfs(0);
        int n = pow(3., m);
        for(int i = 0 ; i < n ; i++){
            order = getOrder(i, m);
            if(check(bit)) res++;
        }
        cout << res << endl;
        cin.ignore();
    }
    return 0;
}