T1 学习异或

20pt

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

40pt

考察枚举法

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

100pt

考察求最大值。

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

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

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

T2 修改数字

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

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

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

T3 学习除法

$cost[i]$ 表示若干个炸弹造成至少 $i$ 点伤害的最小代价。首先初始化 $cost[i]=\min_{j\geq i}b[j]$ 。

考虑枚举小炸弹进行合并。详细地说，枚举伤害为 $i$ 的炸弹和 $j$ 的炸弹，则 $cost[i*j]$ $=min(cost[i*j],$ $cost[i]$ + $cost[j])$ 。这样的二元组个数是 $O(nlog)$ 级别，即为复杂度。

$\lfloor\frac{x}{p} \rfloor \leq y$ 。询问等价于找 $p$ 的最小值。容易知道如果 $p$ 是满足不等式的，那么比 $p$ 大的数都符合不等式，因此可以二分找到最小的 $p$ 。直接输出 $cost[p]$ 即可。

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

T4 坏子串

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

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

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

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

情况二，若 $s_{i-1}=$ 'b' ，那么我们只需要找到在 $i$ 之前的第一个 'a'，位置记为 $l$ ，找到在 $i-1$ 之前的第一个 'b' ，位置记为 $r$ ，那么这时 $(min(l,r),i]$ 这一个区间都是合法的，答案将加上 $i-min(l,r)$ 。再以字符串 "aabbaabaaa" 为例，对于右端点5， $l=2$ ， $r=3$ ，因此区间为 $(2,5]$ ，答案记为3，对于右端点8， $l=6$ ， $r=4$ ，因此区间为 $(4,8]$ ，答案记为3。

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

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

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

对每一个位置，记录它前面每一种字母在哪个位置，然后区间合并需要 $26 \times log_2 26$ 的时间排序，因此复杂度为 $O(26 \times log_2 26 \times n)$ 。