2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略

贾蔷
• 阅读 156

2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略 一、题目解读 2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。

二、解题思路 采用位运算+哈希表的核心思想: 1. 将字符映射为二进制位:每个字符(如'a'-'z')对应一位(如1<<('a'-'a')到1<<('z'-'a')),子串状态为各字符位异或结果。 2. 统计等价子串:若当前状态已存在,说明存在前缀与该子串等价,其子串数量计入答案;同时更新哈希表记录当前状态出现次数。

三、解题步骤 1. 初始化:定义哈希表stateCount,初始状态mask=0(空串)计数为1。 2. 遍历处理: 对每个字符,通过mask ^= (1 << (s[i] - 'a'))更新状态(异或操作实现字符添加/删除)。 查询stateCount[mask]获取当前状态的出现次数,累加到答案。 更新哈希表stateCount[mask]++。 3. 结果输出:返回累计的等价子串总数。

四、代码与注释

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

// 核心函数:统计等价子串数量
long long countEquivalentSubstrings(const string& s) {
   int n = s.size();
   long long count = 0;          // 答案计数器
   unordered_map<int, int> stateCount; // 记录状态出现次数
   stateCount[0] = 1;           // 空串状态初始化为1
   int mask = 0;                // 当前子串状态(二进制位表示)

   for (int i = 0; i < n; ++i) {
       mask ^= (1 << (s[i] - 'a'));  // 异或更新状态(字符转位操作)
       count += stateCount[mask];    // 累加已有状态的子串数
       stateCount[mask]++;          // 更新状态计数
   }

   return count;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int n;
   string s;
   cin >> n >> s;   // 输入(题目可能有多组数据,但此处简化)
   cout << countEquivalentSubstrings(s) << endl;
   return 0;
}

原文:2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
2019 力扣杯
给出长度相同的两个字符串:A 和 B,其中A\i\和B\i\是一组等价字符。举个例子,如果 A"abc" 且 B"cde",那么就有 'a''c','b''d','c''e'。等价字符遵循任何等价关系的一般规则:自反性:'a''a'对称性:'a'
贾蔷 贾蔷
1个月前
2013 蓝桥杯 省赛B组 翻硬币(洛谷P8597题) 从暴力BFS到贪心算法的优化之路
一、问题背景与理解洛谷P8597是一道经典的翻硬币问题,题目描述如下:给定两个由''和'o'组成的字符串s1和s2,分别表示初始状态和目标状态。每次操作可以选择任意位置开始翻转连续的k个硬币(''变'o','o'变'')。要求计算出从初始状态变为目标状态所
贾蔷 贾蔷
3星期前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
深度学习 深度学习
3星期前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
深度学习 深度学习
3星期前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
贾蔷 贾蔷
3星期前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
3星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
1星期前
2024蓝桥杯国赛B组最小字符串题解:贪心算法实战应用
一、题目解读题目要求给定一个长度为N的S和M个待插入字符,通过将这些字符全部插入S中,构造出最小的新字符串。这是典型的字符串构造问题,考察选手对的理解和应用能力。二、解题思路采用贪心策略:1.先将待插入字符,便于按字典序选择2.遍历原字符串时,在保证字典序
贾蔷 贾蔷
2天前
洛谷P1102题解:利用哈希表优化的数对统计 C++代码解析
一、题目解读P1102题要求处理一组整数与常数C,统计数组中是否存在元素A与B满足ABC。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。二、解题思路采用(unorderedmap)实现高效统计。首先遍
深度学习 深度学习
2天前
2020CSP-S动物园题解:位运算优化解法(洛谷P7076)
一、题目解读2020年(中国计算机学会青少年信息学奥林匹克竞赛)的“动物园”题目(P7076)要求计算为满足饲养员对动物属性的要求,至少需要新增多少种动物。题目涉及与属性匹配,考验逻辑与优化能力。二、解题思路采用位运算为核心策略:1.属性合并:用位运算将已