记录编号	274847	评测结果	AAAAAAAAAA
题目名称	[USACO Nov]FJ没有大的棕色的牛	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-06-29 21:55:11	内存使用	0.32 MiB

#include<iostream>
#include<vector>
#include<map> 
#include<sstream>
#include<cstdio>
using namespace std;
const int CUTLEN=19,MAXA=30+10,MAXN=100+1;
int n,k,num,cnt[MAXA],mult[MAXA];
vector<string> a;
map<string,int> ht[MAXN];
struct NODE{
	string s;
	//vector<NODE*> ch;
	map<string,NODE*> mm;
	int sz;
	NODE(string& str){sz=0,s=str,mm.clear();}
	NODE(){sz=0;}
	void add(vector<string>& t,int idx=0){
		sz++;
		if(idx>=t.size()) return;
		string& str=t[idx];
		if(!mm.count(str)) mm[str]=new NODE(str);
		mm[str]->add(t,idx+1);
	}
	void build(int pos){
		if(pos>=num) return;
		sz=cnt[pos];
	}
	void sol(int th,int pos=0){
		if(pos) cout<<s<<" ";
		if(pos>=num) return;
		NODE* o;
		map<string,int>::iterator it;
		for(it=ht[pos+1].begin();it!=ht[pos+1].end();it++) {
			if(!mm.count(it->first)) {
				if(th>mult[pos+1]) th-=mult[pos+1];
				else {
					o=new NODE;
					o->s=it->first;
					o->build(pos+1);
					break;
				}
			}
			else {
				o=mm[it->first];
				if(th>mult[pos+1]-o->sz) th-=mult[pos+1]-o->sz;
				else break;
			}
		}
		/*int i;
		for(i=0;i<ch.size();i++) if(th>mult[pos+1]-ch[i]->sz) th-=(mult[pos+1]-ch[i]->sz)
		else break;*/
		o->sol(th,pos+1);
	}
}root;
int main(){
	freopen("nocow.in","r",stdin);
	freopen("nocow.out","w",stdout); 
	cin>>n>>k;
	a.clear();
	string s;
	cin.get();
	for(int i=1;i<=n;i++) {
		getline(cin,s);
		stringstream ss(s.substr(CUTLEN));
		vector<string> t; 
		while(ss>>s&&s!="cow.") {
			t.push_back(s);
			if(!ht[t.size()].count(s)) cnt[t.size()]+=(ht[t.size()][s]=1);
		}
		root.add(t);
		if(!num) num=t.size();   
	}
	mult[num]=1;
	for(int i=num-1;i>=0;i--) mult[i]=mult[i+1]*cnt[i+1];
	root.sol(k,0);
	//root.dfs();
}