4610: [Wf2016]Ceiling Functi
题目连接：
http://www.lydsy.com/JudgeOnline/problem.php?id=4610
Description
给出n个长度为k的数列，每个数列模拟堆的操作，问有多少种形态不同的堆。
Input
第一行包含两个数n(1<n<=50)代表堆的数量，k(1<=k<=20)代表每个堆的插入序列长度。
接下来n行每行包含k个数代表每个堆的插入序列。
Output
输出不同堆的形态数。
Sample Input
12 7
291388 78619 945367 867244 966006 445425 648278
593908 292543 111985 66151 846350 93727 765366
790325 950781 514834 937591 3749 922704 723259
788203 256144 944013 558440 591881 795482 173898
324286 386153 624883 475996 120001 18438 300906
819238 889730 825701 320745 611539 492070 410382
528593 425310 458894 528505 488435 192846 682984
564357 635943 41024 396434 286305 274829 196124
851238 206925 126110 537002 246374 859835 936366
729469 815045 965455 104000 364877 151376 759750
670021 748323 53559 609778 106547 151277 766524
561059 895615 951857 781815 378082 703670 620446
Sample Output
12
Hint
题意
题解：
数据范围很小，模拟一下，然后按照dfs的顺序hash一下，扔到一个set里面看看就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
set<string> S;
struct node{
int l,r,x;
int flag;
}a[maxn];
int cnt;
void add(int x,int v)
{
if(a[x].flag==0){
a[x].x=v;
a[x].flag=1;
return;
}
if(v<=a[x].x)
{
if(a[x].l==0)
a[x].l=++cnt;
add(a[x].l,v);
}
else
{
if(a[x].r==0)
a[x].r=++cnt;
add(a[x].r,v);
}
}
string ans;
void get(int x)
{
if(a[x].flag==0)return;
if(a[x].l!=0)ans+="L",get(a[x].l);
if(a[x].r!=0)ans+="R",get(a[x].r);
ans+="D";
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
memset(a,0,sizeof(a));
ans="";cnt=0;
for(int j=0;j<k;j++)
{
int x;scanf("%d",&x);
add(0,x);
}
get(0);
S.insert(ans);
}
cout<<S.size()<<endl;
}