Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## 模拟题，注意计数的时候，应该先数左子树的种类数。

Posted by sunl449554866 at 2014-08-19 01:46:33 on Problem 1095
#include<iostream>
#include<vector>

std::vector<size_t> kind_node;
std::vector<size_t> kind_node_left;

class Tree
{
public:
Tree(){};
~Tree(){};
size_t order_num;
};

std::istream& operator>>(std::istream& is,Tree& tree)
{
is >> tree.order_num;
return is;
}

int main()
{
void Compute_kind_node(std::vector<size_t>&, std::vector<size_t>&);
void Print(const int&, const size_t&);
Tree instance;
int nodes;
size_t kinds;
Compute_kind_node(kind_node,kind_node_left);
while (std::cin>>instance, instance.order_num != 0){
instance.order_num++;
nodes = 0;
while (instance.order_num > kind_node_left[++nodes]);
kinds = instance.order_num - kind_node_left[nodes - 1];
Print(nodes,kinds);
std::cout << std::endl;
}
}

void Compute_kind_node(std::vector<size_t>& kind_node, std::vector<size_t>& kind_node_left)
{
kind_node.push_back(1);
kind_node.push_back(1);
for (int i = 2; i <= 18; ++i){
kind_node.push_back(0);
for (int j = 0; j <= i - 1; ++j)
kind_node[i] += kind_node[j] * kind_node[i - j - 1];
}
for (int i = 0; i <= 18; ++i){
kind_node_left.push_back(0);
for (int j = 0; j <= i; ++j)
kind_node_left[i] += kind_node[j];
}
}

void Print(const int& nodes, const size_t& kinds)
{
if (nodes){
int nodes_left = 0;
int nodes_right = nodes - 1;
size_t kinds_left;
size_t kinds_right;
size_t sum = kind_node[nodes_left]*kind_node[nodes_right];
while (sum < kinds){
sum += kind_node[++nodes_left] * kind_node[--nodes_right];
}
sum -= kind_node[nodes_left] * kind_node[nodes_right];
sum = kinds - sum;
kinds_left = sum % kind_node[nodes_right] ?
sum / kind_node[nodes_right] + 1 : sum / kind_node[nodes_right];
kinds_right = sum % kind_node[nodes_right] ?
sum % kind_node[nodes_right] : kind_node[nodes_right];
if (nodes_left != 0){
std::cout << "(";
Print(nodes_left, kinds_left);
std::cout << ")";
}
std::cout << "X";
if (nodes_right != 0){
std::cout << "(";
Print(nodes_right, kinds_right);
std::cout << ")";
}

}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator