P3087 [USACO13NOV]Farmer John has no Large Brown Cow S

正解像是康托展开之类的？但是蒟蒻不会，所以用了一堆 STL。

对于每一列的字符串，按照字典序给它们编号。这样每一行的形容词串就变成了一堆数字。

设共有 \(s\) 列，第 \(i\) 列共有 \(b_i\) 个不同的形容词，那么实际上每一行就是一个“第 \(i\) 位是 \(b_i\) 进制”的数。设第 \(j\) 行的第 \(k\) 个形容词再该列的排名为 \(a_{j,k}\)，然后这一行的形容词就可以用数字 \(\sum\limits_{k=1}^{s}(a_{j,k} \times \prod\limits_{p=k+1}^{s}b_p)\) 表示。

例如样例，large brown noisy转化为0 0 0，small white silent转化为1 2 1。然后按照进制转化的方法，前者转化为 \(0\)，后者转化为 \(1 \times 6 + 2 \times 2 + 1 \times 1 = 11\)。

然后对于每一行的形容词都可以转化为一个数字，我们将这些数字称为“关键数字”。将关键数字排序后得到数组 \(key\)。我们要求的其实是第 \(k\) 个"非关键数字"，而“非关键数字”个数是 \(O(\prod b_i)\) 级别的，直接枚举妥妥的 T 飞。而“关键数字”只有 100 个，所以考虑计算答案在哪两个“关键数字”之间。

这个是简单的。从小到大找区间 \((key_i , key_{i+1})\)，若 \(k \leq key_{i+1} - key_i\) 说明答案为 \(ans = key_i + k - 1\)，直接输出 \(ans\) 对应的形容词串即可。否则 \(k \gets k-(key_{i+1}-key_i)\)，然后进入下一个区间。

具体的复杂度懒得算了。这题的数据范围极小，\(n \leq 100\)，形容词个数 \(\leq 30\)，所以不论怎么玩 STL 都炸不了。事实上最大点仅 4ms。

我的代码里面使用了大量的 STL，而且还是修修补补才写出来的。做这种毒瘤前还是先思考完整再写，不然不知道写出来一坨什么玩意（

#include<map>
#include<set>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

int n,k,sz;
map<string,int>adj[110];	// 每一列形容词的编号
map<int,string>rev[110];	// adj[rev[S]] = S
set<string>qwq[110];		// 每一列形容词
vector<string>awa[110];		// 每一行形容词
long long bit[110];			// 每一列进率
vector<long long>key;		// 关键数字 

long long encode(vector<string>v){
	long long ret=0;
	for(int i=0;i<sz;i++) ret=ret*bit[i+1]+(adj[i+1][v[i]]-1);
	return ret;
}
vector<string>decode(long long v){
	vector<string>ret;
	for(int i=sz;i>=1;i--)
		ret.push_back(rev[i][v%bit[i]]),v/=bit[i];
	reverse(ret.begin(),ret.end());
	return ret;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		string tmp;
		cin>>tmp; cin>>tmp; cin>>tmp; cin>>tmp;
	//   Farmer     John       has       no
		for(int j=1;;j++){
			cin>>tmp;
			if(tmp=="cow.") break;
			qwq[j].insert(tmp),sz=j;
			awa[i].push_back(tmp);
		}
	}
	
	long long R=1;
	bit[0]=1;
	for(int i=1;i<=sz;i++){
		int cnt=0;
		auto it=qwq[i].begin();
		for(;it!=qwq[i].end();it++) adj[i][*it]=++cnt,rev[i][cnt-1]=*it;
		R*=cnt,bit[i]=cnt;
	}
	
	for(int i=1;i<=n;i++) key.push_back(encode(awa[i]));
	sort(key.begin(),key.end()),key.push_back(R);
	
	long long cur=0,res=k;
	for(auto it=key.begin();it!=key.end();it++){
		long long now=*it;
		if(res<=now-cur){
			vector<string>ans=decode(res+cur-1);
			for(auto it0=ans.begin();it0!=ans.end();it0++) cout<<*it0<<' ';
			break;
		}else
			res-=(now-cur),cur=now+1;
	}
	return 0;
}