AOJ : 1037 - Midnight Teatime

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1037
日本語の問題文なので, 説明省略.

アルゴリズム

全探索で解けます.
ツリーを表す文字列を前方からパースしつつ, 再帰で全パターン調べましょう.
(もちろん, ツリー構造作ってから, 再帰しても大丈夫です)

プログラム

int n,idx,leaf[10];
string s;

map<int,int> solve(void){
  map<int,int> res;
  if(isdigit(s[idx])){
    res[ leaf[s[idx++]-'1'] ]++;
    return res;
  }

  idx++;
  map<int,int> left = solve();
  idx++;
  map<int,int> right = solve();
  idx++;

  for(map<int,int>::iterator i=left.begin();i!=left.end();i++){
    for(map<int,int>::iterator j=right.begin();j!=right.end();j++){
      int lbit = i->first;
      int rbit = j->first;
      res[lbit & rbit] += i->second * j->second; //積集合
      res[lbit | rbit] += i->second * j->second; //和集合
      res[lbit ^ rbit] += i->second * j->second; //対称差
    }
  }

  return res;
}

int main(void){
  while(getline(cin,s),s!="END"){
    cin>>n;
    for(int i=0;i<n;i++){
      leaf[i] = 0;

      //a,b,c,dをビット管理
      for(int j=0;j<4;j++){
        int x;
        cin>>x;
        if(x) leaf[i] |= 1<<j;
      }
    }

    idx = 0;
    map<int,int> rst = solve();
    cout<<rst[15]<<endl;

    getchar(); //getline使用前に改行とばし
  }

  return 0;
}