题目描述给定一个仅由字符^和_组成的字符串SSS要求从中选取尽可能多的互不相交的子序列每个子序列都等于^_^。子序列的定义遵循标准定义从原字符串中按原顺序选取若干字符不要求连续互不相交意味着每个字符最多只能被使用一次。目标是最大化能够组成的^_^的数量。输入格式输入第一行为一个正整数TTT1≤T≤50001 \le T \le 50001≤T≤5000表示测试用例的数量。接下来TTT行每行一个由^和_组成的字符串长度不超过100000100000100000。所有字符串的总长度不超过2 100 0002\,100\,0002100000。输出格式对于每个测试用例输出一行格式为Case x: y其中xxx为用例编号从111开始yyy为最大数量。样例输入5 _^^_^^_ ^__^__^ ______ ^^__^^ ^_^^_^输出Case 1: 1 Case 2: 1 Case 3: 0 Case 4: 2 Case 5: 2题目分析问题要求在给定字符串中找出最多的互不相交的子序列^_^。每个子序列需要一个^作为左符号一个_作为中间符号另一个^作为右符号且三者的位置必须严格递增。直接枚举所有可能的组合并判断是否重叠不可行因为字符串长度可达10510^5105枚举子序列是指数级的。我们需要一个线性或近线性的贪心策略。关键观察所有的左^都必须位于所匹配的_的左侧所有的右^都必须位于该_的右侧。为了提高匹配数量我们应该尽可能早地使用^作为左符号并尽可能晚地使用^作为右符号以留出更多空间给其他匹配。当遇到一个^时它可以扮演三种角色左符号、右符号或者暂时不参与匹配储备。当遇到一个_时它要么立即与一个左^配对形成“半成品”^_要么因为缺少左^而被暂存等待未来的^来激活。这种动态决策可以通过三个计数器来高效模拟从而在一次扫描中得到最优解。解题思路我们维护四个变量left当前可用的左^的数量即尚未被任何_匹配的^。waiting已经获得左^但尚未匹配到右^的_的数量即半成品^_的个数。pending因缺少左^而暂时被“暂存”的_的数量它们等待未来的^来充当左符号。paired已经成功完成的^_^的数量即最终答案。贪心策略如下遇到字符^优先作为右符号如果存在等待右符号的半成品waiting 0则当前^直接与一个半成品匹配完成一个^_^waiting减111paired加111。这比将当前^用作左符号或激活暂存_更优因为半成品已经占用了一个左^若不及时补上右^它可能永远无法完成。否则尝试激活一个暂存的_如果pending 0且paired 0则说明之前有暂存的_并且我们已经至少完成了一个匹配有“信用”此时可以用当前^作为左符号激活一个暂存的_使其进入半成品状态pending--waiting。激活暂存比单纯增加left更有利因为它把一个潜在的匹配向前推进。否则作为左符号储备将当前^计入left供后续的_使用。遇到字符_优先匹配左^如果left 0则立即将一个左^与当前_配对形成半成品left--waiting。这样做能充分利用当前_避免浪费。否则尝试暂存如果当前没有可用的左^但paired pending即已完成匹配数大于已暂存数则将当前_暂存pending。这个条件保证暂存的_数量不会超过已完成匹配数防止过度乐观的暂存导致无法完成。否则丢弃如果既不满足匹配也不满足暂存条件则当前_无法参与任何匹配直接忽略。正确性说明该贪心算法的每一步都做出了局部最优选择并且可以通过交换论证证明其不破坏全局最优^优先做右符号若某个最优解中当前^没有匹配等待的半成品而某个半成品使用了更靠后的^交换两个^的角色将当前^给该半成品将更靠后的^用于其他用途仍合法且匹配数不变。^在无半成品时优先激活暂存暂存的_已处于等待左^的状态激活它使其进入半成品相当于将未来的一个左^提前使用不会减少最终匹配数。_优先匹配左^有左^就立即配对避免当前_错失机会左^留给更靠后的_并不会更好因为更靠后的_也可以使用更靠后的^。暂存条件paired pending保证了不会无限暂存使得每个暂存的_最终都有机会完成匹配。综上该贪心算法能得到最大匹配数。复杂度分析每个字符只被扫描一次每次操作都是常数时间。时间复杂度O(n)O(n)O(n)其中nnn为字符串长度。空间复杂度O(1)O(1)O(1)仅使用了几个整型变量。代码实现// Emoticons// UVa ID: 13029// Verdict: Accepted// Submission Date: 2026-06-23// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intT;cinT;for(intcs1;csT;cs){string s;cins;intleft0,waiting0,pending0,paired0;for(charc:s){if(c^)if(waiting)waiting--,paired;elseif(pending0paired0)pending--,waiting;elseleft;elseif(left)left--,waiting;elseif(pairedpending)pending;}coutCase cs: paired\n;}return0;}总结本题的关键在于识别出子序列匹配的贪心本质并设计出能够动态调整的三个计数器分别跟踪左符号储备、半成品和暂存的下划线。通过优先使用^作为右符号、及时激活暂存_、以及_优先匹配左^我们能够在单次扫描中计算出最大匹配数。这种技巧适用于类似的有序配对问题当匹配模式固定时贪心往往比动态规划更高效且简洁。时间复杂度O(n)O(n)O(n)和空间O(1)O(1)O(1)使得该算法足以应对大规模数据。