P9943题解

LastKismet · 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;
}

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