题意简述
给定一个长度不超过\(5\times 10^5\)的，仅有数字构成的字符串，问存在多少段子串，使得子串内字符重新排序后，前半段与后半段相同？
做法分析
重组后前后两部分相同，其实也就意味着，这一子串内所有数字出现的次数都为偶数次。
考虑暴力竹筏，枚举左端点和右端点，统计子串内每个数字出现次数，判断是否都为偶次。但是这样达到\(O(n^3)\)级别，效率过低。
ABC295 D题 题解
发布时间 2023-03-26 14:21:48作者: six_one
给定一个长度不超过\(5\times 10^5\)的，仅有数字构成的字符串，问存在多少段子串，使得子串内字符重新排序后，前半段与后半段相同？
重组后前后两部分相同，其实也就意味着，这一子串内所有数字出现的次数都为偶数次。
考虑暴力竹筏，枚举左端点和右端点，统计子串内每个数字出现次数，判断是否都为偶次。但是这样达到\(O(n^3)\)级别，效率过低。