自动搬运

查看原文

来自洛谷，原作者为

	LastKismet 欲买桂花同载酒，终不似，少年游

搬运于2025-08-24 22:53:13，当前版本为作者最后更新于2023-12-22 21:29:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

P9943

题目概述

给出不同奶牛出生生肖之间的关系，最后求出 Bessie 与 Elsie 的出生年份之间相差的年数。

解题思路

注意题中有这三个限制：

• 最后一个单词是农场上某一头奶牛的名字，为 Bessie 或一头已经在之前的输入中出现过的奶牛。
• 第一个单词是农场上某一头奶牛的名字，不为 Bessie 且未在之前的输入中出现过。
• 输入保证可以通过给定的信息求出结果。

这说明所有的关系式都是由已知推未知，并且确保有结果，大大降低了难度和复杂度。

我们可以开一个 $c$ 数组表示 Bessie 与其他所有奶牛出生年份的差值，$y$ 数组储存每一头奶牛的生肖的对应年份。

易得：$c_0=0$，$y_0=0$。（以牛年为起始年，Bessie 的编号为 $0$ ）

设已知牛编号为 $a$，未知牛编号为 $b$，易得：

当输入条件为 previous 时，

$$c_b = \begin{cases} c_a+(y_b-y_a) & y_b<y_a\\ c_a+(y_b-12-y_a) & y_b \ge y_a\end{cases} $$

当输入条件为 next 时，

$$c_b = \begin{cases} c_a+(y_b-y_a) & y_b>y_a\\ c_a+(y_b+12-y_a) & y_b \le y_a\end{cases} $$

代码思路

我们可以使用 map 映射奶牛名称与对应的编号和各个生肖与其对应的编号。例子：

map<string, int> id;
map<string, int> sx={{"Ox",0},{"Tiger",1},{"Rabbit",2},{"Dragon",3},{"Snake",4},{"Horse",5},{"Goat",6},{"Monkey",7},{"Rooster",8},{"Dog",9},{"Pig",10},{"Rat",11}};

id["Bessie"]=0;

然后根据上面推出的公式编写代码即可。

完整代码

#include<bits/stdc++.h>
using namespace std;

int n;
int c[105],y[205];
string a,b,pd,t,year;//已知犇，未知犇，前或后，临时字符串，生肖年
map<string,int> sx={{"Ox",0},{"Tiger",1},{"Rabbit",2},{"Dragon",3},{"Snake",4},{"Horse",5},{"Goat",6},{"Monkey",7},{"Rooster",8},{"Dog",9},{"Pig",10},{"Rat",11}};
map<string,int> id;

int main(){
	cin>>n;
	c[0]=y[0]=0;
	id["Bessie"]=0;
	for(int i=1;i<=n;i++){
		cin>>a>>t>>t>>pd>>year>>t>>t>>b;//此处也可用scanf，但蒟蒻没弄好格式QAQ 
		id[a]=i;y[i]=sx[year];//初始化Bessie的数据
		if(pd=="previous"){
			if(y[i]<y[id[b]]){
				c[i]=c[id[b]]+(y[i]-y[id[b]]);
			}
			else{
				c[i]=c[id[b]]+(y[i]-12-y[id[b]]);
			}
		}
		if(pd=="next"){
			if(y[i]>y[id[b]]){
				c[i]=c[id[b]]+(y[i]-y[id[b]]);
			}
			else{
				c[i]=c[id[b]]+(y[i]+12-y[id[b]]);
			}
		}
	}
	cout<<abs(c[id["Elsie"]]);//c数组中储存的是差值，不要忘了加绝对值
	return 0;
}

_完结撒花_ヾ(≧ ▽ ≦)ゝ