C: Ceiling Function
問題
n個のk頂点-二分探索木が与えられる。
二分探索木は挿入する値とその順番によって与えられる(回転などはしない)。
何種類の形があるか数えよ。
制約
1 <= n <= 50
1 <= k <= 20
各木の要素は互いに異なる値である。
解法
根付き木の同型性判定問題。
サイズが小さいので、木を陽に持ち全てのペアに対して、同時に探索を行うことで判定するのが簡単。
より大きなサイズの問題について考えると、木の同型性判定はハッシュを用いる方法がある。
コード
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } struct Tree { int v; Tree *l, *r; Tree(int v_=0) { v = v_; l = r = NULL; } }; Tree * insert(Tree *x, int v) { if (!x) return new Tree(v); if (v < x->v) { x->l = insert(x->l, v); } else { x->r = insert(x->r, v); } return x; } bool same(Tree *x, Tree *y) { if (!x && !y) return true; if (!x || !y) return false; return same(x->l, y->l) && same(x->r, y->r); } int N, K; Tree *tree[55]; bool use[55]; int main() { scanf("%d%d", &N, &K); REP (i, N) { REP (j, K) { int v; scanf("%d", &v); tree[i] = insert(tree[i], v); } } int ans = 0; REP (i, N) { if (use[i]) continue; ans++; for (int j=i+1; j<N; j++) { if (same(tree[i], tree[j])) { use[j] = true; } } } printf("%d\n", ans); return 0; }