总的来说华子这两道题只是输入输出在处理的时候麻烦一点，思路倒是很直白，过程是有点复杂，要做好心理准备去一道一道啃下来，不然像这次第一题嫌麻烦跳第二道题，第二道题又没做出来，就GG。而且通过此次机考，发现我自己做题状态与平时完全不同，思维有点凝滞，应该是太紧张了，所以说多多参加机考还是有用的。加油，再接再厉！

T1 热词排序

T1 题干

有多篇文章输入，每篇文章分为标题行和正文行，每篇文章输入时标题和正文各占一行。需要统计所有文章中出现的热词并输出topN的热词。title中的词权重为3，text中权重为1，所有文章中的热词权重相加即为该词的总权重。排序方法为：

1. 两词权重大的排前面
2. 若权重一样，则在title中最先出现的排前面
3. 若title中出现顺序一样，则在text中最先出现的排前面

测试案例：

3 2
xinguan feiyan xinzeng bendi quezhen anli
ju baodao chengdu xinzeng xinguan feiyan bendi quezhen anli yili shenzhen xinzeng bendi quezhen anli liangli yi***gti kongzhi lianghao
xinguan yimiao linchuang shiyan
wuzhong xinguan yimiao tongguo sanqi linchaung shiyan xiaoguo lianghao

输出：

//忘记了

注意：第一行两数代表topN和文章总数M，后面每两行代表一篇文章

T1 解析

此题非常直观，思路是哈希表+sort排序，但是值得注意的是有多重排序条件，我们应该如何进行处理？

此处我们需要自定义一个cmp函数用于比较，由于条件太多，可以设置一个类，用于存储该词的权重，在title中首次出现的index，在text中首次出现的index，这样只需要使用一个自定义的类的cmp函数就可以进行多重条件的排序。

代码如下：

#include <iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
#include<sstream>

using namespace std;

//自定义类
struct Data
{
    string word;
    int total_cnt=0;
    int title_index = INT_MAX;
    int text_index = INT_MAX;
};

//自定义cmp函数
bool cmp(Data& a, Data& b)
{
    if (a.total_cnt == b.total_cnt)
    {
        if (a.title_index == b.title_index)
            return a.text_index < b.text_index;
        else
            return a.title_index < b.title_index;
    }
    else
        return a.total_cnt > b.total_cnt;   
}

/// <summary>
/// 按照pattern拆分字符串，若patter间没有字符串，则不会加入到结果中
/// </summary>
/// <param name="str"></param>
/// <param name="pattern"></param>
/// <returns></returns>
vector<string> split(string& str, const char pattern)
{
    vector<string> ans;
    string temp;
    stringstream ss(str);
    while (getline(ss, temp, pattern))
    {
        ans.push_back(temp);
    }
    return ans;
}

int main()
{
    vector<string> title, text;
    unordered_map<string,Data> mp;
    
    int topN = 0, M = 0;
    scanf_s("%d %d\n", &topN,&M);

    for (int i = 0; i < M; ++i)
    {
        string temp1, temp2;
        getline(cin, temp1);
        getline(cin, temp2);
        title.push_back(temp1);
        text.push_back(temp2);

        //生成每个字段的Data对象并计算其权重和首次出现的下标信息
        vector<string> ss = split(temp1,' ');
        for (int j = 0;j<ss.size();++j)
        {
            string s = ss[j];
            if (mp.find(s) == mp.end())
                mp.insert(make_pair(s, Data()));
            Data& d = mp[s];          
            d.word = s;
            d.total_cnt += 3;
            if (d.title_index > j) d.title_index = j;
        }

        ss = split(temp2, ' ');
        for (int j = 0; j < ss.size(); ++j)
        {
            string s = ss[j];
            if (mp.find(s) == mp.end())
                mp.insert(make_pair(s, Data()));
            Data& d = mp[s];           
            d.word = s;
            d.total_cnt += 1;
            if (d.text_index > j) d.text_index = j;
        }
        temp1.clear();
        temp2.clear();
    }

    vector<Data> vec;
    for (auto& p : mp)
    {
        vec.push_back(p.second);
    }

    //对所有Data对象进行排序
    sort(vec.begin(), vec.end(), cmp);

    //调整输入输出格式
    string ans;
    for (int i = 0; i < topN; ++i)
    {
        ans += vec[i].word;
        ans.push_back(' ');
    }
    //注意去掉结尾的空格
    ans.pop_back();
    cout << ans;
   
    return 0;
}

T1 复盘易错点

T2 依赖关系

T2 题干

某段程序依赖于其他的程序启动，题目提供了n个程序（0~n-1）以及他们之间的依赖关系，要求按下标顺序返回target程序所有前置依赖项。若依赖关系中有环存在，则该程序不能启动，返回-1；若该程序没有依赖关系，则不用管它。

其中，第一行为程序个数n，第二行为target程序下标，之后的第 i 行表示第 i 个程序的相关依赖信息。

对于依赖信息的这一行，第一个数表示依赖个数，之后的数用逗号隔开，每个数表示其依赖程序的下标

测试案例：

4
2
0
1，0
1，1
2，0，2

答输出：

0 1

解析：

依赖关系如图：

程序2依赖程序1，程序1依赖于程序0，所以按序输出为： 0 1

T2 解析

这是一道典型的拓扑关系，解决此类问题可以用dfs和bfs。由于该题只要输出某个节点的前置依赖节点，不妨使用dfs。

程序如下：

#include <iostream>
#include<vector>
#include<string>
#include<sstream>

using namespace std;

/// <summary>
/// 按照pattern拆分字符串，若patter间没有字符串，则不会加入到结果中
/// </summary>
/// <param name="str"></param>
/// <param name="pattern"></param>
/// <returns></returns>
vector<string> split(string& str, const char pattern)
{
    vector<string> ans;
    string temp;
    stringstream ss(str);
    while (getline(ss, temp, pattern))
    {
        ans.push_back(temp);
    }
    return ans;
}

bool dfs(vector<vector<int>>& edges, vector<int>& visited, int node)
{
    //若该节点已经完成了访问，则可以剪枝
    if (visited[node] == 1)  return true;
    //若该节点处于正在访问状态，说明该路径下有环
    else if (visited[node] == 0) return false;

    //将节点状态设置为正在访问
    visited[node] = 0;
    //依次遍历该节点下的所有依赖项，看看是否有相互依赖的情况发生
    for (auto& i : edges[node])
    {
        if (!dfs(edges, visited, i)) return false;
    }
    //若所有依赖项都完成了访问，则设置本节点为完成访问状态
    visited[node] = 1;
    return true;
}

int main()
{
    int n, index;
    cin >> n >> index;

    //edges存储节点i对应的所有前置依赖节点
    vector<vector<int>> edges(n);
    //visited存储每个节点的访问状态，-1表示未访问，0表示正在访问，1表示访问完成
    vector<int> visited(n, -1);
  
    //换行
    string temp;
    getline(cin, temp);

    //逐行获取edges依赖关系
    for (int i = 0; i < n; ++i)
    {
        temp.clear();
        getline(cin, temp);
        vector<string> ss = split(temp, ',');

        int num = atoi(ss[0].c_str());
        for (int j = 1; j <= num; ++j)
        {
            edges[i].push_back(atoi(ss[j].c_str()));
        }
    }
    
    string ans;
    //如果有环，则返回-1
    if (!dfs(edges, visited, index)) cout << -1;
    else
    {
        //循环读取以访问的节点（不包括index节点）
        for (int i = 0; i < n; ++i)
        {
            if (visited[i] == 1 && i != index) {
                ans += to_string(i);
                ans.push_back(' ');
            }
        }
        ans.pop_back();
        cout << ans;
    }
    return 0;
}

T2 复盘易错点

T3 接雨水

此题我没时间看，听说与接雨水类似，之后再总结一下