算法基础：递归初阶实战解析

占卜 DIY

参考题目： P10457 占卜 DIY - 洛谷

思路分析

这道题模拟了一个抽牌过程。规则比较绕，但核心逻辑其实是一个循环：

1. 抽出第 13 堆最上面的牌 ch；
2. 根据这张牌的点数，找到对应的牌堆，取出该堆最后一张牌；
3. 重复上述步骤，直到完成指定次数或取完牌。

这里需要处理牌面字符到数字的映射（如 J、Q、K、A），并且要注意数组越界的问题。递归在这里用来模拟'抽一张牌后继续抽下一张'的过程。

代码实现

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

vector<vector<char>> v(14, vector<char>(4));
vector<int> arr(14, 0);

// 将牌面字符转换为数字索引
int getnum(char ch) {
    if (ch == '1') return 13;
    else if (ch >= '2' && ch <= '9') return ch - '0';
    else if (ch == '0') return 10;
    else if (ch == 'J') return 11;
    else if (ch == 'Q') return 12;
    else if (ch == 'A') return 1;
    else return 0;
}

// 递归处理抽牌逻辑
void func(char ch) {
    if (arr[0] == 4) return; // 终止条件
    int num = getnum(ch);
    arr[num]++;
    
    char code;
    if (num == 0) code = '1';
    else if (num == 13) {
        code = v[13][0];
        v[13].erase(v[13].begin());
    } else {
        code = v[num][v[num].size() - 1];
        v[num].erase(v[num].end() - 1);
        v[num].insert(v[num].begin(), ch);
    }
    func(code); // 递归处理下一张
}

int main() {
    for (int i = 1; i <= 13; i++) {
        for (int j = 0; j < 4; j++) {
            char num;
            cin >> num;
            v[i][j] = num;
        }
    }
    func('1');
    
    int ret = 0;
    auto it = arr.begin() + 1;
    while (it != arr.end() - 1) {
        if (*it == 4) ret++;
        it++;
    }
    cout << ret;
    return 0;
}

FBI 树

参考题目： P1087 [NOIP 2004 普及组] FBI 树 - 洛谷

思路分析

FBI 树本质上是一棵二叉树，每个节点代表一段区间。我们需要判断这段区间内 0 和 1 的分布情况：

• 全为 1：I 型节点
• 全为 0：B 型节点
• 既有 0 又有 1：F 型节点

直接遍历统计会超时，利用前缀和可以在 O(1) 时间内算出任意区间的 1 的个数。构建过程采用后序遍历的思想：先递归构建左右子树，再确定当前节点类型并输出。

代码实现

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

struct node {
    char val;
    node* left;
    node* right;
    node(char _val) { val = _val; left = nullptr; right = nullptr; }
};

string s;
vector<int> v(1, 0);

// 判断区间类型
char check(int left, int right) {
    int ones = v[right] - v[left];
    int length = right - left;
    if (ones == length) return 'I';
    if (ones == 0) return 'B';
    return 'F';
}

// 递归建树
node* create(int left, int right) {
    if (right - left == 1) {
        char ch = (s[left] == '1') ? 'I' : 'B';
        return new node(ch);
    }
    int mid = (left + right) / 2;
    node* newnode = new node(check(left, right));
    newnode->left = create(left, mid);
    newnode->right = create(mid, right);
    return newnode;
}

// 后序遍历输出
void rearorder(node* root) {
    if (root == nullptr) return;
    rearorder(root->left);
    rearorder(root->right);
    cout << root->val;
}

int main() {
    int num;
    cin >> num;
    cin >> s;
    // 构建前缀和数组
    for (int i = 0; i < s.size(); i++) {
        int digit = s[i] - '0';
        v.push_back(digit + v[i]);
    }
    
    node* root = create(0, s.size());
    rearorder(root);
    return 0;
}