P3087 [USACO13NOV]Farmer John has no Large Brown Cow S(进制)

admin管理员组

文章数量:815114

P3087 [USACO13NOV]Farmer John has no Large Brown Cow S(进制)

P3087 [USACO13NOV]Farmer John has no Large Brown Cow S(进制)

就是进制转换。

先预处理每种形容词的个数，排序。

然后求出 n n n个牛当前的排名。

然后对这 n n n头牛排序。

更新实际的 k k k。

然后再倒着从左往右求出每个进制位上的数字即可。

#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;            //第一位代表的数字应该是1adj_by_pos[adj_num + 1].push_back("temp"); //1和1相乘是1，所以要push一个元素进去，这样子size就是1for (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];}return 0;
}

本文标签： P3087 USACO13NOVFarmer John has no Large Brown Cow S(进制)