T1 学习异或

20pt

由于只有一个数字，输出这个数字即可。

40pt

考察枚举法

枚举对哪一个数字进行异或，假设将 异或，那么修改 ，然后对整个数组进行求和。

100pt

考察求最大值。

不管是对一个数字求异或还是什么别的运算，总之本题只能对一个数字用一次操作，那么计算总和就很简单，我们只需要保存原来所有数字的和，再看看本次操作时这个数字的改变，就可以知道新的总和了。

本题需要知道最大的和，所以我们可以对每个数字都试一遍，看看谁和 异或之后能够变大得更多，也就是求所有 的最大值，其中 为异或运算。

1. 最后两个测试点注意开 long long
2. 求最大值的时候初始值不要设成 0，要设成负无穷。因为本题是必须使用这次异或运算的，而异或运算还有可能让数字变小。

T2 修改数字

枚举操作 1 使用多少次，我们可以发现操作 1 最多使用 9 次，因为使用 10 次和使用 0 次是一样的，数字是 10 个一循环。

枚举之后再看操作 2，操作 2 无需枚举，贪心即可，想要让数字最大，就对第一个非 9 的数位进行 +1，就可以得到最大的数字了。

对于 10 种情况（操作 1 使用 0 次到 9 次，共 10 种枚举）求一个最大值即可。求最大值的时候可以用 string 的字典序比大小，因为数字长度一定，所以比大小的时候就用字典序就可以了。

T3 学习除法

表示若干个炸弹造成至少 点伤害的最小代价。首先初始化。

考虑枚举小炸弹进行合并。详细地说，枚举伤害为 的炸弹和 的炸弹，则 + 。这样的二元组个数是 级别，即为复杂度。

。询问等价于找 的最小值。容易知道如果 是满足不等式的，那么比 大的数都符合不等式，因此可以二分找到最小的 。直接输出 即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=64397315

T4 坏子串

首先考虑一下暴力的做法，我们可以找出所有的子串，也就是枚举每一个左、右端点，然后从左往右将所有字母存进一个桶里，若桶里存在一种字母只出现一次，即可记为答案。此时复杂度为 。

​ 其次，考虑一个简单的优化，枚举每一个右端点，然后从右往左把所有字母存进一个桶里，查找桶里是否有字母只出现一次。此时每存一个字母，就相当于枚举了一个区间，按上述方法计算答案即可。此时复杂度为 。

​ 再考虑一下只有两种字母的做法，并假设只有 'a' 、 'b' 两种字母，那么对于一个右端点 （不妨假设 ），会有两种情况：

​ 情况一，若 'a' ，那么我们只需要找到在 之前的第一个 'b' ，位置记为 。此时左端点从 往前枚举，就会有一段的左端点都是合法的，那么什么时候不合法呢？也就是在 之前，又找到一个 'b' 位置为 ，此时再往前找都将是不合法的。那么，在 区间内，所有的点作为左端点， 作为右端点的区间都是合法的，答案将加上 ，再加上长度为1的 "a" 子串本身。以字符串 "aabbaabaaa" 为例，对于右端点10，子串 "baaa" 、 "abaaa" 、 "aabaaa" 都是合法的，换算为左端点所在区间即为 ，答案记为3，再加上子串 "a" 本身，答案为4。

​ 情况二，若 'b' ，那么我们只需要找到在 之前的第一个 'a'，位置记为 ，找到在 之前的第一个 'b' ，位置记为 ，那么这时 这一个区间都是合法的，答案将加上 。再以字符串 "aabbaabaaa" 为例，对于右端点5， ， ，因此区间为 ，答案记为3，对于右端点8， ， ，因此区间为 ，答案记为3。

​ 我们可以对每一个位置，记录它前面一个 'a' 字母在哪， 'b' 字母在哪，就可以优化枚举的时间，此时复杂度为 。

​ 仔细观察只有两种字母的情况，分别考虑 'a' 、 'b' 两种字母，我们可以发现：对于情况一， 'a' 字母只出现一次的左端点区间为 ， 'b' 字母只出现一次的区间为 ，计算答案为 和 ；对于情况二， 'a' 字母只出现一次的区间为 ， 'b' 字母只出现一次的区间为 ，计算答案为 。对于情况二，我们进行了一次区间合并，然后计算这个区间的大小，而情况一，我们计算了两个相离的区间的大小。对于一种字母记为 ， 只出现一次区间，其实都是从位置 往前找到第一个 ，记为 ，再从位置 往前找到第一个 ，也就是从位置 往前的第二个 ，记为 ，区间即为 ，若找不到 ，则这个字母不用考虑，若找不到 ，则区间 都是合法的。

​ 若字母有26种，那么对于一个右端点，将会产生26个区间，我们把这些区间进行合并，再计算所有区间的大小，即可求出这个右端点对答案的贡献。例如，字符串 "abcdabcc" ，对于右端点8，字母 'a' 只出现一次的区间为 ，字母 'b' 只出现一次的区间为 ，字母 'c' 只出现一次的区间 ，字母 'd' 只出现一次的区间为 ，将区间合并后，生成两个新的区间 ， ，此时答案为6+1=7。

​ 对每一个位置，记录它前面每一种字母在哪个位置，然后区间合并需要 的时间排序，因此复杂度为 。