B4101 [CSP-X2023 山东] 回文字符串 平衡树构造+哈希表 黄题太难了

· · 休闲·娱乐

背景

蒟蒻学了一点csp-s内容，想试一试

但是看到了这个CSP-X的题，因为今年双打J和S，想看看黄题练练手

转折点

我竟然不懂吗！

（内心大草）

这XXS的题不会做！

record

这个不禁让我想起了平衡树，哈希表，于是，再2个小时后，我调出了这样一份代码：

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
#include <tuple>//用了bits/stdc++.h不知神奇的CE了，应该是哪个变量名在变异
using namespace std;

typedef long long ll;

// 哈希参数（避免哈希冲突）
const ll BASE = 911382629;
const ll MOD = 1e18 + 3;
const ll BASE_REV = 358664861; // BASE在MOD下的逆元
const ll MOD_REV = 1e18 + 3;   // 与MOD同（质数）

// 前缀哈希与逆元前缀（这是抄的）
vector<ll> prefix_hash, prefix_rev_hash, pow_base, pow_rev;

// 预处理哈希（哈希其实不会，还是抄的）
void precompute_hash(const string& s, const string& rev_s) {
    int n = s.size();
    prefix_hash.resize(n + 1, 0);
    prefix_rev_hash.resize(n + 1, 0);
    pow_base.resize(n + 1, 1);
    pow_rev.resize(n + 1, 1);

    for (int i = 0; i < n; ++i) {
        prefix_hash[i + 1] = (prefix_hash[i] * BASE + s[i]) % MOD;
        pow_base[i + 1] = (pow_base[i] * BASE) % MOD;
    }
    for (int i = 0; i < n; ++i) {
        prefix_rev_hash[i + 1] = (prefix_rev_hash[i] * BASE + rev_s[i]) % MOD;
        pow_rev[i + 1] = (pow_rev[i] * BASE_REV) % MOD;
    }
}

// 获取子串s[l..r]的哈希（0-based, 闭区间）
ll get_hash(int l, int r) {
    int len = r - l + 1;
    ll hash_val = (prefix_hash[r + 1] - prefix_hash[l] * pow_base[len]) % MOD;
    return hash_val < 0 ? hash_val + MOD : hash_val;
}

// 获取子串s[l..r]反转后的哈希（即rev_s中对应位置的哈希，还是不会）
ll get_rev_hash(int l, int r) {
    int n = prefix_rev_hash.size() - 1;
    int rev_l = n - 1 - r;
    int rev_r = n - 1 - l;
    int len = rev_r - rev_l + 1;
    ll hash_val = (prefix_rev_hash[rev_r + 1] - prefix_rev_hash[rev_l] * pow_base[len]) % MOD;
    return hash_val < 0 ? hash_val + MOD : hash_val;
}

// 检查子串[l1..r1]与[l2..r2]是否相等或互为回文
bool is_valid(const string& s, int l1, int r1, int l2, int r2) {
    if (r1 - l1 != r2 - l2) return false;
    int len = r1 - l1 + 1;

    // 检查是否相等（哈希直接比较）
    if (get_hash(l1, r1) == get_hash(l2, r2)) return true;

    // 检查是否互为回文（s[l1..r1]的反转是否等于s[l2..r2]）
    if (get_rev_hash(l1, r1) == get_hash(l2, r2)) return true;

    return false;
}

struct State {
    int left;   // 当前左侧起始位置
    int right;  // 当前右侧结束位置
    int cnt;    // 已分割的子串数
    State(int l, int r, int c) : left(l), right(r), cnt(c) {}
    // 排序用于平衡树（set），优先按left递增，再按right递减（优先处理更靠左的短分割）
    bool operator<(const State& other) const {
        if (left != other.left) return left < other.left;
        if (right != other.right) return right > other.right;
        return cnt > other.cnt; // 相同区间保留更大的计数
    }
};

int main() {
    string s;
    cin >> s;
    int n = s.size();
    if (n < 2) {
        cout << "NO" << endl;
        return 0;
    }
    string rev_s = s;
    reverse(rev_s.begin(), rev_s.end());
    precompute_hash(s, rev_s);

    // 平衡树存储可能的状态，用于BFS式扩展，这个我会的，自己写的，没抄
    set<State> states;
    // 哈希表记录每个[left,right]区间的最大分割数，避免重复处理
    unordered_map<int, unordered_map<int, int>> max_cnt;

    // 初始状态：整个字符串待分割
    states.insert(State(0, n - 1, 0));
    max_cnt[0][n - 1] = 0;

    int max_total = -1;

    while (!states.empty()) {
        // 取出当前最优状态（最左、分割数最多）
        State curr = *states.begin();
        states.erase(states.begin());
        int l = curr.left;
        int r = curr.right;
        int cnt = curr.cnt;

        // 若当前状态已被更优解覆盖，跳过
        if (max_cnt[l][r] > cnt) continue;

        // 区间处理完毕，检查是否满足条件
        if (l > r) {
            if (cnt > 1) {
                max_total = max(max_total, cnt);
            }
            continue;
        }

        // 尝试中间单独一个子串（总分割数为奇数）
        if (l == r) {
            // 单个字符自身是回文，可作为中间子串
            if (cnt + 1 > 1) {
                max_total = max(max_total, cnt + 1);
            }
            continue;
        }

        // 枚举可能的分割长度（从1到区间长度的一半）
        int max_len = (r - l + 1) / 2;
        for (int len = 1; len <= max_len; ++len) {
            int r1 = l + len - 1;
            int l2 = r - len + 1;
            if (r1 >= l2) break; // 子串重叠，无效

            // 检查左右子串是否有效
            if (is_valid(s, l, r1, l2, r)) {
                // 分割后新状态
                int new_l = r1 + 1;
                int new_r = l2 - 1;
                int new_cnt = cnt + 2;

                // 若新状态更优，加入平衡树
                if (!max_cnt.count(new_l) || !max_cnt[new_l].count(new_r) || new_cnt > max_cnt[new_l][new_r]) {
                    max_cnt[new_l][new_r] = new_cnt;
                    states.insert(State(new_l, new_r, new_cnt));
                }
            }
        }

        // 特殊情况：中间子串为回文（总分割数为奇数）
        if ((r - l + 1) % 2 == 1) {
            int mid = (l + r) / 2;
            // 检查中间子串是否为回文（自身与自身互为回文）
            if (get_hash(l, mid) == get_rev_hash(l, mid)) {
                int new_l = mid + 1;
                int new_r = mid - 1; // 已处理中间，左右闭合
                int new_cnt = cnt + 1;
                if (!max_cnt.count(new_l) || !max_cnt[new_l].count(new_r) || new_cnt > max_cnt[new_l][new_r]) {
                    max_cnt[new_l][new_r] = new_cnt;
                    states.insert(State(new_l, new_r, new_cnt));
                }
            }
        }
    }

    if (max_total != -1) {
        cout << "YES" << endl;
        cout << max_total << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}
//感谢CSDN，OI-WIKI对本文的代码引导%%%%

（不要骂我，我真的很菜，哈希表抄的板子）

简单概括下来这个差不多3类：

哈希表优化

平衡树构造

分割状态

前两个比较好理解，第三个我想了很久

不仅考虑对称子串对，还处理了中间单独回文子串的情况（总分割数为奇数），覆盖所有可能的有效分割

所以很烦很烦

所以你想看我的得分是吧，

是的你想看的，

我们竟然得到了

40分

的好成绩

record

半江\textcolor{green}{瑟瑟}

半江\textcolor{red}{红}

在非正规解的情况下，也是

                      肥肠牛🖊啊

如果你闲的D疼，那你可以帮我改改，我还是太弱了。。。

不改也就算了

END

备注（作者因为之前灌水被禁言了，改动回复会在文章中体现）

————华丽的分割线—————