1.ABC三人分别向骆驼身上加稻草，A加1，B加1，C加的稻草是AB之和，然后A加的稻草是BC之和，B加的稻草是AC之和，输入一个值为骆驼能承受的极限值，输出一个值为谁压死的骆驼.

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

int main() {
    cout << "=== 最后一根稻草压死骆驼问题 ===" << endl;
    
    int limit;
    cout << "请输入骆驼能承受的极限重量: ";
    cin >> limit;
    
    // 初始重量
    int total_weight = 0;
    int round = 1;  // 轮次计数
    
    // A、B、C三人每轮添加的稻草重量
    int a_add = 1;  // A初始加1
    int b_add = 1;  // B初始加1
    int c_add = 2;  // C初始加2（A+B=1+1=2）
    
    cout << "\n=== 加稻草过程 ===" << endl;
    cout << "极限重量: " << limit << endl;
    cout << "轮次\tA加\tB加\tC加\t当前总重\t状态" << endl;
    cout << "--------------------------------------------" << endl;
    
    while (true) {
        // A加稻草
        total_weight += a_add;
        cout << round << "\t" << a_add << "\t-\t-\t" << total_weight;
        if (total_weight > limit) {
            cout << "\t骆驼死亡！" << endl;
            cout << "\n*** 结果：A压死了骆驼！***" << endl;
            cout << "A加了 " << a_add << " 根稻草后，总重量达到 " << total_weight 
                 << "，超过极限 " << limit << endl;
            return 0;
        }
        cout << "\t正常" << endl;
        
        // B加稻草
        total_weight += b_add;
        cout << "\t-\t" << b_add << "\t-\t" << total_weight;
        if (total_weight > limit) {
            cout << "\t骆驼死亡！" << endl;
            cout << "\n*** 结果：B压死了骆驼！***" << endl;
            cout << "B加了 " << b_add << " 根稻草后，总重量达到 " << total_weight 
                 << "，超过极限 " << limit << endl;
            return 0;
        }
        cout << "\t正常" << endl;
        
        // C加稻草
        total_weight += c_add;
        cout << "\t-\t-\t" << c_add << "\t" << total_weight;
        if (total_weight > limit) {
            cout << "\t骆驼死亡！" << endl;
            cout << "\n*** 结果：C压死了骆驼！***" << endl;
            cout << "C加了 " << c_add << " 根稻草后，总重量达到 " << total_weight 
                 << "，超过极限 " << limit << endl;
            return 0;
        }
        cout << "\t正常" << endl;
        
        // 计算下一轮每人要加的稻草数量
        int next_a = b_add + c_add;  // A下轮加的 = 本轮B加的 + 本轮C加的
        int next_b = a_add + c_add;  // B下轮加的 = 本轮A加的 + 本轮C加的
        int next_c = a_add + b_add;  // C下轮加的 = 本轮A加的 + 本轮B加的
        
        a_add = next_a;
        b_add = next_b;
        c_add = next_c;
        
        round++;
        
        // 防止无限循环（如果极限值太大）
        if (round > 20) {
            cout << "\n注意：计算轮次过多，可能极限值设置过大！" << endl;
            break;
        }
    }
    
    return 0;
}

2.有面值为 1元、5元、10元、20元、50元的纸币,分别有 n1、n5、n10、n20、n50 张,现在要用这些钱来支付 M 元,求：至少要用多少张纸币？

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

int minBanknotes(int M, int n1, int n5, int n10, int n20, int n50) {
    // 面值数组（从大到小）
    vector<int> values = {50, 20, 10, 5, 1};
    // 对应的张数
    vector<int> counts = {n50, n20, n10, n5, n1};
    
    int totalBanknotes = 0;
    int remaining = M;
    
    // 贪心算法：优先使用大面值
    for (int i = 0; i < 5; i++) {
        if (remaining <= 0) break;
        
        // 计算当前面值最多能用多少张
        int useCount = min(remaining / values[i], counts[i]);
        
        totalBanknotes += useCount;
        remaining -= useCount * values[i];
    }
    
    // 检查是否能完全支付
    if (remaining > 0) {
        return -1; // 无法支付
    }
    
    return totalBanknotes;
}

int main() {
    int M, n1, n5, n10, n20, n50;
    
    cout << "请输入要支付的金额M: ";
    cin >> M;
    
    cout << "请输入各面值纸币的张数:" << endl;
    cout << "1元张数: "; cin >> n1;
    cout << "5元张数: "; cin >> n5;
    cout << "10元张数: "; cin >> n10;
    cout << "20元张数: "; cin >> n20;
    cout << "50元张数: "; cin >> n50;
    
    int result = minBanknotes(M, n1, n5, n10, n20, n50);
    
    if (result == -1) {
        cout << "无法支付" << M << "元" << endl;
    } else {
        cout << "支付" << M << "元至少需要" << result << "张纸币" << endl;
    }
    
    return 0;
}

3.Shopee算法团队团建游戏问题：

给定两个长度相同的20位以内数字串num1和num2，需要在10秒内分析并返回格式为"xAyB"的字符串，其中：

A：num2中有多少位数字和num1完全一致（数字相同且位置相同）
B：num2中有多少位数字在num1中存在，但位置不对

规则说明：

xA表示num2有x位数字在num1中且位置一致
yB表示num2有y位数字在num1中但位置不一致
每位数字只能统计一次
两个数字串可能包含重复数字

示例：

示例1：num1="1807", num2="7810" → 输出"1A3B"
示例2：num1="1123", num2="0111" → 输出"1A1B"

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

string analyzeNumbers(string num1, string num2) {
    int n = num1.length();
    int A = 0; // 位置和数字都正确的个数
    int B = 0; // 数字正确但位置错误的个数
    
    // 统计每个数字在num1和num2中的出现次数（排除已经A匹配的）
    vector<int> count1(10, 0); // num1中各数字的计数
    vector<int> count2(10, 0); // num2中各数字的计数
    
    // 第一遍：统计A（位置和数字都正确）
    for (int i = 0; i < n; i++) {
        if (num1[i] == num2[i]) {
            A++;
        } else {
            // 只有位置不匹配的才加入计数
            count1[num1[i] - '0']++;
            count2[num2[i] - '0']++;
        }
    }
    
    // 第二遍：统计B（数字正确但位置错误）
    for (int digit = 0; digit <= 9; digit++) {
        // 对于每个数字，B的贡献是两个计数的最小值
        B += min(count1[digit], count2[digit]);
    }
    
    return to_string(A) + "A" + to_string(B) + "B";
}

int main() {
    string num1, num2;
    
    cout << "请输入num1: ";
    cin >> num1;
    cout << "请输入num2: ";
    cin >> num2;
    
    string result = analyzeNumbers(num1, num2);
    cout << "输出: " << result << endl;
    
    // 测试示例
    cout << "\n测试示例:" << endl;
    cout << "示例1: " << analyzeNumbers("1807", "7810") << endl; // 应输出1A3B
    cout << "示例2: " << analyzeNumbers("1123", "0111") << endl; // 应输出1A1B
    
    return 0;
}

4.方格游戏

起点：左上角(1,1)，初始能量 = grid[0][0]的值
移动规则：只能向右或向下，每步消耗1点能量
能量机制：到达新位置时，能量直接变为该位置的数值（不是累加！）
约束条件：移动前必须保证当前能量 ≥ 1（够支付移动成本）
目标：计算所有能到达终点的路径数量

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

int count_valid_paths(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    
    // dp[i][j] 表示能够到达位置(i,j)的路径数量
    vector<vector<int>> dp(n, vector<int>(m, 0));
    
    // 起点
    dp[0][0] = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dp[i][j] == 0) {  // 当前位置不可达
                continue;
            }
            
            int current_energy = grid[i][j];
            
            // 尝试向右走
            if (j + 1 < m) {
                // 检查能量是否足够走到下一步
                if (current_energy >= 1) {  // 能量够走一步
                    dp[i][j+1] += dp[i][j];
                }
            }
            
            // 尝试向下走
            if (i + 1 < n) {
                // 检查能量是否足够走到下一步
                if (current_energy >= 1) {  // 能量够走一步
                    dp[i+1][j] += dp[i][j];
                }
            }
        }
    }
    
    return dp[n-1][m-1] % 10000;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<vector<int>> grid(n, vector<int>(m));//二维容器
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> grid[i][j];
            }
        }
        
        int result = count_valid_paths(grid);
        cout << result << endl;
    }
    
    return 0;
}

举个具体例子：

假设网格是：

复制代码

2 1
1 0

执行过程：

初始化：dp = [[0,0], [0,0]]
设置起点：dp[0][0] = 1，现在 dp = [[1,0], [0,0]]
处理 (0,0)：
- 向右走：dp[0][1] += dp[0][0] → dp[0][1] = 0 + 1 = 1
- 向下走：dp[1][0] += dp[0][0] → dp[1][0] = 0 + 1 = 1
- 现在 dp = [[1,1], [1,0]]
处理 (0,1)：
- 向下走：dp[1][1] += dp[0][1] → dp[1][1] = 0 + 1 = 1
- 现在 dp = [[1,1], [1,1]]
处理 (1,0)：
- 因为 grid[1][0] = 1，能量够，向右走：dp[1][1] += dp[1][0] → dp[1][1] = 1 + 1 = 2
- 最终 dp = [[1,1], [1,2]]

所以 += 操作是在累加从不同路径到达同一位置的路径数量！

5.串联所有单词的子串（哈希）

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) return result;
        
        int wordLen = words[0].length();
        int wordCount = words.size();
        int totalLen = wordLen * wordCount;
        
        if (s.length() < totalLen) return result;
        
        // 统计words中每个单词的频次
        unordered_map<string, int> wordFreq;
        for (const string& word : words) {
            wordFreq[word]++;
        }
        
        // 从每个可能的起始位置开始滑动窗口
        for (int i = 0; i < wordLen; i++) {
            int left = i;
            int right = i;
            unordered_map<string, int> windowFreq;
            
            while (right + wordLen <= s.length()) {
                // 取出右边界的单词
                string rightWord = s.substr(right, wordLen);
                right += wordLen;
                
                if (wordFreq.count(rightWord)) {// wordFreq中是否存在rightWord，存在为1，不存在为0
                    window Freq[rightWord]++;
                    
                    // 如果某个单词出现次数超过了要求，移动左边界
                    while (windowFreq[rightWord] > wordFreq[rightWord]) {
                        string leftWord = s.substr(left, wordLen);
                        windowFreq[leftWord]--;
                        left += wordLen;
                    }
                    
                    // 检查窗口大小是否符合要求
                    if (right - left == totalLen) {
                        result.push_back(left);
                    }
                } else {
                    // 如果遇到不在words中的单词，重置窗口
                    windowFreq.clear();
                    left = right;
                }
            }
        }
        
        return result;
    }
};