目录

  1. 额外的一道题
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析
  2. 第一题
    1. 题目描述
    2. 输入描述
    3. 输出描述
    4. 分析
  3. 第二题
    1. 输入描述
    2. 输入描述
    3. 输出描述
    4. 分析
  4. 第三题
    1. 输入描述
    2. 输入描述
    3. 输出描述
    4. 分析

额外的一道题

题目描述

长宽分别为m、n的一个棋盘，里面有k个位置设有障碍物，有障碍物的点不能通过，求问从左上顶点(0,0)到右下顶点(m-1, n-1)是否有最短路径，并求出最短路径。

输入描述

第一行为n,m,k，分别代表棋盘的行数和列数，以及障碍物的数量。
剩下k行，每一行有两个数，代表障碍物的x和y坐标。

输出描述

若存在最短路径，输出为最短路径的大小；否则输出为0。

分析

  • 采用回溯法，利用递归，列出各种可能情况进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int m, n;
bool isFound = false;
int minCnt = INT_MAX;

void findShortestPath(const vector<vector<bool> >& map, vector<vector<bool> >& visited, int curX, int curY, int cnt) {
    if (curX == n - 1 || curY == m - 1) {
        isFound = true;
        if (cnt < minCnt)
            minCnt = cnt;
        return;
    }
    // down
    if (curX < n - 1 && !barrier[curX + 1][curY] && !visited[curX + 1][curY]) { 
        visited[curX + 1][curY] = true;
        shortestPath(barrier, visited, curX + 1, curY, cnt + 1);
        visited[curX + 1][curY] = false;
    }
    // right
    if (curY < m - 1 && !barrier[curX][curY + 1] && !visited[curX][curY + 1]) {
        visited[curX][curY + 1] = true;
        shortestPath(barrier, visited, curX, curY + 1, cnt + 1);
        visited[curX][curY + 1] = false;
    }
    // up
    if (curX > 0 && !barrier[curX - 1][curY] && !visited[curX - 1][curY]) {
        visited[curX - 1][curY] = true;
        shortestPath(barrier, visited, curX - 1, curY, cnt + 1);
        visited[curX - 1][curY] = false;
    }
    // left
    if (curY > 0 && !barrier[curX][curY - 1] && !visited[curX][curY - 1]) {
        visited[curX][curY - 1] = true;
        shortestPath(barrier, visited, curX, curY - 1, cnt + 1);
        visited[curX][curY - 1] = false;
    }
}

int main() {
    int k;
    cin >> n >> m >> k;
    vector<vector<bool> > barrier(n, vector<bool>(n, false));
    vector<vector<bool> > visited(n, vector<bool>(n, false));
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        barrier[x][y] = true;
    }
    shortestPath(barrier, visited, 0, 0, 0);
    if (isFound)
        cout << minCnt << endl;
    else
        cout << 0 << endl;
}

第一题

题目描述

薯队长写了一篇笔记草稿，请你帮忙输出最后内容。

  1. 输入字符包括英文字符、“(”、“)”和“<”；
  2. 英文字符表示笔记内容；3. 括号之间表示注释内容，任何字符都无效。括号保证成对出现；
  3. “<”表示退格，删去前面一个笔记内容字符，括号不受“<”影响。

输入描述

输入一行字符串。长度小于等于10000。

输出描述

输出一行字符串，表示最终的笔记内容。

分析

  • 题目不是很难，直接按照题意即可求出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
    string src;
    cin >> src;
    string dst = "";
    int cnt = 0;
    for (int i = 0; i < src.size(); ++i) {
        if (src[i] == '(') 
            ++cnt;
        else if (src[i] = ')') {
            --cnt;
            continue;
        }
        if (cnt == 0) {
            if (src[i] == '<') {
                if (!dst.empty())
                    dst.pop_back(src[i]);
            }
            else
                dst.push_back(src[i]);
        }
    }
    cout << dst << endl;
    return 0;
}

第二题

输入描述

薯队长最近在玩一个迷宫探索类游戏，迷宫是一个N*N的矩阵形状，其中会有一些障碍物禁止通过，这个迷宫还有一些特殊的设计，它的左右边界以及上下边界是连通的，比如在(2,n)的位置继续往右走一格可以到(2,1)，在(1,2)的位置继续往上走一格可以到(n,2)。请问薯队长从起点位置S，最少走多少格才能到达迷宫的出口位置E。

输入描述

第一行正整数N，接下来N行字符串。‘.’表示可以通过，‘#’表示障碍物，‘S’表示起点（有且仅有一个），‘E’表示出口（有且仅有一个）。
对于50%的数据，0<N<10；对于100%的数据，0<N<1000。

输出描述

输出一个整数，表示从S到E最短路径的长度，无法到达则输出-1。

分析

  • 用一个二维数组保存从S到当前节点的路径长度，最后直接返回E坐标位置的值即可。（回溯法只能通过50%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int startX = 0, startY = 0;
int endX = 0, endY = 0;

int findShortestPath(const vector<vector<int> >& map, int n) {
    const vector<vector<int> > dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 上下左右四个方向
    vector<vector<bool> > visited(n, vector<bool>(n, false)); // 记录已访问结点
    vector<vector<int> > times(n, vector<int>(n, -1)); // 记录从S到当前位置的路径长度
    times[startX][startY] = 0;
    queue<vector<int> > q;
    q.push({startX, startY});
    
    while (!q.empty()) {
        vector<int> cur = q.front();
        q.pop();
        for (int i = 0; i < dir.size(); ++i) {
            // 下一步点的坐标
            int x = cur[0] + dir[i][0];
            int y = cur[1] + dir[i][1];
            // 处理边界点
            if (x == -1)
                x = n - 1;
            else if (x == n)
                x = 0;
            if (y == -1)
                y = n - 1;
            else if (y == n)
                y = 0;
            
            if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y]
                && (map[x][y] == '.' || map[x][y] == 'S') ) {
                times[x][y] = times[cur[0]][cur[1]] + 1;
                if (x == endX && y == endY)
                    return times[x][y];
                visited[x][y] = true;
                q.push({x, y});
            }
        }
    }
    return times[endX][endY];
}

int main() {
    int n;
    cin >> n;
    vector<string> map;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); ++j) {
            if (s[j] == 'S') {
                startX = i;
                startY = j;
            }
            if (s[j] == 'E') {
                endX = i;
                endY = j;
            }
        }
        map.push_back(s);
    }
    int res = findShortestPath(map, n);
    cout << res << endl;
}

第三题

输入描述

在游戏中，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱，这个回收员有个坏毛病，每次卖给他一件宝物后，之后他就看不上比这件宝物差的宝物了。在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多？

输入描述

第一行一个正整数N，接下来N行每行两个整数分别表示X和H。
对于70%的数据：0<N<10000，0<Xi<10^6，0<Hi<10^6；
对于100%的数据：0<N<10^6，0<Xi<10^6，0<Hi<10^6

输出描述

一个整数，表示最多可以卖出的宝物数。

分析

  • 先按X进行从小到大的排序，保证维度X是单调非递减的，然后将问题转化为求H维度的最长递增子序列；
  • 最长递增子序列需要利用二分查找，控制时间复杂度为O(N logN)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int getLargestSales(vector<pair<int, int> >& values) {
    vector<int> res;
    sort(values.begin(), values.end(), [](pair<int, int>l, pair<int, int>r)
        {return l.first == r.first ? l.second < r.second : l.first < r.first;});
    for (int i = 0; i < values.size(); ++i) {
        if (res.empty() || res.back() <= values[i].second) {
            res.push_back(values[i].second);
        }
        else {
            int low = 0;
            int high = res.size() - 1;
            while (low < high) {
                int mid = (high + low) / 2;
                if (res[mid] <= values[i].second)
                    low = mid + 1;
                else
                    high = mid;
            }
            res[low] = values[i].second;
        }
    }
    return res.size();
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int> > values(n);
    for (int i = 0; i < n; ++i)
        cin >> values[i].first >> values[i].second;

    cout << getLargestSales(values) << endl;
}