博客主页:誓则盟约系列专栏:IT竞赛 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ 试题F:括号与字母 【问题描述】 给定一个仅包含小写字母和括号的字符串 S ,保证括号可以两两匹配。 给出 Q 组询问,每组询问给出一个小写字母 ci 和一个数 xi ,询问 S 中有 多少对匹配的括号之间有不
问题分析 这道题属于贪心加回溯。所有操作如果能使得高位的数字变大必定优先用在高位,因为对高位的影响永远大于对低位的影响。然后我们再来分析一下,如何使用这两种操作?对于加操作,如果能使这一位的数字加到9则变成9,否则使这个数字尽量大。对于减操作,如果能使这一位的数字减到9则变成9,否则不采用减操作。然后我们用回溯来分别对该位进行加操作和减操作,记录最大值。时间复杂度大概是 O ( 2 l g