T1 学习求余

本题是考察加法、乘法、求余运算的综合题

观察 这个式子。

情况 1：如果 的话，那么 。这样的话，这道学习求余就变成了学习加法。

当然，此题是一道综合题，还需要学会乘法的性质才能做出此题——两个数字的和一定，差值越小，乘积越大。所以如果想要让乘积尽量大，那么肯定要让 尽可能地接近。如果 是奇数的话，那么可以写出这样的式子：

，答案就是

如果 是偶数的话，可以写出这样的式子：

，答案就是

情况 2：，那么 ，其中 表示 除以 的商，且至少为 2。显然，这样算出来的 值之和肯定没有情况 1 大，那么最终得到的乘积也没有情况 1 大，故舍弃这种情况。

T2 提取数字

考察字符串模拟

考虑在字符串中是如何构造出一个数字的：例如字符串中有 123，先看第一位 1，得到数字 1，再看第二位 2，得到数字 12，此处的 12 就是由之前的数字 1 乘以 10 再加上当前的数字 2 得到的。再看第三位 3，得到数字 123，这是由数字 12 乘以 10 再加上 3 得到的。也就是说每看一位数字，都用之前的数字乘以 10 再加上当前就可以了。

遇到字母之后，就不用再乘以 10 了，遇到字母表示我们现在已经提取好了一个数字，加上 5 之后加入答案即可。假设 s 是题目的字符串，now 是当前数字，sum 是最终要输出的答案，那么我们可以写出如下代码：

// 循环查看字符串的每一位
if(s[i] >= '0' && s[i] <= '9'){ // 遇到数字
	now = now * 10 + s[i] - '0'; // 乘以 10 加上当前位
}else{ // 遇到字母
	sum += now + 5; // 加到答案里
	now = 0; // 清空当前数字
}

但是这样的代码无法处理连续字母的问题，例如读入的字母是 aaaaa，那么对于每一个 a 来说，都会进入 else 里面，使得 sum += 5，最终算出 25。但是实际上 aaaaa 里面没有数字，应该输出 0。我们可以用一个变量 hasnumber 来标记当前是否遇到过数字。

 for(int i = 0; i < s.size(); i++){
	if(s[i] >= '0' && s[i] <= '9'){
        hasnumber = 1; // 遇到过数字
        now = now * 10 + s[i] - '0';
    }else{
        if(!hasnumber)	continue; // 处理连续字母的情况，如果没遇到过数字就跳过 +5 的操作
        sum += now + 5;
        hasnumber = 0; // 重置标记
        now = 0;
    }
}

最后，我们要注意纯数字或者字符串末尾是数字的情况，例如 12345，或者 123a12345，对于这种情况，最后的 12345 这个数字不会被统计到，因为代码的逻辑是遇到非数字（进入 else）才会统计到 sum 中。

所以我们可以在读入的时候就把字符串末尾强行加入一个字母，来应对这种情况。

cin >> s;
s += 'A';

T3 武器选择

考虑种类数量的 ，有 ，即合法的武器种类最多只有 种。

对所有合法种类求前缀和，每次询问检查所有合法种类是否在该区间内满足条件即可。

总的时间复杂度为 。

T4 括号序列

• 合法括号序列内每个左括号都有一个对应的右括号。如果第 个括号和第 个括号匹配，那么可以将 分为 和 两部分，只要保证第 个括号和第 个括号不同色即可，后续可独立考虑两部分。通过区间划分可以想到动态规划。

• 根据上一点指出的第 个括号和第 个括号不同色这个条件，所以区间信息要记录区间的最左边的括号和区间最右边的括号的颜色。因此设置 表示第 个括号涂颜色 ，第 个括号涂颜色 ， 区间的最大代价。颜色集合是 ，分别对应，无色、白色、黑色。

• 首先通过栈预处理出配对括号， 表示第 个括号和第 个括号匹配，且 。

• 转移过程暴力枚举区间端点的颜色，采用记忆化搜索实现。

• 转移方程需分类讨论：

  • 如果 和 不配对，即 。则 和 没有关系，继续递归处理 和 即可。注意 和 不同色。

  • 如果 和 配对，即 ，则 。当前区间记录上该配对括号的贡献。继续处理 区间即可，同时保证 和 不同色、 和 不同色。