题目描述
给定n组两头牛之间的出生关系,a在b的前或后12年中的 num 年出生,这里的num 需要用前面给定的关系中,a,和 b 的生肖顺序和出生前后顺序计算。
碎碎念
在听了y总的讲解后, 从小算年龄的脑袋就不太灵光的 本菜鸡对于x和y的关系还是不太清楚,y总列了一个等式, 有点抽象 尤其中间还有过笔误 ,不理解为什么可以把年龄和生肖序号作差,思索许久,看到了这个大佬的题解 oopstls 的题解 ,菜鸡顿悟!特把自己的理解分享如下:
算法一:三哈希表版
- 这个题的关键在于 对于a和b,当a和b同一个生肖时,差值为12岁,当不同生肖时, 后出生者的生肖序号 - 前出生者的生肖序号 模12取正值得到的是这两者的年龄差值 ,这句话我觉得很重要,但是y总没有直说,而是列了数学等式,
而且中间还笔误了, 让本菜鸡苦苦思索了一个小时emmmm - 然后可以看到我们是要对生肖序号作差值,当然可以维护一个哈希表来保存,同时我们要记录一个生肖与序号的对应,还要记录一个每只牛和它的年龄的对应,共需要三个哈希表。
- 计算时,由于我们这里年龄是单独计算的,所以后出生的年龄小,先出生的年龄大,所以这一段
if (info[3] == "previous") {
int r = ((x - y) % 12 + 12) % 12;
if (!r) r = 12;
age[info[0]] = x_age + r;
年龄这里,info[0] (即y)对应待求牛,info[7] (即x)对应已知牛,那么待求牛的年龄更大,这里应为加,下文对应位置应该为减(这也是上文的大佬题解里我认为说的不清楚的地方)。但是这个题只求一个差值,而不要求符号,所以如果说这里正好写反了,即写成了
if (info[3] == "previous") {
int r = ((x - y) % 12 + 12) % 12;
if (!r) r = 12;
age[info[0]] = x_age - r;
} else {
int r = ((y - x) % 12 + 12) % 12;
if (!r) r = 12;
age[info[0]] = x_age + r;
}
最后的输出结果也是一样的,因为取了绝对值,但真正算年龄的话,大小关系是相反的。
4. 根据以上思路,写出以下代码:
代码
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> id = {
{"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2}, {"Dragon", 3}, {"Snake", 4},
{"Horse", 5}, {"Goat", 6}, {"Monkey", 7}, {"Rooster", 8}, {"Dog", 9},
{"Pig", 10}, {"Rat", 11}};
int main() {
unordered_map<string, int> age;
unordered_map<string, string> zod;
age["Bessie"] = 0;
zod["Bessie"] = "Ox";
int n;
scanf("%d", &n);
vector<string> info(8);
while (n--) {
for (int i = 0; i < 8; ++i) {
cin >> info[i];
}
int x = id[zod[info[7]]], x_age = age[info[7]], y = id[info[4]];
if (info[3] == "previous") {
int r = ((x - y) % 12 + 12) % 12; // 后出生的生肖减先出生的生肖对12取模,并取正数
if (!r) r = 12;
age[info[0]] = x_age + r; // 这里若改为-,下文对应地方改为+,也可以AC
} else {
int r = ((y - x) % 12 + 12) % 12; // 后出生的生肖减先出生的生肖对12取模,并取正数
if (!r) r = 12;
age[info[0]] = x_age - r;
}
zod[info[0]] = info[4]; // 把新出现的牛的生肖加入哈希表
}
cout << abs(age["Elsie"]);
return 0;
}
算法二:两哈希表版
- 上一版代码感觉还阔以,但是我们可以发现Bessie作为初始值,最后要求的年龄也只是相对值,所以Bessie的年龄是年龄部分的基准值,那么既然年龄有基准值,那不妨令生肖的基准值也是Bessie的生肖,那就可以省去一个哈希表了~
- 所以我们就只维护一个生肖序号和年龄序号的哈希表,后续年龄差值计算和生肖序号差值计算都借助年龄序号哈希表完成,因为都是相对值。但是有得必有失,这里可以发现生肖顺序与年龄顺序虽然都可以作为相对值,但是顺序可以说是相反的,比如 如果A的生肖序号为0,B的生肖序号为1,那B的生肖比A的大,但是年龄却比A的小,所以这里的代码
if (info[3] == "previous") {
int r = ((x - y) % 12 + 12) % 12; // 生肖差值
if (!r) r = 12;
age[info[0]] = x - r;
} else {
int r = ((y - x) % 12 + 12) % 12;
if (!r) r = 12;
age[info[0]] = x + r;
}
x比y后生,X应该比y的年龄小,但这里却要x - r,正是为了对齐生肖的顺序,那么随之而来,年龄的顺序就恰好相反了,这也算是少用一个哈希表所带来的问题吧。不过本题本来也只需要求差值的绝对值,所以权衡利弊,还是很好的~
- 代码如下:
代码
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> id = {
{"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2}, {"Dragon", 3}, {"Snake", 4},
{"Horse", 5}, {"Goat", 6}, {"Monkey", 7}, {"Rooster", 8}, {"Dog", 9},
{"Pig", 10}, {"Rat", 11}};
int main() {
unordered_map<string, int> age;
age["Bessie"] = 0;
int n;
scanf("%d", &n);
vector<string> info(8);
while (n--) {
for (int i = 0; i < 8; ++i) {
cin >> info[i];
}
int x = age[info[7]], y = id[info[4]]; // 此处x作为年龄的相对值,后续也可以作为生肖序号的相对值
if (info[3] == "previous") {
int r = ((x - y) % 12 + 12) % 12; // 生肖差值
if (!r) r = 12;
age[info[0]] = x - r;
} else {
int r = ((y - x) % 12 + 12) % 12;
if (!r) r = 12;
age[info[0]] = x + r;
}
}
cout << abs(age["Elsie"]);
return 0;
}
结束语碎碎念
一道简单题,但是比较绕,所以来来回回调代码+写题解竟然花了两个小时,也不好说值不值得,希望能帮助看过本文的有疑惑的小伙伴吧~
有任何错误,欢迎大家指出,大家交流,共同进步!菜鸡鞠躬~~~