专栏文章

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

休闲·娱乐参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmq9q0
此快照首次捕获于
2025/12/02 04:56
3 个月前
此快照最后确认于
2025/12/02 04:56
3 个月前
查看原文

背景

蒟蒻学了一点csp-s内容,想试一试
但是看到了这个CSP-X的题,因为今年双打J和S,想看看黄题练练手

转折点

我竟然不懂吗!

(内心大草)

这XXS的题不会做!

这个不禁让我想起了平衡树,哈希表,于是,再2个小时后,我调出了这样一份代码:
CPP
#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}{红}
在非正规解的情况下,也是
CPP
                      肥肠牛🖊啊
如果你闲的D疼,那你可以帮我改改,我还是太弱了。。。
不改也就算了

END

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

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

评论

0 条评论,欢迎与作者交流。

正在加载评论...