题目资料：https://wwb.lanzouo.com/i8RQD1qfasof

Part_1 题目

43788 最大化股票交易的利润 OJ编程题 中等

【考点】考点主要涉及到贪心算法的思想。

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int res = -99999999;
    for(int i = 0; i < N - 1; i++) {
        for(int j = i + 1; j < N; j++) {
            if(A[j] - A[i] > res) {
                res = A[j] - A[i];
            }
        }
    }
    cout << res;
    return 0;
}

43792 求一个数字的数根 OJ编程题 中等

【考点】这个问题考察了递归的应用，以及对数学概念的理解。

#include <iostream>
using namespace std;

int root(int n) {
    int x = 0;
    while(n) {
        x += n % 10;
        n /= 10;
    }
    return x >= 10 ? root(x) : x;
}

int main() {
    int n;
    cin >> n;
    cout << root(n);
    return 0;
}

43793 确定一个数字是否为 2 的幂 OJ编程题 中等

【考点】考点是判断一个数字是否为2的幂。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while(n % 2 == 0 && n != 1) {
        n /= 2;
    }
    cout << (n == 1 ? "YES" : "NO");
    return 0;
}

43822 金币 OJ编程题 中等

【考点】利用了数学模型来解决问题，较为巧妙地求解了金币的数量问题。

#include <iostream>
using namespace std;

int main() {
    int K;
    cin >> K;
    int n = 1, temp = 1;
    while(temp < K) {
        n++;
        temp += n;
    }
    int res = 0;
    for(int i = 1; i < n; i++) {
        res += i * i;
    }
    cout << res + n * (K - temp + n);
    return 0;
}

43826 神奇的幻方 OJ编程题 中等

【考点】递归：代码使用递归的方式填充幻方，这是一个常见的编程技巧。
幻方的规则：通过特定的规则来填充幻方，这需要对幻方的性质有一定的了解。
【解题思路】
1.创建一个二维矩阵map，初始化为全0。
2.从矩阵的第一行中间位置开始，按照特定的规则填充数字，规则是在当前位置填充数字n，然后根据特定的条件选择下一个位置。
3.递归地填充矩阵，直到所有位置都被填充。

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

int K;
vector<vector<int>> map;

void fill_n(int x, int y, int n) {
    if(n == K * K) {
        return;
    }
    if(x == 0) {
        if(y == K - 1) {
            map[x + 1][y] = n;
            fill_n(x + 1, y, n + 1);
        } else {
            map[K - 1][y + 1] = n;
            fill_n(K - 1, y + 1, n + 1);            
        }
    } else if(y == K - 1) {
        map[x - 1][0] = n;
        fill_n(x - 1, 0, n + 1);
    } else {
        if(map[x - 1][y + 1] == 0) {
            map[x - 1][y + 1] = n;
            fill_n(x - 1, y + 1, n + 1);        
        } else {
            map[x + 1][y] = n;
            fill_n(x + 1, y, n + 1);            
        }
    }
}

int main() {
    cin >> K;
    if(K == 1) {
        cout << 1;
        return 0;
    }
    map.resize(K, vector<int>(K, 0));
    map[0][K / 2] = 1;
    fill_n(0, K / 2, 2);
    for(int i = 0; i < K; i++) {
        for(int j : map[i]) {
            cout << (j == 0 ? K * K : j) << " ";
        }
        cout << endl;
    }
    return 0;
}

43837 寻找道路 OJ编程题 困难

【考点】考察DFS的思想来遍历从起点到终点的所有可能路径，然后找到其中最长的一条。
【解题思路】
1.从起点开始，使用深度优先搜索（DFS）遍历所有可能的路径。
2.在每一步中，检查当前节点是否与终点相邻，如果是，则更新最长路径长度。
3.继续深度优先搜索，直到遍历完所有可能的路径。

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

int n, m, first, last;
int maxLenth = 0;
vector<vector<int>> map;

void res(int current, int lenth) {
    if(current == last - 1) {
        if(lenth > maxLenth) {
            maxLenth = lenth;
        }
        return;
    }
    for(int i = 0; i < n; i++) {
        if(map[current][i]) {
//          cout << "(" << current + 1 << "→" << i + 1 << ") ";
            map[current][i] = 0;
            res(i, lenth + 1);
        }
    }
}

int main() {
    cin >> n >> m;
    map.resize(n, vector<int>(n, 0));
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        map[x - 1][y - 1] = 1;
    }
    cin >> first >> last;
    res(first - 1, 0);
    cout << (maxLenth == 0 ? -1 : maxLenth); 
    return 0;
}

43838 计数问题 OJ编程题 中等

【考点】两层循环，外层循环遍历从1到n的所有整数，内层循环则是对每个整数的每一位进行遍历，检查是否等于给定的数字x。

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int res = 0;
    for(int i = 1; i <= n; i++) {
        int y = i;
        while(y){
            if(y % 10 == x) {
                res++;
            }
            y /= 10;
        }
    }
    cout << res;
    return 0;
}

43842 花匠 OJ编程题 中等

【考点】考察动态规划的思想。这个问题求一个数组中最长的起伏子序列长度。
【解题思路】
1.递归思路： 通过递归的方式，不断尝试扩展子序列，记录并更新最长子序列的长度。
2.动态规划： 可以将 maxLenth 视为动态规划数组的一部分，通过不断更新它来记录最优解。

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

int n;
int maxLenth = 1, flag = -1;
vector<int> h;

void res(int last, int current, int lenth) {
    if(current == n) {
        if(lenth > maxLenth) {
            maxLenth = lenth;
        }
        flag = -1;
        return;
    }
    if(h[current] < h[last] && flag != 0) {
        flag = 0;
        res(current, current + 1, lenth + 1);
    } else if(h[current] > h[last] && flag != 1) {
        flag = 1;
        res(current, current + 1, lenth + 1);       
    }
    res(last, current + 1, lenth);
}

int main() {
    cin >> n;
    h.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> h[i];
    }
    res(0, 1, 1);
    cout << maxLenth << endl;
    return 0;
}

43846 Vigenère 密码 OJ编程题 中等

【考点】凯撒密码是一种替换密码，通过将字母按照指定的偏移量进行移位来加密。在这里，通过从密文中减去相应密钥字母的偏移量来解密。
【解题思路】
1.对每个密文字符进行解密。解密过程中，需要根据密钥中的字母确定凯撒密码的偏移量，然后将密文字符减去相应的偏移量来得到明文字符。
2.考虑字母循环的情况，即如果减去偏移量后字符小于 'a'（或 'A'），则需要将其加上 26，使其循环到字母表的末尾。
3.将解密后的明文字符添加到结果字符串M中。

#include <iostream>
using namespace std;

int main() {
    string K, C, M;
    cin >> K >> C;
    int j = 0, len = K.size();
    for(int i = 0; i < C.size(); i++) {
        char k = K[j % len], c;
        if('a' <= k && k <= 'z') {
            c = C[i] - (k - 'a');
        } else {
            c = C[i] - (k - 'A');
        }
        if('A' <= C[i] && C[i] <= 'Z') {
            c += c < 'A' ? 26 : 0;
        } else {
            c += c < 'a' ? 26 : 0;
        }
        M.push_back(c);
        j++;
    }
    cout << M;
    return 0;
}

43850 数字反转 OJ编程题 中等

【考点】这道题考察了对字符串的操作、条件判断和循环的使用。
【解题思路】
1.如果N的第一个字符是负号（'-'），则结果字符串M的第一个字符也为负号;
2.然后从N的末尾开始遍历，逐个将非零字符添加到M中。这是为了去除反转后可能出现的开头零。
3.如果N的第一个字符不是负号，那么直接从N的末尾开始遍历，同样逐个将非零字符添加到M中。

#include <iostream>
using namespace std;

int main() {
    string N, M;
    cin >> N;
    if(N[0] == '-'){
        M.push_back('-');
        for(int i = N.size() - 1; i >= 1; i--) {
            if(!(N[i] == '0' && M.size() == 1)) {
                M.push_back(N[i]);
            }
        }
    } else {
        for(int i = N.size() - 1; i >= 0; i--) {
            if(!(N[i] == '0' && M.empty())) {
                M.push_back(N[i]);
            }
        }
    }
    cout << M;
    return 0;
}

Part_2 题目

OpenJ_Bailian-2749 分解因数

【考点】考点是分解因数，即将给定的整数分解为若干个素数的乘积。
【解题思路】
1.isOnly 函数用于判断一个数是否为素数。
通过循环从2到sqrt(b)+1的范围内，检查是否有能整除b的数。如果存在，则b不是素数；否则，b是素数。
2.Find 函数采用递归方式，寻找给定整数a的因数。
如果a是素数或者x大于y，则返回当前的结果result。
否则，检查是否可以整除a，如果是，则递归调用 Find 函数，将a除以x，并更新result。
然后递归调用 Find 函数，将x加1，继续寻找下一个因数。

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

bool isOnly(int b) {
    for(int i = 2; i < sqrt(b) + 1; i++) {
        if(b % i == 0) {
            return false;
        }
    }
    return true;
}

int Find(int a, int x, int y, int result) {
    if(isOnly(a) || x > y) {
//      if(x <= y) {
//          cout << a << endl;
//      }
        return result;
    } else {
        if(a % x == 0) {
//          if(!isOnly(a / x)) {
//              cout << x << " * " << a / x << endl;
//          }
//          cout << x << " * "; 
            result = Find(a / x, x, y, result + 1);
        }
        result = Find(a, x + 1, y, result); 
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> res(n);
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
//      cout << "所有情况：\n" << a << endl;
        res[i] = Find(a, 2, sqrt(a), 1);
    }
    for(int o : res) {
        cout << o << endl;
    }
    return 0;
}

OpenJ_Bailian-2797 最短前缀

【考点】字符串处理： 程序涉及对字符串的处理，包括字符串的截取、比较等。
【解题思路】
1.isOnly函数用于检查给定的字符串是否是数组中除了指定标志位置的字符串之外的所有字符串的前缀。
2.Find函数用于找到给定字符串的最短前缀。它通过遍历输入字符串的每个字符，并逐步构建前缀，然后调用isOnly函数检查该前缀是否满足条件。一旦找到满足条件的前缀，就立即返回该前缀。

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

vector<string> S;

bool isOnly(string x, int flag) {
    for(int i = 0; i < S.size(); i++) {
        string y;
        if(S[i].size() < x.size()) {
            continue;
        }
        if(i != flag) {
            for(int j = 0; j < x.size(); j++) {
                y.push_back(S[i][j]);
            }
        }
        if(x == y) {
            return false;
        }
    }
    return true;
}

string Find(string s, int flag) {
    string result;
    for(char c : s) {
        result.push_back(c);
        if(isOnly(result, flag)) {
            return result;
        }
    }
}

int main() {
    string s;
    getline(cin, s);
    while(!s.empty()) {
        S.push_back(s);
        getline(cin, s);
    }
    for(int i = 0; i < S.size(); i++) {
        cout << S[i] << " " << Find(S[i], i) << endl;
    }
    return 0;
}

OpenJ_Bailian-2755 神奇的口袋

【考点】考点是递归和深度优先搜索（DFS）。
【解题思路】
1.Find 函数接受两个参数：current 表示当前处理的物品下标，total 表示当前已选取物品的体积之和。
2.在每次调用 Find 函数时，会尝试将当前物品加入选取的物品集合，并递归调用 Find 函数来处理剩余的物品。当 total 等于目标体积40时，就将结果计数器 result 增加一次。
【解题思路2】
经典的通过位运算枚举所有可能的组合，然后通过条件判断确定符合要求的组合。（套路代码）

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

int result = 0, n;
vector<int> a;

void Find(int current, int total) {
    total += a[current];
    if(total == 40) {
        result++;
        return;
    }
    if(current + 1 == n) {
        return;
    }
    for(int i = current + 1; i < n; i++) {
        Find(i, total);
    }
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        a.push_back(ai);
    }
    for(int i = 0; i < n; i++) {
        Find(i, 0);
    }
    cout << result;
    return 0;
}

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

bool correct(string choice, vector<int>& a) {
    int money = 0;
    for(char c : choice) {
        money += a[c - '0'];
    }
    return money == 40 ? true : false;
} 

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    string str = "";
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        str.push_back('0' + i);
    }
    int count = 0;
    for(int i = 0; i < (1 << n); i++) { // 枚举所有情况
        string s;                       // 套路代码，类似第6题
        for(int j = 0; j < n; j++) {
            if(i & (1 << j)) {
                s.push_back(str[j]);
            }
        }
        if(correct(s, a)) {
            count++;
        }
    }
    cout << count;
    return 0;
}

OpenJ_Bailian-2738 实数加法

【考点】考察了对字符串处理和基本加法运算的理解，同时也考察了对于数组或向量的简单操作。
【解题思路】
1.输入处理：首先，通过输入获取两个实数的字符串表示。然后，从字符串中提取出整数部分和小数部分。整数部分直接转换为整数型变量，而小数部分则分别存储到两个向量中，以便后续的计算。
2.计算：接下来进行实数的加法运算。小数部分的加法是逐位进行的，从小数点后第一位开始直到最后一位，同时考虑进位。将两个小数部分对应位置的数字相加，加上前一位的进位，得到当前位的结果。进位则是除以10的商，结果取余数。这个过程需要从小数部分的末尾往前遍历，以保证进位的正确性。

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

int A = 0, B = 0, n;    // 整数部分
vector<int> x, y, z;    // 小数部分

void input() {
    string a, b;
    cin >> a >> b;
    int i = 0, j = 0;
    while(a[i] != '.'){
        A *= 10;
        A += a[i++] - '0';
    }
    while(b[j] != '.'){
        B *= 10;
        B += b[j++] - '0';
    }
    n = max(a.size() - i, b.size() - j) - 1;
    x.resize(n, 0);
    y.resize(n, 0);
    z.resize(n, 0);
    a.erase(0, i + 1);
    b.erase(0, j + 1);
    i = 0;
    for(char c : a) {
        if(c != '.') {
            x[i++] = c - '0';
        }
    }
    i = 0;
    for(char c : b) {
        if(c != '.') {
            y[i++] = c - '0';
        }
    }   
}

void calculate() {
    int carry = 0;
    for(int i = n - 1; i >= 0; i--) {
        int temp = x[i] + y[i] + carry;
        carry = temp / 10;
        z[i] = temp % 10;
    }
    cout << A + B + carry << ".";
    for(int o : z) {
        cout << o;
    }
}

int main() {
    input();
    calculate();
    return 0;
}

OpenJ_Bailian-2972 确定进制

【考点】考察了对进制转换的理解以及循环控制的运用。
【解题思路】
1.首先，确定一个起始的进制值 n，该值一般选取为 p 和 q 中较大的那个数，因为在这个进制下，p 和 q 的值会尽可能小。
2.然后，进入一个循环，不断尝试不同的进制值 n，直到找到满足条件的进制值。
3.在每一次循环中，将 p、q、r 分别转换为当前进制下的十进制数，然后判断是否满足条件。如果满足条件，则输出当前进制值 n 并退出循环。

#include <iostream>
using namespace std;

int pow(int k, int j) {
    if (j == 0) {
        return 1;
    }
    int y = k;
    for (int i = 0; i < j - 1; i++) {
        y *= k;
    }
    return y;
}

int change(int x, int k) {
    int res = 0, j = 0;
    while (x) {
        res += x % 10 * pow(k, j++);
        x /= 10;
    }
    return res;
}

int main() {
    int p, q, r;
    cin >> p >> q >> r;
    int n = max(p, q);
    while(1){
        // 将 n 进制转为 10 进制检验
        if (change(p, n) * change(q, n) == change(r, n)) {
            cout << n;
            break;
        }
        n++;
    }
    return 0;
}

OpenJ_Bailian-2814 拨钟问题

【考点】这道题是一个典型的搜索（搜索空间）和暴力枚举的问题，通常用于测试编程能力和逻辑思维。
【解题思路】
经典的通过位运算枚举所有可能的组合，然后通过条件判断确定符合要求的组合。（套路代码）
1.首先定义了一个9个元素的整数数组clock，表示每个钟的状态。
2.correct函数用于判断给定的拨动顺序是否能够将钟拨动到12点位置。
3.主函数中使用了一个嵌套的循环，对所有的可能的拨动顺序进行了枚举，然后通过correct函数来验证拨动顺序是否有效。在枚举拨动顺序时，使用了位运算来实现。利用了每个位上的0和1表示选择和不选择的含义，从而生成了所有可能的拨动顺序。

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

vector<string> choices = {
    "ABDE", "ABC", "BCEF",
    "ADG", "BDEFH", "CFI",
    "DEGH", "GHI", "EFHI"
};

bool correct(string s, vector<int>& clock) {
    for(int i = 0; i < s.length(); i++) {
        string choice = choices[s[i] - '0' - 1];
        for(char c : choice) {
            clock[c - 'A']++;
        }
    }
    for(int time : clock) { // 检验是否拨正
        if(time % 4 != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<int> clock(9);
    for(int i = 0; i < 9; i++) {
        cin >> clock[i];
    }
    string str = "123456789";
    for (int i = 0; i < (1 << 9); i++) { // 枚举所有情况
        string s;
        for (int j = 0; j < 9; j++) {
            if (i & (1 << j)) {
                s.push_back(str[j]);
            }
        }
        if(correct(s, clock)) {
            for(char c : s) {
                cout << c << " ";
            }
        }
    }
    return 0;
}

OpenJ_Bailian-2801 填词

【考点】主要是考察对DFS的理解和实现能力，以及对基本编程概念和C++语法的熟悉程度。
【解题思路】
1.深度优先搜索：findWord 函数实现了DFS算法。它在二维的字符矩阵 map 上进行搜索，寻找是否存在以给定字符串 word 开头的连续路径。在搜索过程中，通过递归的方式不断地向四个方向进行探索，直到找到完整的单词或者无法继续拼接为止。
2.回溯：如果在某个位置开始的路径不符合要求，就需要回溯到上一个位置重新尝试其他路径。这就是通过将 visited 数组来标记已经访问过的位置，并在 findWord 函数的末尾恢复为未访问状态来实现的。

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

int N, M, P;
vector<vector<char>> map;
vector<vector<int>> visited;

bool findWord(string word, int current, int j, int k) {
    visited[j][k] = 1;
    if(current == word.length() - 1) { // 找到单词了
        return true;
    }
    char next = word[current + 1];
    int a[4] = {-1, +1, 0, 0};
    int b[4] = {0, 0, -1, +1};
    for(int i = 0; i < 4; i++) { // 四个方向找
        if(0 <= j + a[i] && j + a[i] <= N && 0 <= k + b[i] && k + b[i] <= M) {
            if(!visited[j + a[i]][k + b[i]] && map[j + a[i]][k + b[i]] == next) {
                if(findWord(word, current + 1, j + a[i], k + b[i])) {
                    return true;
                }
            }           
        }
    }
    visited[j][k] = 0; // 没找到单词
    return false;
}

void input() {
    cin >> N >> M >> P;
    map.resize(N, vector<char> (M, 0));
    visited.resize(N, vector<int> (M, 0));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}

void resolution() {
    for(int i = 0; i < P; i++) {
        string word;
        cin >> word;
        for(int j = 0; j < N; j++) { // 找到首字母
            for(int k = 0; k < M; k++) {
                if(!visited[j][k] && map[j][k] == word[0] && findWord(word, 0, j, k)) {
                    goto next_word;
                }
            }
        }
        next_word: continue;
    }
}

void print() {
    string res;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(!visited[i][j]){
                res.push_back(map[i][j]);
            }
        }
    }
    sort(res.begin(), res.end());
    cout << res;
}

int main() {
    input();
    resolution();
    print();
    return 0;
}

OpenJ_Bailian-2775 文件结构“图”

【考点】涉及了一个文件系统的模拟和其内容的循环移动展示。
【解题思路】
1.数据结构：使用二维向量 vector<vector<string>> res 来表示文件系统的结构。外层向量 res 的每个元素表示一个目录，内层向量表示该目录下的文件和子目录。每个文件和目录的名字都存储为字符串。OUTPUT 是一个全局向量，用于存储最终的输出结果。
2.解析输入：在 resolution() 函数中，代码通过逐行读取输入来构建文件系统的结构。当读取到 * 时，表示一个数据集的结束；当读取到 # 时，表示所有数据集的结束。每次读取一个新的数据集之前，都会重置 res 和一些计数器，以准备存储新的文件系统结构。
3.文件系统构建：当读取到一个新的字符串时，根据字符串的内容以及其开头的字母来判断是文件还是目录，并将其存储在合适的位置。当读取到 ] 时，表示返回上一级目录，因此需要减少当前目录的层级。
4.输出文件系统：output() 函数负责将构建好的文件系统以特定的格式输出到 OUTPUT 向量中。该函数使用迭代方式来遍历文件系统的结构，并根据文件和目录的层级关系进行适当的缩进和展示。

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

vector<string> OUTPUT;

void output(vector<vector<string>>& res, int flag) {
    OUTPUT.push_back("\nDATA SET ");
    OUTPUT.push_back(to_string(flag++));
    OUTPUT.push_back(":\n");
    for(int j = 0; j < res.size(); j++) { // 文件名排序
        if(res[j][1][0] == 'f') {
            sort(res[j].begin() + 1, res[j].end());
        }
    }
    int x = 0, y = 0, p = 0;
    while(1) {
        for(int k = 0; k < p; k++) {
            OUTPUT.push_back("|     ");
        }
        OUTPUT.push_back(res[x][y]);
        OUTPUT.push_back("\n");
        if(x == 0 && y == res[0].size() - 1) { // 遍历结束
            break;
        }
        if(x < res.size() - 1 && y == 0) { // 未遍历到最里层目录
            x++;
            p++;
        } else {
            if(y < res[x].size() - 1) { // 未遍历到最末尾文件
                y++;
            } else if(x > 0) {
                y = 1;
                x--;
                p--;        
            }
        }
    }
}

void resolution() {
    string s;
    getline(cin, s);
    int i = 0, n = 1, flag = 1;
    while (s != "#") {
        vector<vector<string>> res(1, vector<string> (1, "ROOT"));
        while (s != "*") {
            if (s[0] == 'd') {
                i++;
                if(i + 1 > n) {
                    n = i + 1;
                    res.resize(n);
                }
            } else if (s == "]") {
                i--;
                getline(cin, s);
                continue;
            }
            res[i].push_back(s);
            getline(cin, s);
        }
//      for(int j = 0; j < n; j++) {
//          cout << j + 1 << "级目录：";
//          for(string o : res[j]) {
//              cout << o << " ";
//          }
//          cout << endl;
//      }
        output(res, flag);
        i = 0;
        n = 1;
        getline(cin, s);
    }
}

int main() {
    resolution();
    for(string s : OUTPUT) {
        cout << s;
    }
    return 0;
}

OpenJ_Bailian-2682 循环移动

【考点】主要考察了对deque（双端队列）的运用，以及如何实现数组的循环右移。
【解题思路】
使用deque是因为它支持在两端进行高效的插入和删除操作，而且可以很方便地模拟数组的循环移动。

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

int main() {
    int n, m;
    cin >> n >> m;
    deque<int> number(n);
    for(int i = 0; i < n; i++) {
        cin >> number[i];
    }
    m = m % n;
    for(int j = 0; j < m; j++) {
        number.push_front(number.back());
        number.pop_back();
    }
    for(int o : number) {
        cout << o << " ";
    }
    return 0;
}

OpenJ_Bailian-2973 Skew数

【考点】考点包括字符串操作、数学运算、循环结构。
【解题思路】
这个代码的主要思路是将输入的Skew数转换成十进制数。它通过迭代每个位上的数字，并根据Skew数的特性计算出对应位的十进制值，然后将所有位的十进制值相加，得到最终结果。算法的时间复杂度是O(n)，其中n是Skew数的位数。

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

int calculate(string n) {
    int result = 0;
    int len = n.size();
    for (int i = 1; i <= len; i++) {
        int a = n[len - i] - '0';
        if (a != 0) {
            int b = 2;
            for (int j = 0; j < i - 1; j++) {
                b *= 2;
            }
            result += a * (b - 1);
        }
    }
    return result;
}

int main() {
    string n;
    vector<int> res;
    while (cin >> n && n != "0") {
        res.push_back(calculate(n));
    }
    for (int o : res) {
        cout << o << endl;
    }
    return 0;
}

Part_3 题目

43852 表达式的值 OJ编程题 中等

【考点】主要考察了如何通过递归和回溯生成所有可能的表达式。使用栈来处理表达式中的运算符和数字，实现对表达式的计算。
【解题思路】（套路代码）
1.递归穷举： 通过 generate 函数递归生成所有可能的字符串，其中 s 存储数字，op 存储运算符。递归过程中，每次可以选择添加一个数字（'0' 或 '1'）或者添加一个运算符。
2.栈的应用： 在 correct 函数中使用两个栈 num 和 op，分别存储数字和运算符。遍历表达式字符，根据不同情况进行处理，包括数字入栈、左括号入栈、右括号出栈运算，以及处理运算符优先级。
3.运算函数 operate： 定义了运算函数，用于执行栈顶两个数字和栈顶运算符的运算，根据运算符是加法还是乘法，返回相应的结果。

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

int count = 0;

int operate(stack<int>& num, stack<char>& op) {
    int y = num.top();  num.pop();
    int x = num.top();  num.pop();
    char o = op.top();  op.pop();
    if (o == '+') {
        return (x == 0 && y == 0) ? 0 : 1;
    } else {
        return (x == 1 && y == 1) ? 1 : 0;
    }
}

bool correct(string expression) {
    stack<int> num;
    stack<char> op;
    for (char c : expression) {
        if (isdigit(c)) {
            num.push(c - '0');
        } else if (c == '(') {
            op.push(c);
        } else if (c == ')') {
            while (op.top() != '(') {
                num.push(operate(num, op));
            }
            op.pop(); // 弹出左括号
        } else {
            while (!op.empty() && op.top() != '('
            && ((c == '*' && op.top() == '+')
            ||  (c == '+' && op.top() == '+'))) {
                num.push(operate(num, op));
            }
            op.push(c);
        }
    }
    while (!op.empty()) {
        num.push(operate(num, op));
    }
    return !num.top();
}

void generate(int len, string s, string op) { // 遍历所有方案
    if(s.length() == len) {
        string expression;
        int i = 0;
        for(char c : op) {
            if(c != '(') {
                expression.push_back(s[i++]);
            }
            expression.push_back(c);
        }
        if(correct(expression)) {
            count++;
            cout << expression << endl;
        }
        return;
    }
    generate(len, s + '0', op);
    generate(len, s + '1', op);
}

int main() {
    int n;
    string op;
    cin >> n >> op;
    generate(n - 1, "", op);
    cout << count % 10007;
    return 0;
}

43856 数字统计 OJ编程题 中等

【考点】这个问题的关键在于对数字的分解和统计的理解，以及使用循环来处理每个数字的每一位。

#include <iostream>
using namespace std;

int occur_times(int x) {
    int count = 0;
    while(x){
        if(x % 10 == 2) {
            count++;
        }
        x /= 10;
    }
    return count;
}

int main() {
    int L, R;
    cin >> L >> R;
    int res = 0;
    for(int i = L; i <= R; i++) {
        res += occur_times(i);
    }
    cout << res;
    return 0;
}

43858 打印图形 OJ编程题 中等

【考点】利用递归不断地将图形分割成更小的部分，并在每个部分中绘制特定的图形，最终得到完整的图形。

#include <stdio.h>
#include <stdlib.h>

void show(char* buf, int w){
    int i,j;
    for(i=0; i<w; i++){
        for(j=0; j<w; j++){
            printf("%c", buf[i*w+j]==0? ' ' : 'o');
        }
        printf("\n");
    }
}

void draw(char* buf, int w, int x, int y, int size){
    if(size==1){
        buf[y*w+x] = 1;
        return;
    }
    
    int n = size / 3; //填空
    draw(buf, w, x, y, n);
    draw(buf, w, x-n, y ,n);
    draw(buf, w, x+n, y ,n);
    draw(buf, w, x, y-n ,n);
    draw(buf, w, x, y+n ,n);
}

int main()
{
    int N ;
    scanf("%d",&N);
    int t = 1;
    int i;
    for(i=0; i<N; i++) t *= 3;
    char* buf = (char*)malloc(t*t);
    for(i=0; i<t*t; i++) buf[i] = 0;
    draw(buf, t, t/2, t/2, t);
    show(buf, t);
    free(buf);
    return 0;
}

43946 成绩统计 OJ编程题 中等

【考点】浮点数的精度控制；百分比的计算和四舍五入处理。

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    double a = 0, b = 0;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a += x >= 60 ? 1 : 0;
        b += x >= 85 ? 1 : 0;
    }
    cout << fixed << setprecision(0) << round(a / n * 100) << "%\n";
    cout << fixed << setprecision(0) << round(b / n * 100) << "%\n";
    return 0;
}

43950 装饰珠 OJ编程题 中等

【考点】使用动态规划来解决，并且需要注意状态的定义和状态转移方程的设计。
【解题思路】（套路代码）
1.输入处理：首先，读取珠宝盒中不同类型珠宝的数量以及每种珠宝的数量，以及每种珠宝的信息（包括种类、等级和价值）。
2.递归穷举：通过递归函数 resolution 来穷举所有可能的珠宝组合。该函数会遍历每种珠宝的数量，生成不同的组合，并将其传递给 calculate 函数进行价值计算。
3.价值计算：在 calculate 函数中，对传入的字符串进行排序，然后遍历统计每种珠宝的数量，根据珠宝的等级和数量来计算总价值。

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

vector<int> box;
vector<vector<int>> pearl;
int maxMoney = 0;

void calculate(string s) {
    int money = 0;
    sort(s.begin(), s.end());
    int i = 0;
    while(i < s.length()) { // 计算各种装饰珠价值
        char c = s[i];
        int count = 0;
        while(s[i] == c){
            count++;
            i++;
        }
        for(int j = 0; j < pearl.size(); j++) { // 计算该种装饰珠价值
            if(pearl[j][0] == c - '0') {
                if(count > pearl[j].size() - 1) {
                    money += pearl[j].back();
                } else {
                    money += pearl[j][count];
                }
            }
        }
    }
    cout << s << " money: " << money << endl;
    if(money > maxMoney)
        maxMoney = money;
}

void resolution(vector<int>& box2, int i, int len, string s) {
    if(s.length() == len) {
        calculate(s);
        return;
    }
    for(int j = 1; j <= box2[i]; j++) {
        resolution(box2, i + 1, len, s + char('0' + j));
    }
}

void input() {
    for(int i = 0; i < 6; i++) {
        int n;
        cin >> n;
        for(int j = 0; j < n; j++) {
            int x;
            cin >> x;
            box.push_back(x);
        }
    }
    int m;
    cin >> m;
    pearl.resize(m);
    for(int i = 0; i < m; i++) {
        int L, P;
        cin >> L >> P;
        pearl[i].resize(P + 1);
        pearl[i][0] = L;
        for(int j = 0; j < P; j++) {
            cin >> pearl[i][j + 1];
        }
    }
    resolution(box, 0, box.size(), ""); // 遍历所有情况
}

int main() {
    input();
    cout << maxMoney;
    return 0;
}

43951 导弹拦截 OJ编程题 中等

【考点】几何算法中的点到圆心的距离计算和条件判断。
【解题思路】
1.导弹拦截条件判断：对于每一个导弹的坐标 ((x, y))，需要判断它是否能被拦截。如果一个导弹位于两个拦截器的覆盖范围内，那么就需要判断它离哪个拦截器更近，然后更新对应拦截器的覆盖范围半径。
2.更新拦截器的覆盖范围半径：对于每一个导弹，判断它是否位于两个拦截器的覆盖范围内。如果是，则比较该导弹到两个拦截器的距离，将距离较大的那个导弹的距离赋值给对应的拦截器的覆盖范围半径。

#include <iostream>
using namespace std;

int x1, y1, x2, y2;
int r2_1 = 0, r2_2 = 0;

void calculate(int x, int y) {
    int d2_1 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
    int d2_2 = (x - x2) * (x - x2) + (y - y2) * (y - y2);
    if(d2_1 > r2_1 && d2_2 > r2_2) {
        d2_1 <= d2_2 ? r2_1 = d2_1 : r2_2 = d2_2;
    }
}

int main() {
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        calculate(x, y);
    }
    cout << r2_1 + r2_2;
    return 0;
}

43953 机器翻译 OJ编程题 中等

【考点】对双端队列（deque）的理解以及查找算法（find函数）的运用。
【解题思路】
1.队列（deque）： deque是一种双端队列，允许在队列的前端和后端进行插入和删除操作。在这道题中，deque用来模拟一个固定大小为M的容器，存储最近输入的M个元素。
2.查找算法： 通过使用STL提供的find函数，检查输入的元素是否在队列中已经存在。如果元素不存在，则将其加入队列。如果队列已满，则需要将队列的第一个元素移出，以便为新元素腾出空间。

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

int main() {
    deque<int> box;
    int M, N;
    cin >> M >> N;
    int count = 0;
    for(int i = 0; i < N; i++) {
        int word;
        cin >> word;
        if(find(box.begin(), box.end(), word) == box.end()) {
            if(box.size() == M) { // 没查到，且装满了
                box.pop_front();
            }
            box.push_back(word); // 没查到，且没装满
            count++;
        }
    }
    cout << count;
    return 0;
}

43955 关押罪犯 OJ编程题 中等

【考点】罪犯关押问题可以被抽象成一个图，每个罪犯是图中的一个节点，而每一条边上的权重是积怨值。问题的目标是找出构成环的最大权重边。
【解题思路】
1.将边按权重降序排序，可以使用 sort 函数，排序的比较函数是 bigger。
2.使用并查集来维护节点所在集合，初始化每个节点为一个单独的集合。
3.遍历排序后的边，对于每一条边，判断其两个节点是否在同一个集合中。如果在同一个集合中，说明加入这条边会形成环，输出该边的权重即可。如果不在同一个集合中，将这两个节点所在的集合合并。

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

int e[20010], pre[20010];

bool bigger(vector<int>& h1, vector<int>& h2) {
    return h1[2] > h2[2];
}

int find(int x) {
    if (x == pre[x])
        return x;   
    pre[x] = find(pre[x]);
    return pre[x];
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> h(100010, vector<int> (3));
    for (int i = 0; i < M; i++) {
        cin >> h[i][0] >> h[i][1] >> h[i][2];
    }
    sort(h.begin(), h.end(), bigger);
    for (int i = 0; i < 20010; i++) {
        pre[i] = i;
    }
    for (int i = 0; i < M; i++) {
        int a = h[i][0], b = h[i][1];
        if (find(a) == find(b)) {
            cout << h[i][2] << endl;
            return 0;
        }
        e[a] == 0 ? e[a] = b : pre[find(b)] = find(e[a]);
        e[b] == 0 ? e[b] = a : pre[find(a)] = find(e[b]);
    }
    return 0;
}

Part_4 题目

浮点数求高精度幂 OpenJ_Bailian - 2951

【考点】
1.高精度计算：题目要求实现浮点数的高精度幂运算，这涉及到对大整数的乘法和浮点数的处理。
2.字符串处理：需要对输入的浮点数进行处理，去除小数点并进行高精度计算。
3.循环和逻辑控制：使用循环来进行乘法运算和对结果进行修正。
【解题思路】
1.实现大整数乘法函数：实现一个函数 multiply(string x, string y) 来计算两个大整数字符串的乘积。这里采用类似手工乘法的方法，按位相乘然后进位求和。
2.大整数转换为浮点数：实现一个函数 fix(string s, string R, int n)，将大整数转换为浮点数。这里根据乘方的结果长度和给定的小数点位置进行修正，使结果保持正确的小数点位置和精度。
3.主程序：在 main 函数中，循环读入浮点数和幂数，并使用上述函数进行高精度幂运算和结果修正，然后将结果输出。

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

string multiply(string x, string y) {   // 大整数运算
    string a, b;
    for(char c : x) {
        if(c != '.') a.push_back(c);
    }
    for(char d : y) {
        if(d != '.') b.push_back(d);
    }
    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 c;
    for (int x : result) {
        if (!(c.empty() && x == 0)) { // 避免前导零
            c.push_back(x + '0');
        }
    }
    return c;
}

string fix(string s, string R, int n) {
    int count = 5;
    for(char c : R) {
        if(c != '.') {
            count--;
        } else {
            break;
        }
    }
    int right = count * n;
    string result;
    if(s.length() > right) {
        int left = s.length() - right;
        for(int i = 0; i < s.length(); i++) {
            if(i == left){
                result.push_back('.');
            }
            result.push_back(s[i]);
        }
    } else {
        result.push_back('.');
        for(int i = 0; i < right - s.length(); i++) {
            result.push_back('0');
        }
        for(char c : s) {
            result.push_back(c);    
        }
    }
    while(1){
        if(result[result.length() - 1] == '0'){ // 去除末尾零
            result.pop_back();
        } else {
            break;
        }
    }
    return result;
}

int main() {
    vector<string> res;
    string R;
    int n;
    for(int i = 0; i < 6; i++) {
        cin >> R >> n;
        string temp = R;
        for(int j = 0; j < n - 1; j++) {
            temp = multiply(temp, R);
        }
        res.push_back(fix(temp, R, n)); // 大整数变浮点数
    }
    for(string o : res) {
        cout << o << endl;
    }
    return 0;
}

小白鼠排队 OpenJ_Bailian - 2943

【考点】
1.字符串转换为整数的方法：在 weight 函数中，通过迭代字符串中的每个字符，将字符转换为数字，并构建出对应的整数。这是一种常见的字符串转整数的方法，通过逐位相加构建整数。
2.自定义排序函数：bigger 函数是自定义的比较函数，用于在 sort 函数中排序小白鼠的数组。这里比较的是小白鼠的编号，而编号是通过 weight 函数转换成整数后进行比较的。这展示了如何使用自定义的比较函数进行复杂对象的排序。
3.二维向量的使用：vector<vector<string>> mouse(N, vector<string>(2)) 创建了一个二维向量，用于存储小白鼠的编号和重量。这样的数据结构使得对每只小白鼠的信息能够方便地进行管理。
【解题思路】
1.通过 weight 函数将字符串编号转换为整数，以便进行比较。
2.使用自定义的比较函数 bigger 对小白鼠进行排序，排序的依据是编号的整数值。
3.最后通过循环输出排序后的小白鼠编号。

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

int weight(string s) {
    int w = 0;
    for(int i = s.length() - 1; i >= 0; i--) {
        w *= 10;
        w += s[i] - '0';
    }
    return w;
}

bool bigger(vector<string> m1, vector<string> m2) {
    return weight(m1[0]) > weight(m2[0]);
}

int main() {
    int N;
    cin >> N;
    vector<vector<string>> mouse(N, vector<string> (2));
    for(int i = 0; i < N; i++) {
        cin >> mouse[i][0] >> mouse[i][1];
    }
    sort(mouse.begin(), mouse.end(), bigger);
    for(int i = 0; i < N; i++) {
        cout << mouse[i][1] << endl;
    }
    return 0;
}

最大子矩阵 OpenJ_Bailian - 2766

【考点】
1.时间复杂度：考察了算法的时间复杂度。暴力解法的时间复杂度为 O(N^4)，对于较大的矩阵可能会很慢，而动态规划解法的时间复杂度为 O(N^3)，更加高效。
2.空间复杂度：考察了算法的空间复杂度。暴力解法只需要额外的常数级空间，而动态规划解法需要一个额外的二维数组来存储中间结果，因此空间复杂度稍高。
【解题思路】
1.暴力解法：通过遍历矩阵中的所有可能的子矩阵，并计算它们的总和，然后比较找出最大的总和。具体做法是使用四重循环，遍历所有可能的子矩阵的左上角和右下角的坐标，然后调用 calculate 函数计算这个子矩阵的总和，更新最大总和。
2.动态规划解法：基本思想是，维护一个额外的二维数组，用来记录以当前元素为右下角的所有子矩阵的最大总和。然后通过递推公式来更新这个数组。这种方法的时间复杂度为 O(N^3)。

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

vector<vector<int>> matrix;

int calculate(int x, int y, int x2, int y2, int maxTotal) {
    int total = 0;
    for(int i = x; i <= x2; i++) {
        for(int j = y; j <= y2; j++) {
            total += matrix[i][j];
        }
    }
    return total > maxTotal ? total : maxTotal;
}

int main() {
    int N;
    cin >> N;
    matrix.resize(N, vector<int>(N));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> matrix[i][j];
        }
    }
    int maxTotal = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            for(int m = i; m < N; m++) {
                for(int n = j; n < N; n++) {
                    maxTotal = calculate(i, j, m, n, maxTotal);
                }
            }
        }
    }
    cout << maxTotal;
    return 0;
}

排列 OpenJ_Bailian - 1833

【考点】
1.排列算法： 使用了next_permutation函数，该函数是C++标准库中提供的用于生成下一个排列的函数。它通过重排容器中的元素来生成所有可能的排列。
2.循环控制： 使用了do-while循环，通过对next_permutation的反复调用来生成多个排列。
3.函数设计： resolution函数的设计，包括函数参数的合理选择和返回值的处理。
【解题思路】
1.输入处理： 通过cin获取整体测试用例的数量（m），然后循环处理每个测试用例。
2.测试用例处理： 对于每个测试用例，获取排列长度（n）和排列中要移动的位置数（k）。
3.排列生成： 使用next_permutation生成排列序列，并在循环中执行k次，相当于将排列序列后移k次。

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

vector<int> resolution(int k, vector<int> arr) {
    int i = 0;
    do {    
        if (++i > k) break;
    } while(next_permutation(arr.begin(), arr.end()));
    return arr; // 后移序列
}

int main() {
    int m;
    cin >> m;
    vector<vector<int>> res;
    for(int i = 0; i < m; i++) {
        int n, k;
        cin >> n >> k;
        vector<int> arr(n); // 当前序列
        for(int j = 0; j < n; j++) {
            cin >> arr[j];
        }
        res.push_back(resolution(k, arr));
    }
    for(vector<int> o : res) {
        for(int c : o) {
            cout << c << " ";
        }
        cout << endl;
    }
    return 0;
}

求矩阵的加法 OpenJ_Bailian - 2870

【考点】涉及到的是数组与循环的使用，以及将矩阵相加并输出结果。

#include <iostream>
using namespace std;

int main() {
    int a[3][3], b[3][3];
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> b[i][j];
        }
    }
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cout << a[i][j] + b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

字符串排序 OpenJ_Bailian - 2915

【考点】
1.字符串排序： 这个题目要求对输入的字符串列表进行排序，排序的规则是按字符串长度从小到大排序。这需要定义一个比较函数 smaller，其功能是比较两个字符串的长度，根据长度来确定它们的顺序。在C++中，可以使用 std::sort 函数来排序容器中的元素，通过传递自定义的比较函数 smaller 来实现按照自定义规则排序。
2.向量的使用： 代码中使用了嵌套的二维向量 vector<vector<string>> 来存储输入的多个字符串列表。在每次输入完成后，将当前字符串列表排序，并将其存储到二维向量 res 中，最终输出排序后的结果。
【解题思路】
1.定义比较函数 smaller，用于按字符串长度排序。使用一个嵌套的二维向量 res 存储所有输入的字符串列表。
2.在每次输入字符串列表时，使用一个内部循环读取字符串，直到遇到 "stop" 为止，将读取的字符串存储到一个临时向量 S 中。
3.对临时向量 S 进行排序，排序规则是按照字符串长度从小到大。将排序后的字符串列表 S 存储到二维向量 res 中。
4.如果输入结束（即已经读取了 n 个字符串列表），则退出循环。最后，遍历二维向量 res，输出其中每个字符串列表中的字符串。

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

bool smaller(string s1, string s2) {
    return s1.length() < s2.length();
}

int main() {
    vector<vector<string>> res;
    int n;
    while(cin >> n){
        cin.ignore(); // 清除换行符
        vector<string> S;
        int i = 0;
        for( ; i < n; i++) {
            string s;
            getline(cin, s);
            if(s == "stop") {
                break;
            } else {
                S.push_back(s);
            }
        }
        sort(S.begin(), S.end(), smaller);
        res.push_back(S);
        if(i == n){ // 输入结束
            break;
        }
    }
    for(int i = 0; i < res.size(); i++) {
        for(string o : res[i]) {
            cout << o << endl;
        }
    }
    return 0;
}

打印极值点下标 OpenJ_Bailian - 2691

【考点】考点主要是理解极值点的概念以及在给定数组中找到极值点的方法。
【解题思路】
1.读取输入：首先，从标准输入读取一个整数n，表示测试用例的数量。然后对于每个测试用例，读取一个整数k，表示该用例中数组的长度。接着读取k个整数，表示数组的元素。
2.寻找极值点：遍历数组，对于每个元素，检查其与相邻元素的关系，如果其与前后元素的差乘积大于0，则说明该点为极值点。特别处理首尾元素，因为它们只有一个相邻元素。
3.存储结果：将找到的极值点的下标存入一个新的数组中，然后将这个数组存入结果数组result中。
4.输出结果：遍历结果数组，对于每个测试用例，输出其中的极值点下标。

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

int main() {
    vector<vector<int>> result;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        vector<int> arr(k);
        for(int j = 0; j < k; j++) {
            cin >> arr[j];
        }
        vector<int> res; // 找到极值点，存入res
        if(arr[0] != arr[1]) {
            res.push_back(0);
        }
        for(int j = 1; j < k - 1; j++) {
            if((arr[j - 1] - arr[j]) * (arr[j + 1] - arr[j]) > 0) {
                res.push_back(j);
            }
        }
        if(arr[k - 2] != arr[k - 1]) {
            res.push_back(k - 1);
        }
        result.push_back(res);
    }
    for(int i = 0; i < result.size(); i++) {
        for(int o : result[i]) {
            cout << o << " ";
        }
        cout << endl;
    }
    return 0;
}

圣诞老人的礼物-Santa Clau's Gifts OpenJ_Bailian - 4110

【考点】考点主要涉及到贪心算法和排序。
【解题思路】
1.输入：首先，从标准输入读取两个整数n和w，分别表示礼物的数量和圣诞老人的背包容量。然后，读取n组数据，每组数据包含两个实数，分别表示礼物的价值和重量。
2.排序：接下来，将读取的礼物数据按照性价比（即价值与重量的比值）进行排序。这里使用自定义的比较函数compare，按照性价比从高到低进行排序。这一步是为了优先选择性价比高的礼物。
3.贪心选择：接下来，使用贪心算法选择礼物。从性价比最高的礼物开始遍历，依次将礼物放入背包中，直到背包容量超过限制为止。对于每一个礼物，如果能够全部放入背包，则直接将其价值加到总价值中；否则，按照比例将其部分放入背包，并且计算此时的总价值。最后输出总价值。

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

bool compare(vector<double> g1, vector<double> g2) {
    return g1[0] / g1[1] > g2[0] / g2[1];
}

int main() {
    int n, w;
    cin >> n >> w;
    vector<vector<double>> gift(n, vector<double> (2));
    for(int i = 0; i < n; i++) {
        cin >> gift[i][0] >> gift[i][1];
    }
    sort(gift.begin(), gift.end(), compare); // 按性价比排序
    double count = 0, value = 0;
    for(int i = 0; i < n; i++) { // 统计价值
        count += gift[i][1];
        if(count <= w){
            value += gift[i][0];
        } else {
            value += (w - count + gift[i][1]) * (gift[i][0] / gift[i][1]);
            break;
        }
    }
    printf("%.1f", value);
    return 0;
}

踩方格 OpenJ_Bailian - 4103

【考点】考点主要涉及递归和深度优先搜索（DFS）。
【解题思路】
1.定义一个二维布尔数组 map，表示方格的状态，初始状态都为 false，表示未被踩过。从中心点 (20, 20) 开始进行搜索，假设方格的大小为 21x41，这样可以保证搜索不会越界。
2.编写递归函数 letsGo，参数包括当前方格的坐标 (x, y)、当前已经踩过的方格数量 n。
3.在每个方格进行搜索时，首先将当前方格标记为已踩过，然后检查其上、左、右是否可以前进，如果可以，则递归调用 letsGo 函数。当已踩过的方格数量等于总方格数量时，表示已经完成一次踩方格的操作，将计数器 count 自增。

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

int count = 0, N;

void letsGo(vector<vector<bool>>& map, int x, int y, int n) {
    if(n + 1 == N){
        count++;
        return;
    }
    map[x][y] = true;
    n++;
    if(y - 1 >= 0 && !map[x][y - 1]){
        letsGo(map, x, y - 1, n);
    }
    if(y + 1 < 41 && !map[x][y + 1]){
        letsGo(map, x, y + 1, n);
    }
    if(x - 1 >= 0 && !map[x - 1][y]){
        letsGo(map, x - 1, y, n);
    }
}

int main() {
    vector<vector<bool>> map(21, vector<bool> (41, false));
    cin >> N;
    letsGo(map, 20, 20, -1);
    cout << count;
    return 0;
}

集合加法 OpenJ_Bailian - 2792

【考点】考点主要是集合操作和算法复杂度。
【解题思路】
1.输入：首先从标准输入读取一个整数n，表示有n组测试数据。然后对于每组测试数据，先读取一个整数s，表示目标和；然后分别读取两个整数a和b，表示两个集合的大小；接着分别读取a和b个整数，表示两个集合中的元素。
2.集合加法：对于每组测试数据，需要找出两个集合中的元素相加等于目标和s的情况有多少种。为了解决这个问题，首先对两个集合进行排序，这样可以减少后续的搜索复杂度。然后使用两层循环遍历集合A和集合B的所有元素，分别计算它们的和，如果等于目标和s，则计数器加一；如果和大于目标和s，则直接退出内层循环，因为集合已经排序，后面的元素和一定更大。
3.输出：将每组测试数据的计数结果存储在一个向量中，然后在所有测试数据处理完毕后，依次输出每组测试数据的计数结果。

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

int main() {
    vector<int> res;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int s, a, b;
        cin >> s >> a;
        vector<int> A(a);
        for(int j = 0; j < a; j++) {
            cin >> A[j]; // 输入集合
        }
        cin >> b;
        vector<int> B(b);
        for(int j = 0; j < b; j++) {
            cin >> B[j];
        }
        sort(A.begin(), A.end()); // 排序，减少复杂度
        sort(B.begin(), B.end());
        int count = 0;
        for(int ai : A) {
            for(int bj : B) {
                if(ai + bj == s) {
                    count++;
                } else if(ai + bj > s) {
                    break;
                }
            }
        }
        res.push_back(count);
    }
    for(int x : res) {
        cout << x << endl;
    }
    return 0;
}