洛谷P3087，[USACO13NOV]Farmer John has no Large Brown Cow S 题解

update：2022/4/17 更正了博客地址 [题目链接](https://www.luogu.com.cn/problem/P3087) [博客中观看体验更好](https://ttzytt.com/2021/09/P3087/) 前言：这篇题解写的可能比较啰嗦，主要时是因为我把所有思考的过程都写下来了，所以如果你已经有了基本的思路，或者是希望找一篇简洁的题解，就可以跳过这篇题解了。 # 1：理解题意 总共有 $cow$ 头牛，$type$ 类形容词，有 $num_i$ 个第 $i$ 类形容词，第 $i$ 类的第 $j$ 种形容词是 $adj_{i,j}$ ，每头牛都需要有这 $type$ 类形容词按照顺序来修饰。现在告诉你要删除这 $cow$ 头牛中的 $n$ 头，问你在这剩下的 $cow-n$ 头牛中，按照字典序排序，排在第 $k$ 位的牛是哪一头? # 2：分析和转化问题 ## 2.1：和数字系统的关联 单看这样的描述可能有些抽象，现在我们来看一下样例是怎么样的，再在样例的基础上思考应该怎么解决这道题。 在样例中 $n=3$，$k = 7$。$adj_{i,j}$的值如下 | $adj_{i,j}$ | $j=1$ | $j=2$ | $j=3$ | | :-------------------- | :------ | :------- | :-------- | | $i=1$（第一类形容词） | "large" | "small" | N/A | | $i=2$（第二类形容词） | "brown" | "white" | "spotted" | | $i=3$（第三类形容词） | "noisy" | "silent" | N/A | 因为样例中让我们求的是按照字典序排在第7的牛，我们可以思考一下以字典序为关键字进行排序的过程是什么样的。 举个例子：有两个字符串"abc"和字符串"cde"需要进行字典序排序，首先我们应该比较在第一位的字符"a"和"c"的字典序，再比较第二位"b"和"c"的字典序，最后才是第三位的字符。 从这个过程中我们可以发现每一位字符对于字符串整体字典序的影响是不一样的，其中第一位的影响最大，最后一位最小。因此我们就可以说他们对于整个字符串的字典序的影响的“权值”不同。如果我们按照字典序给不同的字符串从小到大排序，对于一个字符串，不管从第二个字符到最后一个字符的字典序有多小，如果第一个字符的字典序很大，那么它也会排在很后面 再观察这道题目中让我们求解的问题，我们可以发现，第1类形容词比如"large"对于整串字符的影响是最大的，其次是第二类，比如"brown"，最后才是第三类。 分析到这里，相信你已经体会到这个问题和数字系统的相关性了。 那就是我们在比较数字时，采用的方法也是从高位到低位进行比较 比如有这样一个 $10$ 进制数字 $(123456789)_{10}$ 数字 $1$ 代表的值是 $100000000$ 它代表的值是所有数字中最大的（1是第一位） 数字 $2$ 代表的值是 $20000000$ 它代表的值是第二大的（2是第二位） 数字 $x$ 在第 $i$ 位代表的值就是 $10^{i-1}\times x$，整个 $10$ 进制数代表的值就每一位数字代表的值的累加 把整个规则推广到 $k$ 进制，那么数字 $x$ 在第 $i$ 位代表的值就是 $k^{i-1}\times x$ ## 2.2：解决简化过的问题 那么问题就来了，不管是我们刚刚讨论的 $10$ 进制还是 $k$ 进制，它们的机制都是 “逢 $k$ 就进 $1$”，因此第 $i+1$ 位的 “数字 $1$” 在十进制中代表的值一定是第 $i$ 位的 “数字 $1$” 代表的值的 $k$ 倍。而在我们这个问题中，每一类形容词的数量是不一定的。 我们可以先尝试解决每类形容词数量一定的情况，设每类形容词的数量都是 $k$ ，首先我们要对每类形容词进行字典序排序，把结果存在 `rank[i][j]`中，其中 $i$ 代表形容词类型，$j$ 代表排名。 这一步的目的是把字符串转化成数字，方便后续的计算。（把每个形容词映射到数字系统中的 “第 $i$ 位的数字 $j$ ”，但是需要注意的一点是，形容词的类数越小，对整体字典序影响越大，数字的位数越小，对整体的值的影响越小） 因为我们已经完成了形容词到数字的映射，所以下面要做的就等于“把 $10$ 进制转换到 $k$ 进制”，再把得到的数字转换回对应的字符串 这样的例子可能有些抽象，下面我们来模拟一遍这个过程 我们规定第一类形容词有以下两个 {"a","b"}, 第二类形容词也有以下两个{"c","d"}, 第三类是{"e","f"}。 那么我们可以求出以下的`rank`数组 （因为方便计算，所以排名从0开始） | $rank_{i,j}$ | $j=0$ | $j=1$ | | :-------------------- | :---- | :---- | | $i=1$（第一类形容词） | "a" | "b" | | $i=2$（第二类形容词） | "c" | "d" | | $i=3$（第三类形容词） | "e" | "f" | 如果我们想求字典序排在第 $3$ 位的牛，那么我们需要先求出 $3$ 的二进制数，也就是 $(011)_2$。然后把这个数字倒过来，变成 $(110)_{2反}$（形容词的类数越小，对整体字典序影响越大，数字的位数越小，对整体的值的影响越小），最后再把 $(110)_{2反}$ 映射回对应的字符串（第几位对应第几类），最后的答案也就是 "a, d, f" ## 2.3：解决原问题 在解决刚刚简化过的问题的过程中，我们把每类形容词的类映射到了数字系统的 “第几位数”，把它们的排名 $j$ 映射到了数字系统中的数字 $j$，而每类形容词的数量就成了这个数字系统的进制数。 我们可以发现，解决原问题的关键就在于进制，在刚刚简化过的问题中，数字系统中每一位的进制是一样的，并且每一类形容词的数量也是一定的，那么再解决当前问题时，每一类的形容词数量是不一定的，所以相应的，每一位的进制也要有所改变。 回到题目给的样例，每类形容词的数量是 $num_1 = 2$, $num_2 = 3$, $num_3 = 2$ 而第三类的形容词被我们映射到了数字系统中的第一位数字，第二类是第二位，同样的，第一类就是第三位 因此我们可以规定，在第一位的时候，这个数字系统是二进制的，在第二位的时候，这个数字系统是三进制的，第三位也是二进制。 虽然我们可以做到用这样的 "$2,3,2$" 进制来描述每一种牛，但是在解决这道题的时候，我们还需要把十进制转换成这样的 "$2,3,2$" 进制。 大家肯定对十进制转二进制这样的问题非常熟悉，比如要把一个十进制数 $a$ 转换成 $x$ 位的二进制数 $b$ ，要做的就是从 $b$ 的最高位 $x$ 开始，每次都进行 $\lfloor a \div （b的这一位在十进制中代表的值） \rfloor$ 的操作，然后再计算 $a = a \bmod （b的这一位在十进制中代表的值）$ 写成程序的话，就是这样的 ~~~cpp //k是十进制数 //weight_in_pos[i]是第i位（从最高位开始计，和我们平常用的方法相反）在十进制中代表的值 //i是当前位（从最高位开始计，和我们平常用的方法相反） for (int i = 1; i <= adj_num; i++) { cout << adj_by_pos[i][(k) / weight_in_pos[i]] << " "; k %= weight_in_pos[i]; } ~~~ 所以呢，对于 "$2,3,2$" 这样的进制，我们只需要提前计算好他们每一位在十进制中代表的值就可以把十进制转换成这样的进制了。 （每一位在十进制中代表的值的意思就是 在原进制系统中，如果这一位是 $1$ ，其他位都是 $0$ ，转换成 $10$ 进制之后的值） 那么这样的进制的每一位在十进制中代表的值如何计算呢？ 不管是在几进制的系统里，只要两个数的进制系统相同，那么一个 位数更多的数 所代表的值一定比位数更少的那个要大。 所以我们可以这样计算第 $i$ 位在十进制中所代表的值，就是第 $i-1$ 位数字在十进制中代表的值再乘上第 $i-1$ 位上能表示的最大的数字 $+ 1$（确保位数更多的数一定比位数更少的大），并且我们可以发现最大的数字 $+ 1$ 刚好就是这一位的进制。（比如 $2$ 进制最大的数是 $1$ ） 有了这个结论就可以递推的求解每一位在十进制中代表的值，我们可以把答案存在 `weight_in_pos[i]` 数组中（第 $i$ 位代表的值），并且把第一位代表的值初始化为 $1$ 在样例的 "$2,3,2$" 进制中，第一位在十进制中代表的值被初始化为 $1$，第二位的 weight_in_pos 值就是 $1\times 2 = 2$，第三位就是 $2\times 3 = 6$， 至此，我们已经能计算出所有牛中排在第 $k$ 个的牛了，但是题目问的是在这剩下的 $cow-n$ 头牛中，按照字典序排序，排在第 $k$ 位的牛是哪一头。 这个小问题的求解就比较简单了，我们可以把 $k$ 转化成在所有牛中的排名，而不是剩下的牛的排名，我们可以先计算出要删除的那 $n$ 头牛在所有牛中的排名，如果这 $n$ 头牛中有牛的排名比 $k$ 小，或是等于 $k$ ，那么就需要把 $k$ 加 $1$。（相当于排名前 $k$ 的这些牛中有一些是不能选取的，而我们要选出 $k$ 头，所以要加上删去的 $n$ 头牛中排名比 $k$ 小的） # 代码和细节 细节都有注释 ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long int n, k; int adj_num = 0; vector<string> str[105]; //str[i]表示用于修饰第i头牛的形容词 vector<string> adj_by_pos[35]; //adj_by_pos[i]表示所有在位置i出现的形容词 set<string> is_appear[35]; //is_appear[i]用于判断在位置i上，某个形容词是否出现 int weight_in_pos[35]; //每一位代表的值（按照字典序排在第几） map<string, int> rank_in_pos[35]; //rank_in_pos[i][j]代表在位置i上，字符串j按照字典序排序，排在第几 int cow_rank[105]; //fj没有的牛的排名 bool debug = false; //调试开关，可以打开去体会一下解题的过程 void mapping() //对每类形容词进行字典序排序，把结果存在 rank[i][j]中，其中 i 代表形容词类型，j 代表排名 { //注意这里的排名从0开始（这是把单词映射到数字上，数字是从0开始的） for (int i = 1; i <= adj_num; i++) { int rank = 0; for (auto j : adj_by_pos[i]) //c++11的新特性，意思是用j遍历所有adj_by_pos[i]的元素 { rank_in_pos[i][j] = rank; if (debug) cout << j << " rank = " << rank << " i = " << i << endl; rank++; } } } int get_pos(int cow_id) { int ans = 0; for (int i = 1; i <= adj_num; i++) { ans += weight_in_pos[i] * (rank_in_pos[i][str[cow_id][i - 1]]); } return ans + 1; //答案可能是0，但是排位应该从1开始 } int main() { ios::sync_with_stdio(false); cin >> n >> k; string temp_str; for (int i = 1; i <= n; i++) { cin >> temp_str; while (temp_str != "no") { cin >> temp_str; } int adj_pos = 1; while (1) { cin >> temp_str; if (temp_str == "cow.") { break; } str[i].push_back(temp_str); if (!is_appear[adj_pos].count(temp_str)) //还没有出现过，这里是去重操作 { adj_by_pos[adj_pos].push_back(temp_str); is_appear[adj_pos].insert(temp_str); } if (i == 1) { adj_num++; //计算形容词的种类数 } adj_pos++; } } for (int i = 1; i <= adj_num; i++) { sort(adj_by_pos[i].begin(), adj_by_pos[i].end()); //对每个类型的形容词进行排序 } weight_in_pos[adj_num + 1] = 1; //第一位代表的数字应该是1 adj_by_pos[adj_num + 1].push_back("temp"); //1和1相乘是1，所以要push一个元素进去，这样子size就是1 for (int i = adj_num; i >= 1; i--) //计算每一位在十进制中代表的值（这里的位的计算方法和平时的方法是反的） { //这是因为本题中的形容词类型和数字系统的 “位” 是相反的 if (debug) cout << "i" << i << endl; weight_in_pos[i] = weight_in_pos[i + 1] * adj_by_pos[i + 1].size(); } mapping(); for (int i = 1; i <= n; i++) { cow_rank[i] = get_pos(i); //计算出要删除的n头牛的整体排名 if (debug) cout << "cowrkw " << i << " = " << cow_rank[i] << endl; } sort(cow_rank + 1, cow_rank + n + 1); //按照每种牛的排名进行排序 for (int i = 1; i <= n; i++) { if (cow_rank[i] <= k) { k++; } else { break; } } k--; //k原本代表的是排在第几的牛，但是我们已经把牛的排名转化成数字了， //排名最小的牛的数字是0而不是1，所以这里要减1 if (debug) cout << "new k" << k << endl; for (int i = 1; i <= adj_num; i++) { cout << adj_by_pos[i][(k) / weight_in_pos[i]] << " "; if (debug) cout << "i " << i << " (k) / weight_in_pos[i] " << (k) / weight_in_pos[i] << endl; k %= weight_in_pos[i]; } system("pause"); } ``` 题解就到这里了，如果你发现题解有问题，或是有看不懂的地方，都欢迎私信我或者是在评论区里讲，如果你觉得对你有帮助就点个赞吧，谢谢。