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

贾蔷
• 阅读 120

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)代码解析与优化策略

点赞
收藏
评论区
推荐文章
Easter79 Easter79
3年前
str字符串 count( ) 方法
描述Pythoncount()方法用于统计字符串里某个字符出现的次数。可选参数为在字符串搜索的开始与结束位置。语法count()方法语法:str.count(sub,start0,endlen(string))参数sub搜索的子字符串start字符串开始搜索的位置
Wesley13 Wesley13
3年前
2019 力扣杯
给出长度相同的两个字符串:A 和 B,其中A\i\和B\i\是一组等价字符。举个例子,如果 A"abc" 且 B"cde",那么就有 'a''c','b''d','c''e'。等价字符遵循任何等价关系的一般规则:自反性:'a''a'对称性:'a'
Stella981 Stella981
3年前
LeetCode 459. 重复的子字符串(Repeated Substring Pattern)
459\.重复的子字符串459\.RepeatedSubstringPattern题目描述给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。<spanclass"badgebadgepillbadgedanger"LeetCod
深度学习 深度学习
5天前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
深度学习 深度学习
5天前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
贾蔷 贾蔷
5天前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
5天前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
3天前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
3星期前
2013 蓝桥杯 省赛B组 翻硬币(洛谷P8597题) 从暴力BFS到贪心算法的优化之路
一、问题背景与理解洛谷P8597是一道经典的翻硬币问题,题目描述如下:给定两个由''和'o'组成的字符串s1和s2,分别表示初始状态和目标状态。每次操作可以选择任意位置开始翻转连续的k个硬币(''变'o','o'变'')。要求计算出从初始状态变为目标状态所
贾蔷 贾蔷
5天前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在