刷题笔记 - January 2024

校门外的树 OpenJ_Bailian - 2808

【考点】这个算法的思路相对简单，主要涉及对数组元素的更新和统计。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int L, M;
    int a, b;
    cin >> L >> M;
    vector<int> tree(L + 1, 1);
    for(int i = 0; i < M; i++) {
        cin >> a >> b;
        for(int j = a; j <= b; j++) {
            tree[j] = 0;    
        }
    }
    int res = 0;
    for(int i = 0; i <= L; i++) {
        if(tree[i]) {
            res++;
        }   
    }
    cout << res << endl;
    return 0;
}

鸡兔同笼 OpenJ_Bailian - 2750

【考点】这个问题是一个简单的数学问题，需要考察对问题的理解和数学建模能力。

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    if(n % 2 == 1) {
        cout << "0 0" << endl;
    } else {
        if(n % 4 == 0) {
            cout << n / 4 << " " << n / 2 << endl;
        } else {
            cout << n / 4 + 1 << " " << n / 2 << endl;
        }
    }
    return 0;
}

与7无关的数 OpenJ_Bailian - 2701

【考点】这道算法题的考点主要是关于条件判断和循环的运用，以及函数的调用。

#include <iostream>

using namespace std;

bool seven(int x) {
    if(x % 7 == 0) {
        return true;
    } else if(x % 10 == 7) {
        return true;
    } else if(x / 10 == 7) {
        return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    while(n >= 100) {
        cin >> n;
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
        if(seven(i) == false) {
            res += i * i;
        }
    }
    cout << res << endl;
    return 0;
}

细菌繁殖 OpenJ_Bailian - 2712

【考点】这道题目主要考察对日期计算和简单模拟问题的理解，以及编写正确的逻辑来解决问题。

#include <iostream>
#include <vector>

using namespace std;

int date(int m, int d) {
    int count = 0;
    if(m == 1) {
        count += d;
    } else if(m == 2) {
        count += 31 + d;
    } else if(m == 3) {
        count += 31 + 28 + d;
    } else if(m == 4) {
        count += 31 * 2 + 28 + d;
    } else if(m == 5) {
        count += 31 * 2 + 28 + 30 + d;
    } else if(m == 6) {
        count += 31 * 3 + 28 + 30 + d;
    } else if(m == 7) {
        count += 31 * 3 + 28 + 30 * 2 + d;
    } else if(m == 8) {
        count += 31 * 4 + 28 + 30 * 2 + d;
    } else if(m == 9) {
        count += 31 * 5 + 28 + 30 * 2 + d;
    } else if(m == 10) {
        count += 31 * 5 + 28 + 30 * 3 + d;
    } else if(m == 11) {
        count += 31 * 6 + 28 + 30 * 3 + d;
    } else {
        count += 31 * 6 + 28 + 30 * 4 + d;
    }
    return count;
}

int main() {
    int n, m1, d1, x, m2, d2;
    cin >> n;
    vector<int> res(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> m1 >> d1 >> x >> m2 >> d2;
        int day = date(m2, d2) - date(m1, d1);
        for(int i = 0; i < day; i++)
            x *= 2;
        res[i] = x;
    }
    for(int y : res) {
        cout << y << endl;
    }
    return 0;
}

完美立方 OpenJ_Bailian - 2810

【考点】这道算法题的考点是寻找满足特定条件的整数组合，即完美立方。
【解题思路】
关键是要理解完美立方的定义，并将其转化为代码。
需要注意的是，内层循环的起始值以及循环条件的设定要保证不会导致重复的组合被输出。

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    for(int a = 3; a <= n; a++) {
        for(int b = 2; b < a; b++) {
            for(int c = b; c < a; c++) {
                for(int d = c; d < a; d++) {
                    if(a * a * a == b * b * b + c * c * c + d * d * d) {
                        cout << "Cube = " << a << ", 
                        Triple = (" << b << ", " << c << ", " << d << ")\n";
                    }
                }
            }
        }
    }
    return 0;
}

计算书费 OpenJ_Bailian - 2675

【考点】这道题目主要涉及基本的输入输出和循环操作，考察对算法和简单计算的理解和实现能力。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int k;
    cin >> k;
    vector<float> res(k, 0);
    for (int n = 0; n < k; n++) {
        int a, b, c, d, e, f, g, h, i, j;
        cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j;
        res[n] = a * 28.9 + b * 32.7 + c * 45.6 + d * 78 +
        e * 35 + f * 86.2 + g * 27.8 + h * 43 + i * 56 + j * 65;
    }
    for(float x : res) {
        printf("%.2f\n", x);
    }
    return 0;
}

肿瘤检测 OpenJ_Bailian - 2677

【考点】这是一道涉及基本逻辑和二维数组操作的算法题。
【解题思路】
主要通过对二维数组的遍历和条件判断，确定肿瘤区域的位置，并计算其面积和边界长度。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> CT(N, vector<int>(N, 0));
    vector<vector<int>> flag(N, vector<int>(N, 0));
    int area = 0, border = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> CT[i][j];
            if(CT[i][j] <= 50) {
                area++;
                flag[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(flag[i][j]) {
                if(i - 1 >= 0 && !flag[i - 1][j]) {
                    border++;
                } else if (j - 1 >= 0 && !flag[i][j - 1]) {
                    border++;
                } else if (i + 1 < N && !flag[i + 1][j]) {
                    border++;
                } else if (j + 1 < N && !flag[i][j + 1]) {
                    border++;
                }
            }
        }
    }
    cout << area << " " << border;
    return 0;
}

城堡问题 OpenJ_Bailian - 2815

【考点】结合了深度优先搜索和位操作来解决城堡问题，其关键在于遍历并统计连通区域的数量和面积。
【解题思路】
（1）深度优先搜索：算法使用深度优先搜索来遍历城堡中的房间。从每个房间开始，递归地探索与当前房间相连的未访问过的房间，直到无法继续为止。
（2）位操作：城堡中的每个房间都可以由四个方向的墙壁表示。这些墙壁可以用二进制数的位来表示。例如，墙壁被编码为：1 表示西墙、2 表示北墙、4 表示东墙、8 表示南墙。通过按位与运算，可以检查当前房间与相邻房间之间的墙壁是否存在。
（3）房间计数和面积计算：在遍历城堡的过程中，统计房间的数量和每个房间的面积。对每个未访问过的房间应用深度优先搜索，并计算每个连通区域的面积。统计房间数量和最大面积。

#include <iostream>
#include <algorithm>

using namespace std;

int m, n;
int castle[50][50] = {0};
bool visited[50][50] = {false};

int DFS(int i, int j) {
    int area = 1;
    visited[i][j] = true;
    if (j - 1 >= 0 && !visited[i][j - 1] && (castle[i][j] & 1) == 0) {
        area += DFS(i, j - 1);
    }
    if (i - 1 >= 0 && !visited[i - 1][j] && (castle[i][j] & 2) == 0) {
        area += DFS(i - 1, j);
    }
    if (j + 1 < n && !visited[i][j + 1] && (castle[i][j] & 4) == 0) {
        area += DFS(i, j + 1);
    }
    if (i + 1 < m && !visited[i + 1][j] && (castle[i][j] & 8) == 0) {
        area += DFS(i + 1, j);
    }
    return area;
}


int main() {
    int room = 0, maxArea = 0;
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> castle[i][j];
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                int area = DFS(i, j);
                room++;
                maxArea = max(area, maxArea);
            }
        }
    }
    cout << room << endl << maxArea;
    return 0;
}

两倍 OpenJ_Bailian - 2807

【考点】双重循环：使用两层循环来遍历数组元素，以检查是否存在满足条件的数对。
条件判断：在内层循环中，检查当前元素是否是外层循环元素的两倍。
【解题思路】1.排序：对输入的数据进行排序，以便后续的比较。
2.双重循环：使用两层循环，外层循环遍历数组的每个元素，内层循环从外层循环的下一个元素开始遍历。
3.条件判断：在内层循环中，检查当前元素是否是外层循环元素的两倍，如果是，则增加结果计数器。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> input;
    int x;
    cin >> x;
    while(x){
        input.push_back(x);
        cin >> x;
    }
    sort(input.begin(), input.end());
    int res = 0;
    for(int i = 0; i < input.size() - 1; i++) {
        for(int j = i + 1; j < input.size(); j++) {
            if(input[j] == input[i] * 2)
                res++;
        }
    }
    cout << res << endl;
    return 0;
}

波兰表达式 OpenJ_Bailian - 2694

【考点】逆波兰表达式： 理解逆波兰表达式的基本概念和计算规则。栈的应用： 使用栈来处理逆波兰表达式的计算。栈在这里用于存储操作数，并在遇到运算符时执行相应的运算。字符串处理： 使用字符串流 istringstream 和 getline 函数来将输入的字符串分割成单个操作数和运算符。
【解题思路】
1.字符串分割： 使用 istringstream 和 getline 将输入的字符串按空格分割成单个操作数和运算符，并存储在 vector<string> input 中。
2.栈的运用： 从右向左遍历 input 向栈中压入操作数，遇到运算符时从栈中弹出相应数量的操作数进行运算，结果再入栈。这样最终栈中的唯一元素就是整个表达式的计算结果。
3.注意运算次序： 由于是逆波兰表达式，遇到运算符时先弹出的是后面的操作数，后弹出的是前面的操作数。在计算时要注意运算次序，比如减法和除法需要注意被减数或被除数和减数或除数的次序。

#include <iostream>
#include <vector>
#include <sstream>
#include <stack>

using namespace std;

int main() {
    vector<string> input;
    string line, s;
    getline(cin, line); 
    istringstream S(line); // 分割字符串
    while (S >> s) {
        input.push_back(s);
    }
    stack<double> v;
    for(int i = input.size() - 1; i >= 0; i--) {
        // 若是运算数，入栈
        if(input[i] != "+" && input[i] != "-" && input[i] != "*" && input[i] != "/") {
            double x = stod(input[i]);
            v.push(x);
        } else {    // 若是运算符，运算
            double b = v.top();
            v.pop();
            double a = v.top();
            v.pop();
            double c;
            if(input[i] == "+") {
                c = a + b;
            } else if(input[i] == "-") {
                c = a - b;
            } else if(input[i] == "*") {
                c = a * b;
            } else if(input[i] == "/") {
                c = a / b;
            }
            v.push(c);
        }
    }
    printf("%f\n", v.top());
    return 0;
}

大整数乘法 OpenJ_Bailian - 2980

【考点】需要理解大整数的乘法过程以及如何通过数组来保存中间结果。此外，还需注意处理前导零的情况，确保结果的正确性。
【解题思路】
1.大整数处理：涉及到的两个大整数无法直接通过基本数据类型（如 int 或 long long）来表示，因此需要通过字符串进行处理。
2.乘法的实现： 通过两个嵌套的循环，对 a 和 b 的每一位进行乘法操作，并将结果保存在 result 中。这里的乘法是模拟手工计算乘法的过程。
3.数组的使用： result 是一个整数数组，用于保存每一位的乘法结果和进位。在循环中，对应位的乘法结果被加到数组的相应位置上。

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

using namespace std;

string multiply(string a, string b) {
    int len1 = a.size();
    int len2 = b.size();
    vector<int> result(len1 + len2, 0);
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = mul + result[i + j + 1];
            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }
    string res;
    for (int x : result) {
        if (!(res.empty() && x == 0)) { // 避免前导零
            res.push_back(x + '0');
        }
    }
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;
    string c = multiply(a,b);
    cout << c << endl;
    return 0;
}

骑车与走路 OpenJ_Bailian - 2703

【考点】主要考察对数学计算和条件判断的理解。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, d;
    cin >> n;
    vector<string> res;
    for(int i = 0; i < n; i++) {
        cin >> d;
        if(27 + 23 + d / 3 <= d / 1.2) {
            res.push_back("Bike");
        } else {
            res.push_back("Walk");
        }
    }
    for(string s : res) {
        cout << s << endl;
    }
    return 0;
}

垂直直方图 OpenJ_Bailian - 2800

【考点】字符串处理：代码通过 getline(cin, line)逐行读取输入的文本内容，并将其存储在名为 line 的字符串变量中。
数组操作：使用了名为 time 的数组来存储 26 个大写字母出现的次数。time 数组的索引对应字母的 ASCII 码减去'A'的 ASCII 码，因此'A'对应 0，'B'对应 1，以此类推。
【解题思路】
1.逐行读取输入的文本内容。
2.对每一行文本进行遍历，统计大写字母的出现次数，更新 time 数组。
3.找到出现次数最多的字母次数，确定垂直直方图的高度。
4.在每一列上根据字母的出现次数打印星号或空格，以绘制垂直直方图。
5.打印字母标签，即'A'到'Z'。

#include <iostream>
#include <vector>

using namespace std;

int time[26] = {0};

void times(string line) {
    for(char c : line) {
        if('A' <= c && c <= 'Z') {
            time[c - 'A']++;
        }
    }
}

void plot() {
    int maxn = 0;
    for(int n : time) {
        if(n > maxn) {
            maxn = n;
        }
    }
    for(int i = 0; i < maxn; i++) {
        for(int j = 0; j < 26; j++) {
            if(maxn - i - time[j] <= 0) {
                cout << "* ";
            } else {
                cout << "  ";
            }
        }
        cout << endl;
    }
    for(int i = 0; i < 26; i++) {
        cout << char(i + 'A') << " ";
    }
}

int main() {
    string line;
    for(int i = 0; i < 4; i++) {
        getline(cin, line);
        times(line);
    }
    plot();
    return 0;
}

数字三角形 OpenJ_Bailian - 2760

【考点】考点主要涉及递归和动态规划的基础思想。
【解题思路】
1.递归路径遍历： path 函数是递归地遍历数字三角形的路径。从顶部开始，每次选择下一行的相邻数字（正下方或右下方），累加路径上的数字，并更新最大路径和。
2.递归终止条件： 当遍历到最后一行时（i == n - 1），将当前路径的和与最大路径和比较，更新最大路径和。递归过程会自动回溯到上一层，继续尝试其他路径。

#include <iostream>
#include <vector>

using namespace std;

int n;
int maxSum = 0;
vector<vector<int>> tree;

void path(int i, int j, int sum) {
    sum += tree[i][j];
    if(i == n - 1) {
        if(sum > maxSum) {
            maxSum = sum;
        }
//      cout << sum << " ";
        return;
    }
    path(i + 1, j, sum);
    path(i + 1, j + 1, sum);
}

int main() {
    cin >> n;
    tree.resize(n);
    int x;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i + 1; j++) {
            cin >> x;
            tree[i].push_back(x);
        }
    }
    path(0, 0, 0);
    cout << maxSum << endl;
    return 0;
}

二叉树 OpenJ_Bailian - 2756

【考点】二叉树的最近公共祖先（LCA）问题。
【解题思路】
通过循环迭代计算这两个节点的祖先，直到找到它们的最近公共祖先或者某一个节点的祖先是根节点（值为 1）。
1.每次迭代比较两个节点的祖先，更新它们的值以便向上移动到更高的祖先节点。
2.如果发现其中一个节点的祖先已经是根节点，则返回 1 作为最近公共祖先。
3.如果发现两个节点的祖先相等，则返回这个相等的值作为最近公共祖先。

#include <iostream>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    int xi = x / 2;
    int yj = y / 2;
    while(xi != 1){
        if(xi == yj) {
            cout << xi << endl;
            return 0;
        } else if(xi < yj){
            yj /= 2;
            continue;
        } else {
            xi /= 2;
            continue;
        }
    }
    cout << 1 << endl;
    return 0;
}

谁拿了最多奖学金 OpenJ_Bailian - 2715

【考点】主要考察了对条件判断、函数调用、全局变量和局部变量的理解和运用，以及对算法设计的能力。
【解题思路】
1.理解奖学金条件： 首先需要理解每个条件对应的奖学金金额计算规则，如成绩、科研论文数量、学科竞赛等。
2.编写条件判断： 根据题目描述，编写条件判断语句来计算每个学生的奖学金金额，并将结果累加到 totalMoney 中。
3.更新最大值： 在计算每个学生的奖学金金额时，比较当前学生的奖学金金额是否大于当前记录的最大奖学金金额，如果是则更新。

#include <iostream>

using namespace std;

string maxName;
int maxMoney = 0;
int totalMoney = 0;

void res(string name, int grade1, int grade2, char leader, char west, int paper) {
    int money = 0;
    if(grade1 > 80 && paper >= 1) {
        money += 8000;
    }
    if(grade1 > 85 && grade2 > 80){
        money += 4000;
    }
    if(grade1 > 90){
        money += 2000;
    }
    if(grade1 > 85 && west == 'Y') {
        money += 1000;
    }
    if(grade2 > 80 && leader == 'Y'){
        money += 850;
    }
    if(money > maxMoney){
        maxName = name;
        maxMoney = money;
    }
    totalMoney += money;
}

int main() {
    string name;
    int N, grade1, grade2, paper;
    char leader, west;
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> name >> grade1 >> grade2 >> leader >> west >> paper;
        res(name, grade1, grade2, leader, west, paper);
    }
    cout << maxName << endl << maxMoney << endl << totalMoney;
    return 0;
}

大象喝水 OpenJ_Bailian - 2720

【考点】计算过程主要涉及到了圆柱体积的计算以及向上取整操作。

#include <iostream>

using namespace std;

int main() {
    const double Pi = 3.14159;
    int h, r;
    cin >> h >> r;
    int res = 20 / (Pi * r * r * h / 1000) + 1;
    cout << res << endl;
    return 0;
}

八皇后 OpenJ_Bailian - 2754

【考点】这是经典的八皇后问题，主要考察的是回溯算法和递归的运用。
【解题思路】
1.递归与回溯：通过递归地尝试每一行的每一个位置，并在不能放置皇后时回溯到上一步，再尝试下一个位置，最终找到所有解。
2.安全性检查：isSafe 函数的实现是解决八皇后问题的核心，通过检查同一列和对角线上是否有其他皇后来保证棋盘的合法性。
3.二维数组存储结果：boards 向量用于存储所有符合条件的八皇后棋盘，即每一个解都是一个八元素的向量，表示每一行皇后所在的列数。

#include <iostream>
#include <vector>

using namespace std;

bool isSafe(vector<int>& board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col) {  // 检查同一列，即列数相等
            return false;
        }
        if (abs(i - row) == abs(board[i] - col)) {  // 检查对角线，即行差 == 列差
            return false;
        }
    }
    return true;
}

void solveQueens(vector<vector<int>>& boards, vector<int>& board, int row) {
    if (row == 8) {
        boards.push_back(board);
        return;
    }
    for (int col = 0; col < 8; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;
            solveQueens(boards, board, row + 1);
        }
    }
}

void printQueens(vector<vector<int>>& boards) {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for(int i = 0; i < n; i++) {
        for (int x : boards[b[i] - 1]) {    // b从1开始，所以-1
            cout << x + 1;  // col从0开始，所以+1
        }
        cout << endl;       
    }
}

int main() {
    vector<vector<int>> boards;
    vector<int> board(8);
    solveQueens(boards, board, 0);
    printQueens(boards);
    return 0;
}

大整数减法 OpenJ_Bailian - 2736

【考点】大整数处理：该代码处理了两个大整数的减法操作，大整数指的是超出了常规整型变量范围的整数，需要以字符串的形式进行处理。
【解题思路】
1.首先定义一个结果数组 result 来存储每一位的计算结果。然后从各个位数的最低位开始，依次相减，同时处理借位情况。
2.在每一位相减时，先将对应位的字符转换为数字，并根据需要处理进位。最后，构造结果字符串，避免输出结果中的前导零。

#include <iostream>
#include <vector>

using namespace std;

string subtraction(string a, string b) {
    vector<int> result(a.size(), 0);
    int carry = 0;
    for(int i = a.size() - 1, j = b.size() - 1; i >= 0; i--, j--) {
        int num_a = a[i] - '0';
        int num_b = (j >= 0) ? b[j] - '0' : 0;
        int temp = num_a - num_b - carry;
        if (temp < 0) { // 如果差值为负，需要借位
            temp += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result[i] = temp;
    }
    string res;
    for (int x : result) {
        if (!(res.empty() && x == 0)) { // 避免前导零
            res.push_back(x + '0');
        }
    }
    return res;
}

int main() {
    string a, b;
    cin >> a >> b;
    cout << subtraction(a, b);
    return 0;
}

迷宫 OpenJ_Bailian - 2790

【考点】主要考点包括深度优先搜索（DFS）算法、递归、二维数组的使用、以及函数的调用和参数传递。
【解题思路】
1.每次调用GOmaze函数时，首先检查当前位置是否为终点，如果是则返回 true，表示找到了一条路径。然后将当前位置标记为已访问过的位置，以避免重复访问。接着依次尝试向上、下、左、右四个方向移动，如果移动后的位置为可行走的位置（即为'.'），则继续递归调用 GOmaze 函数，直到找到一条路径或者无法继续前进。
2.map 函数：首先读取迷宫的大小 n，然后使用二维 vector 来存储迷宫的地图信息。接着读取迷宫的地图信息，并将其存储到二维 vector 中。然后读取起点和终点的坐标信息。如果起点或终点为墙（'#'），则直接将结果设为"NO"，表示无法到达终点。最后调用 GOmaze 函数来判断是否存在从起点到终点的路径，并将结果存储到结果vector 中。

#include <iostream>
#include <vector>

using namespace std;

bool GOmaze(vector<vector<char>>& map, int ha, int la, int hb, int lb, int n) {
    if (ha == hb && la == lb) {
        return true;
    }
    map[ha][la] = '#';
    if (ha + 1 < n && map[ha + 1][la] == '.') {
        if (GOmaze(map, ha + 1, la, hb, lb, n)) {
            return true;
        }
    }
    if (ha - 1 >= 0 && map[ha - 1][la] == '.') {
        if (GOmaze(map, ha - 1, la, hb, lb, n)) {
            return true;
        }
    }
    if (la + 1 < n && map[ha][la + 1] == '.') {
        if (GOmaze(map, ha, la + 1, hb, lb, n)) {
            return true;
        }
    }
    if (la - 1 >= 0 && map[ha][la - 1] == '.') {
        if (GOmaze(map, ha, la - 1, hb, lb, n)) {
            return true;
        }
    }
    return false;
}

void map(vector<string>& result) {
    int n;
    cin >> n;
    vector<vector<char>> maze(n, vector<char>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
        }
    }
    int ha, la, hb, lb;
    cin >> ha >> la >> hb >> lb;
    if (maze[ha][la] == '#' || maze[hb][lb] == '#') {
        result.push_back("NO");
    }
    if (GOmaze(maze, ha, la, hb, lb, n)) {
        result.push_back("YES");
    } else {
        result.push_back("NO");
    }
}

int main() {
    int k;
    cin >> k;
    vector<string> res;
    for (int i = 0; i < k; i++) {
        map(res);
    }
    for (string o : res) {
        cout << o << endl;
    }
    return 0;
}

1.1_约瑟夫问题（手写）

#include <iostream>
#include <list>

using namespace std;

void josephus(int n, int m) {
    list<int> people;
    // 初始化人的编号
    for (int i = 1; i <= n; i++) {
        people.push_back(i);
    }
    auto current = people.begin();
    while (!people.empty()) {
        // 找到报数到 m 的人
        for (int i = 1; i < m; i++) {
            current++;
            if (current == people.end()) {
                current = people.begin();
            }
        }
        cout << *current << " ";
        current = people.erase(current);
        // 如果出圈的是最后一个人，重新开始
        if (current == people.end()) {
            current = people.begin();
        }
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    josephus(n, m);
    return 0;
}

1.2_约瑟夫问题（队列）

#include <iostream>
#include <deque>

using namespace std;

void josephus(int n, int m) {
    deque<int> people;
    for (int i = 1; i <= n; i++) {
        people.push_back(i);
    }
    while (!people.empty()) {
        for (int i = 1; i < m; i++) {
            people.push_back(people.front());
            people.pop_front();
        }
        cout << people.front() << " ";
        people.pop_front();
    }
    cout << endl;
}

int main() {
    int n, m;
    cin >> n >> m;
    josephus(n, m);
    return 0;
}

1.3_机器翻译（deque）

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    deque<int> memory; 
    int* words = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> words[i];
    }
    int count = 0;
    for(int i = 0; i< n; i++) {
        if(find(memory.begin(), memory.end(), words[i]) == memory.end()) {
            count++;
            if(memory.size() == m) {
                memory.pop_front();
            }
            memory.push_back(words[i]);
        }
    }
    cout << count << endl;
    return 0;
}

1.4_餐厅排队（deque）

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int q, n;
    cin >> q;
    deque<int> student;
    vector<vector<int>> manage(q, vector<int>(2, 0));
    for(int i = 0; i < q; i++) {
        cin >> n;
        manage[i][0] = n;
        if(n == 1) {
            cin >> manage[i][1];
        }
    }
    for(int i = 0; i < q; i++){
        if(manage[i][0] == 1) {
            student.push_back(manage[i][1]);
        } else if(manage[i][0] == 2) {
            student.pop_front();
        } else {
            cout << *student.begin() << " " << *(student.end() - 1) << endl;
        }
    }
    return 0;
}

1.5_神秘礼盒（deque）

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int q, n;
    cin >> q;
    deque<int> box;
    vector<vector<int>> manage(q, vector<int>(2, 0));
    for(int i = 0; i < q; i++) {
        cin >> n;
        manage[i][0] = n;
        if(n == 1) {
            cin >> manage[i][1];
        }
    }
    for(int i = 0; i < q; i++){
        if(manage[i][0] == 1) {
            box.push_back(manage[i][1]);
        } else if(manage[i][0] == 2) {
            if(box.size()) {
                box.pop_front();
            } else {
                cout << "lan" << endl;
            }
        } else if(manage[i][0] == 3) {
            if(box.size()) {
                cout << *box.begin() << endl;
            } else {
                cout << "qiao" << endl;
            }
        } else {
            cout << box.size() << endl;
        }
    }
    return 0;
}

2.1_括号匹配（栈）

#include <iostream>
#include <stack>

using namespace std;

int main() {
    char c;
    cin >> c;
    stack<char> l;
    while(c != '@') {
        if(c == '(') {
            l.push(c);
        }
        if(c == ')') {
            if(l.size()) {
                l.pop();    
            } else {
                cout << "NO" << endl;
            }
        }
        cin >> c;
    }
    if(l.size()) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    return 0;
}

2.2_排列（手写）

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int* arr = new int[n];  
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int minValue = min(arr[i], arr[j]);
            bool flag = true;
            for (int k = i + 1; k < j; k++) {
                if (arr[k] >= minValue) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans += j - i + 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

2.3_深度优先搜索（DFS）

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> arrayList = {
    {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}
};

void dfs(int node, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : arrayList[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

int main() {
    vector<bool> visited(6, false);
    dfs(0, visited);
    return 0;
}

2.4_宽度优先搜索（BFS）

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> arrayList = {
    {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}
};

void bfs(int startNode, vector<bool>& visited) {
    queue<int> q;
    q.push(startNode);
    visited[startNode] = true;
    while (!q.empty()) {
        int current = q.front();
        cout << current << " ";
        q.pop();
        for (int neighbor : arrayList[current]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    vector<bool> visited(6, false); 
    bfs(0, visited);
    return 0;
}

3.1_数组、栈、队列、散列表

1.数组（Array）:
数组是一组相同类型的元素的集合。
数组的大小在创建时就被确定，且不能改变。
访问数组元素的时间复杂度是 O(1)。
2.栈（Stack）:
栈是一种后进先出（LIFO）的数据结构，即最后进入的元素最先被取出。
栈的操作包括推入（push）和弹出（pop）元素。
栈通常用于跟踪函数调用、表达式求值等。
3.队列（Queue）:
队列是一种先进先出（FIFO）的数据结构，即最先进入的元素最先被取出。
队列的操作包括入队（enqueue）和出队（dequeue）元素。
队列通常用于任务调度、宽度优先搜索等。
4.散列表（Hash）:
散列表是一种通过哈希函数将键映射到索引的数据结构，用于实现快速的查找、插入和删除操作。

#include <iostream>
#include <stack>
#include <queue>
#include <map>

using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4};
    cout << "Element: " << arr[0] << " " << arr[1] << " " << arr[2] << " " << arr[3] << endl;

    stack<int> s;
    s.push(1);  
    s.push(2);  
    s.push(3);  
    s.push(4); 
    s.pop();
    cout << "After s.pop(), top element: " << s.top() << endl;
    
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.pop();
    cout << "After q.pop(), front element: " << q.front() << endl;
    
    map<int, string> m;
    m[1] = "Alice";
    m[2] = "Bill";
    m[3] = "Charlie";
    m[4] = "David";
    cout << "User name of ID map[3]: " << m[3] << endl;
    return 0;
}

3.2_链表

链表是一种动态数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。
链表的大小可以动态调整，插入和删除元素的时间复杂度较低。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void deleteNode(Node*& head, int key) {
    Node* current = head;
    Node* prev = nullptr;
    while (current != nullptr && current->data != key) {
        prev = current;
        current = current->next;
    }
    if (current != nullptr) {
        if (prev != nullptr) {
            prev->next = current->next;
        } else {
            head = current->next;
        }
        delete current;
    }
}

void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    deleteNode(head, 3);
    cout << "After linked list delete Node3: ";
    printList(head);
    return 0;
}

3.3_树

树是一种分层的数据结构，由节点组成，其中每个节点都有零个或多个子节点。
二叉树是一种特殊的树，每个节点最多有两个子节点。

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    if (root->val != 0) {
        cout << root->val << " ";
    }
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    cout << "Binary tree preorderTraversal: ";
    preorderTraversal(root);
    return 0;
}

3.4_图

图是一组节点和节点之间的边的集合。
节点表示图中的实体，边表示这些实体之间的关系。
图可以是有向的或无向的，带权重的或无权重的。

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

class Graph {
public:
    int V; 
    vector<vector<int>> adjList; 
    Graph(int v) : V(v), adjList(v + 1) {}
    void addEdge(int i, int j) {
        adjList[i].push_back(j);
        adjList[j].push_back(i);
    }
    void displayGraph() {
        for (int i = 1; i <= V; ++i) {
            cout << "Vertex " << i << " is connected to: ";
            for (int neighbor : adjList[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph graph(4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.displayGraph();
    return 0;
}

3.5_堆

堆是一种特殊的树形数据结构，通常用于实现优先队列。
最小堆和最大堆是两种常见的堆类型。

#include <iostream>
#include <vector>

using namespace std;

class BinaryHeap {
private:
    vector<int> heap;
    void heapifyUp(int index) {         // 向上调整
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] < heap[parent]) {
                swap(heap[index], heap[parent]);
                index = parent;
            } else {
                break;
            }
        }
    }
    void heapifyDown(int index) {       // 向下调整
        int size = heap.size();
        while (index < size) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;
            if (leftChild < size && heap[leftChild] < heap[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < size && heap[rightChild] < heap[smallest]) {
                smallest = rightChild;
            }
            if (smallest != index) {
                swap(heap[index], heap[smallest]);
                index = smallest;
            } else {
                break;
            }
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }
    void extractMin() {
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }
    void printHeap() {
        cout << "Heap: ";
        for (int element : heap) {
            cout << element << " ";
        }
        cout << endl;
    }
};

int main() {
    BinaryHeap minHeap;
    minHeap.insert(3);
    minHeap.insert(1);
    minHeap.insert(4);
    minHeap.insert(1);
    minHeap.insert(5);
    minHeap.printHeap();  
    minHeap.extractMin();
    minHeap.printHeap();
    return 0;
}