成都X02八月二期最后一次考试 - 倒数四题题解

前言：

尽管这次考试的题目整体难度偏难，但是大家都考了一个很好的成绩，这让我非常的欣慰。我知道这个成绩对比你们之前的成绩有一些低，但你们也不要灰心，相信在今后你们的学习途中你们会大发自己光彩。当你们看到这一篇题解的时候，也是你们在成都集训营的最后一天。我相信你们一定有许多的不舍和留恋吧，希望大家满揣着所有老师对你们的希望和憧憬离开这里。

话不多说，我们来看一下本次考试的倒数四道题目。题目的大意我就不多说了，每道题大家可以自己点击链接进到对应网页来查看。最后四道题是结合了多种算法因此需要选手考虑到非常多的细枝末节的特殊情况，才可以拿到满分。但大家不要怕，看完这一篇题解你们一定可以看懂的。

第一道题 - 班级合照

题目链接：点我传送

**题目整体思路：**这道题的整体思路并不是很难，而且可以通过多种方式来解决这道问题。这里将讲最简单的思路：我们可以在读入数据的时候将男生和女生单独分开来，男生的身高放置在一个数组中，女生的身高放置在数组中。这样一来只需要单独的对两个数组进行一个排序，男生从小到大排，女生从大到小排。最后再将男生和女生分别拍好的顺序输出即可，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

// male用于存放男生的身高。
// female用于存放女生的身高。
int n, male[5005], female[5005];
int mx, fx;  // mx和fx分别记录男生和女生的人数。

int main(){
    cin >> n;
    for (int i=1; i<=n; i++){
        int g, h;
        cin >> g >> h;
        // 存入男生数组或存入女生数组。
        if (g == 1) male[++mx] = h;
        else female[++fx] = h;
    }
    
    // 从小到大男生的身高排序。
    sort(male+1, male+mx+1);  
    // 从大到小对女生身高排序。
    sort(female+1, female+fx+1, greater<int>());
    
    // 输出男生身高。
    for (int i=1; i<=mx; i++) 
        cout << male[i] << " ";
    // 输出女生身高
    for (int j=1; j<=fx; j++) 
        cout << female[j] << " ";
    return 0;
}

当然这道题还有别的解法，也可以使用结构体排序来实现，这里不展示结构体排序的完整代码，只展示结构体排序中的cmp函数：

struct student{
    int gender;  // 性别
    int height;  // 身高
}

bool cmp(student a, student b){
    // 如果性别不一样，就男生靠前。
    if (a.gender != b.gender){
        return a.gender > b.gender;
    }
    // 如果性别一样，就判断是否是男生。
    if (a.gender == b.gender && a.gender == 1){
        return a.height < b.height;
    }
     // 再判断是否是女生。
    if (a.gender == b.gender && a.gender == 0){
        return a.height < b.height;
    }
    return false;  // 可写可不写，养成好习惯。
}

第一道题整体来说思路不难，因此这边就不过多赘述了。

第二道题 - 滨海花园

题目链接：点我传送

题目整体思路：这道题的首先可以用暴力的方式来解决，在数组中遍历每一个长度为k的区间，并统计这个区间内有多少个不同的数字即可。为了统计有多少个不同的数字，我们自然而然可以想到C++ STL库中的好帮手 - 集合Set。Set可以帮助我们对一些元素排序并去重。不懂set基本使用方法的可以自行去网上查阅，x02的老师在第二天就有讲解过set的用法。

通过暴力枚举的方式解决本道题：

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int n, k, ans;
int arr[1000005];

int main(){
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> arr[i];
    
    for (int i=1; i<=n; i++){
        set<int> s;
        // 通过暴力的方式查找每一个长度为k的区间，
        // 每次对区间的元素进行set去重。
        for (int j=i; j<=i+k-1 && j<=n; j++){
            s.insert(arr[j]);
        }
        // 比较set的大小，选择set大小最大的那一个即为答案。
        int k = s.size();
        ans = max(ans, k);
    }
    cout << ans << endl;
    return 0;
}

但提交代码后我们会发现这代码会出现TLE的现象，因为这道题的数据量很大，如果暴力的做法只能拿到60分，因此我们需要考虑优化我们的代码。

在看到题目中“每次拿到新的石子，就会把包里最早捡到的那个石子给抛弃”这个句子，我们必须联想到一个特殊的数据结构 - 队列。队列这个数据结构讲究的是FIFO，即先进先出。这非常符合我们的题干要求，因此这道题正确的做法是通过队列Queue来实现。我们每次读入一个数据后就判断队列的长度是否为k，如果队列的长度为k我们就将对首元素（即最早的那个石头）弹出队列，并将新的石子给压入队列即可。

那我们该如何统计队列中不同颜色的个数呢？我们可以运用到“计数排序”的思想，通过一个数组来记录每一个数字出现的次数，当一个元素在弹出队列后，我们就将这个颜色出现的次数-1，反之则将这个颜色出现的次数+1。如果这个颜色的石头被弹出后正好计数变成0了，就代表这个队列中没有这种颜色的石头了。反之如果新增元素也一样。本题的代码如下：

#include <iostream>
#include <queue>
using namespace std;

// ans表示最终所记录的答案。
// current表示当前背包中有多少种不同颜色的石头。
int n, k, ans, current;
// color[i]表示颜色序号为i的石头出现的次数。
int color[50005];
queue<int> que;

int main(){
    cin >> n >> k;
    for (int i=1; i<=n; i++){
        int t; cin >> t;
        // 如果背包满了，则需要弹出元素。
        if (que.size() == k){
            int tail = que.front();
            que.pop();
            color[tail]--;
            // 判断这个元素在队列里是否存在。
            if (!color[tail]) current--;
        }
        // 判断这个元素在队列里是否存在。
        if (!color[t]) current++;
        color[t]++;
        que.push(t);
        // 不断更新答案。
        ans = max(ans, current);
    }
    cout << ans << endl;
    return 0;
}

第三题 - King&Queen Game - Epi.01(FindDukeMonkey)

题目链接：点我传送

**题目解题思路：**这道题的要求是让我们找到最短到达Duke Monkey的路有几条。看到“最短路”这个字眼，我们自然而言就想到需要使用广度优先搜索的方式来实现本道题目。但题目要求需要找到这样子的“最短路”有几条，则还需要用到DFS即深度优先搜索暴力递归每一种情况，并记录正好在k步走到Duke Monkey的数量有多少。像这样子，我们将一个大问题分解成多个小问题之后题目就变得非常简单的。

首先就是如何使用BFS计算最短路？

以下是本题的BFS代码，大家应该可以很容易看懂（毕竟这是BFS的模板代码，不需要做过多的改动），课上老师都跟大家讲过了，我这边也就不过多赘述了。

1. map表示的是王国森林的地图。
2. [vis[i][j]]表示坐标(i, j)这个位置是否被访问过。
3. ans用于记录答案，当找到最短路后直接return结束函数即可。

void bfs(int x, int y){
    queue<node> que;
    que.push((node){x, y, 0});
    vis[x][y] = 1;

    while(!que.empty()){
        node t = que.front();
        que.pop();
        if (map[t.x][t.y] == '&'){
            ans = t.steps;
            return ;
        }
        for (int i=0; i<4; i++){
            int cx = t.x + dx[i];
            int cy = t.y + dy[i];
            if (cx < 1 || cy < 1 || cx > n || cy > m || vis[cx][cy]) continue;
            if (map[cx][cy] == '#') continue;
            vis[cx][cy] = 1;
            que.push((node){cx, cy, t.steps + 1});
        }
    }
    return ;
}

如何用DFS计算所有的路径？

其中x, y代表当前递归节点的坐标，steps表示走到坐标(x, y)后目前的步数。

void dfs(int x, int y, int steps){
    // 如果找到了一个答案，就将答案计数器的数量增加一。
    if (steps == ans && map[x][y] == '&'){
        total += 1;
        return ;
    }
    // dfs的结束条件，如果当前步数超过了最短路，则一定没有结果，就直接return掉就行。
    if (steps >= ans) return ;
    for (int i=0; i<4; i++){
        int cx = x + dx[i];
        int cy = y + dy[i];
		// 过滤掉不符合的要求。
        if (cx < 1 || cy < 1 || cx > n || cy > m || vis[cx][cy]) continue;
        if (map[cx][cy] == '#') continue;
        vis[cx][cy] = 1;
        dfs(cx, cy, steps+1);
        vis[cx][cy] = 0;
    }
    return ;
}

最后将本题的BFS和DFS结合一下就可以做出来了。本题的完整代码如下：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int n, m, ans, total;
char map[30][30];
bool vis[30][30];
// 四个方向的位移。
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

struct node{
    int x;
    int y;
    int steps;
};

void dfs(int x, int y, int steps){
    if (steps == ans && map[x][y] == '&'){
        total += 1;
        return ;
    }
    if (steps >= ans) return ;
    for (int i=0; i<4; i++){
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (cx < 1 || cy < 1 || cx > n || cy > m || vis[cx][cy]) continue;
        if (map[cx][cy] == '#') continue;
        vis[cx][cy] = 1;
        dfs(cx, cy, steps+1);
        vis[cx][cy] = 0;
    }
    return ;
}

void bfs(int x, int y){
    queue<node> que;
    que.push((node){x, y, 0});
    vis[x][y] = 1;

    while(!que.empty()){
        node t = que.front();
        que.pop();
        if (map[t.x][t.y] == '&'){
            ans = t.steps;
            return ;
        }
        for (int i=0; i<4; i++){
            int cx = t.x + dx[i];
            int cy = t.y + dy[i];
            if (cx < 1 || cy < 1 || cx > n || cy > m || vis[cx][cy]) continue;
            if (map[cx][cy] == '#') continue;
            vis[cx][cy] = 1;
            que.push((node){cx, cy, t.steps + 1});
        }
    }
    return ;
}

int main(){
    // 初始化，读入数据和地图。
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> map[i][j];
        }
    }
    bfs(1, 1);  // 广度优先搜索求最短路。
    // 记得memset清空一下vis数组，否则答案一定是错的。
    memset(vis, 0, sizeof vis);
    dfs(1, 1, 0);  // 深度优先搜索求最短路路径数量。
    
    // 最后判断最短路路径数量输出结果即可。
    if (total) cout << total << endl;
    else cout << -1 << endl;
    return 0;
}

第四题 - King&Queen Game - Epi.03(OperatorRedef)

题目链接：点我跳转

**本题解题思路：**这道题所需要用到的知识是栈，栈跟队列正好相反，讲究的是先进后出。本道题的解题思路开设两个栈，一个栈用于存放读入的数字，另一个栈用于存放读入的符号，并不断维护符号栈让其成为“单调栈”（不知道这个定义也没关系），保证栈内运算符的优先级一定是从小到大的，而不是从大大小的。题目的整体模拟思路如下：

先读入字符串，然后设定一个指针i用于指向正在处理的字符串的位置。若指针i指向的位置是一个数字，则将数字压入数字栈内。如果是一个符号，则需要判断这个符号的优先级：如果符号栈内没有符号，则直接讲该符号压入栈内。否则的话，检查符号栈内的栈顶符号，如果符号栈内的栈顶符号的优先级小于当前符号，则直接将新的符号压入站内。

继续将指针往右移动，如果再次遇到了一个符号，按照要求先检查栈是否为空，否则如果栈顶元素的优先级大于等于当前符号，我们就让栈顶元素弹出，并将数字栈内的最前面两个栈顶元素弹出来做&运算，并将运算后的新数字给压入数字栈。

重复循环以上操作，直到符号栈为空并且字符串已经被完全处理完了。最后当所有的模拟结束后，直接输出数字栈的栈顶元素即可，当前的数字栈栈顶元素即代表最终答案。

（虽然上面这段话非常难理解，但希望大家手动模拟一下自己画两个栈来模拟，这样就很好理解了。因为文字版本并不能很好的体现出这个概念。）

维护单调栈的目的就是始终先运算优先级较高的运算。

备注：

1. 本题需要开long long，否则会有1-2个点过不去。
2. 括号运算在改算法中优先级是最低的。（自行模拟一下）。

本题的完整代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;

string str;
stack<ll> num;
stack<char> operators; 

// &运算。
inline ll operation(ll a, ll b){
    ll ans = abs(a*a - b*b);
    return ans;
}

// 计算a&b的值。
inline ll calculate(){
    if (num.size() < 2) return -1;
    ll a = num.top(); num.pop();
    ll b = num.top(); num.pop();
    return operation(a, b);
}

// 判断是否是一个数字。
inline bool isDigit(char t){
    if (t >= '0' && t <= '9'){
        return true;
    }
    return false;
}

// 判断运算符优先级。
inline ll oLevel(char opt){
    if (opt == '&') return 1;
    return -1;
}

signed main(){
    cin >> str;
    ll len = str.size();
    ll i = 0;
    while(true){
        if (isDigit(str[i])){
            num.push(str[i] - '0');
            i += 1;
        } else{
            if (i >= len && operators.empty()){
                cout << num.top() << endl;
                break;
            } 
            if (operators.empty()){
                operators.push(str[i]);
                i += 1;
            }
            else if (str[i] == '(' || oLevel(operators.top()) < oLevel(str[i])){
                operators.push(str[i]);
                i += 1;
            } else if (operators.size() && str[i] == ')' && operators.top() == '('){
                operators.pop();
                i += 1;
            }  else if (oLevel(operators.top()) >= oLevel(str[i])){
                operators.pop();
                ll k = calculate();
                num.push(k);
            }
        }
    }
    return 0;
}