T1 学习减法

考察减法中的借位

借位实际上就是指的是让某一位减一。例如对于数字 2000 来说，如果借了千位，那么千位就会变成 1，相当于把这个数字 -1000。

那么如果本来应该向千位借位，但是又忘了，相当于把这个数字加回了 1000。

那么想要让最终的结果最大，我们只需要让牛牛忘记最高位的借位即可。所以本题等价于寻找最高位的借位。

我们可以从右往左一位一位看，看什么时候减法的时候会产生借位。如果对应位置 ，那么会产生借位，除此之外，相等的时候也可能产生借位，例如 11000 - 10001，两个数字的百位都是 0，但是也会借位，这是因为前面的借位传递到这里了。

用变量 flag 来表示借位是否传递。如果对应位置 ，则说明需要传递借位，如果 则会消除之前的传递，如果对应位置 ，则传递情况不变（本来传递借位，现在还传递，本来不传递，则现在不传递）

#include <iostream>
using namespace std;
int main(){
	long long a, b, now = 1, flag = 0;
	cin >> a >> b;
	long long ans = a - b, tmpans = a - b;
	while(a){
		now *= 10; // 从个位开始往上看，所以位权每次乘以 10
		int a1 = a % 10, b1 = b % 10; // 取出数位
		if(a1 < b1 || a1 == b1 && flag){ // 如果 a1 比 b1 小，则需要借位。或者 a1 和 b1 相等，但是前面向这里借位，那么这里也需要借位
			ans = max(ans, tmpans + now);
		}
		if(a1 < b1){
			flag = true;
		}else if(a1 > b1){
			flag = false;
		}
		a /= 10; b /= 10;
	}
	cout << ans << endl;
} 

T2 牛牛吃草

考察枚举+循环节的思想

观察到牛牛们是有循环的吃草的，假设所有牛牛都在大小为 3 的循环上吃草，那么当时间 满足 的时候，牛牛 A 此刻吃草最多，满足 的时候，牛牛 B 此刻吃草最多，满足 的时候，牛牛 C 此刻吃草最多。A、B、C 为预处理出环上每个位置吃草最多的牛牛。

// 伪代码:
int A = 0, B = 0, C = 0;
for(int i = 1; i <= n; i++){
    cin >> k; // 由于我们刚刚说所有牛牛的循环大小都是 3，所以这里读入的 k 一定是 3。
	// 读入每头牛牛的在环上的三个位置的吃草量。
		cin >> a >> b >> c;
		A = max(A, a); 
		B = max(B, b);
		C = max(C, c);
	}
}
// 输出的时候只需要根据预处理出的 A B C 输出即可。

当然，题目要求输出牛牛的编号，所以在求 max 的时候同时需要记住牛牛的编号并输出。

现在我们推广到满分做法：也就是把刚刚大小为 3 的循环变成大小为 不等的循环。我们用 maxx[k][j] 表示所有处于大小为 的环的牛牛，它的第 个位置最大的吃草量。

for(int i = 1; i <= n; i++){
	cin >> k; // k 表示环的大小
	for(int j = 1; j <= k; j++){ // j 表示第 j 个位置
		cin >> a;
		if(a > maxx[k][j]){
			maxx[k][j] = a; // 求 max 操作
			id[k][j] = i; // 记录牛牛的编号
		}
	}
}

的范围只需要到 10 就可以了，本题的数据范围较小。

输出时，枚举时间 ，然后枚举循环大小 ，根据 的值找到此刻吃草最大的牛牛，即可获得答案。

for(int i = 1; i <= m; i++){
	int ans = 0, pos; // ans 是吃草量，pos 是牛牛编号
	for(int j = 2; j <= 10; j++){
		int now = i % j; // 找循环 j 的第 now 位置吃草最大的牛牛
		if(now == 0)	now = j;
		if(maxx[j][now] > ans){
			ans = maxx[j][now];
			pos = id[j][now];
		}else if(maxx[j][now] == ans){
			pos = min(pos, id[j][now]);
		}
	}
	cout << pos << " ";
}

T3 学习加法

• 题目提到每次进位都有可能发生或者不发生，正好对应动态规划的两种转移方式，因此可以考虑动态规划。

• 考虑如何设计动态规划的状态，不难想到要把题面中给出的进位添加到状态内，即表示考虑了位，且这些位对第位没有发生进位的方案数。表示考虑了位，且这些位对第位发生进位的方案数。

• 不妨设位数较多，然后高位填对齐二者方便编写代码。则考虑第位时，将与进位相加，如果大于等于，则可考虑进位或者不进位，即为两种转移方式。具体转移方程可见代码，与题解定义一致。

• 设共有位，则输出即可。分别表示最高位是否发生了进位。

T4 嘤嘤的子串权值和

​ 先记字符串长度为 ，然后定义接下来出现的 "abba" 子序列的字母的位置分别是 。

​ 我们可以枚举每一个 "abba" 子序列，看它出现在多少个子串中，那么，左端点在第一个 'a' 左边，右端点在最后一个 'a' 右边的所有子串都包含这个子序列，对答案的贡献就是 。此时的复杂度为 。

​ 考虑一下优化，固定了前后两个 'a' 之后，中间的两个 'b' 无论取自哪里，对答案的贡献都是一样的，那么中间的两个 'b' 有多少种取法呢？根据组合数可以发现是 （ 为两个 'a' 中间的 'b' 的数量），对答案的贡献就是 。用前缀和计算 'b' 的数量，复杂度就是 。

​ 根据前面可以发现，以某一个 'a' 为开头的子序列，计算贡献用到的就是它左边的字符个数 ；同理，以某一个 'a' 为结尾的子序列，计算贡献用到的就是它右边的字符个数 。那么如果固定第二和第三个 'b' ，它们会在几个子序列中出现？不难想到就是 前面的 'a' 的数量乘以 后面 'a' 的数量，那么贡献又是多少呢？假设 前面有2个 'a' ， 后面有2个 'a' ，位置分别是 ，参考前面计算贡献的方法，列出式子： ，使用结合律结合一下，就是 ，那么我们就可以用前缀和 和后缀和 记录 前面 'a' 可以产生的贡献， 后面 'a' 可以产生的贡献，然后我们就可以枚举中间的两个 'b' ，快速计算贡献，此时的复杂度也为 。

​ 现在我们知道了，通过枚举 'a' 字母位置，或者枚举 'b' 字母位置，都可以计算贡献，但时间复杂度都是 ，依然不能通过此题，需要继续优化。对一个 'b' 字母，固定它为第2个字母，那么第3个字母 'b' 的取法就是 后面 'b' 字母的数量，对于后面每一个 'b' 字母，可以对答案产生贡献在于后面所有 'a' 字母的贡献和，也就是之前的后缀和 。那么对这个固定的 'b' 字母，我们可以再求一个后缀和 ，记录这个 'b' 字母后面所有 'b' 字母作为第3个字母产生的贡献。再根据之前的结合律，枚举每一个 'b' 字母，固定其为第2个字母，对答案产生的贡献就是 。此时，复杂度终于来到了 。

for (int i = 1; i <= n; i++) {
    front_a[i] = front_a[i - 1];
    if (s[i] == 'a') front_a[i] += i;
}
int ans = 0;
for (int i = n; i >= 1; i--) {
    back_a[i] = back_a[i + 1];
    if (s[i] == 'a') back_a[i] += n - i + 1;
    back_ba[i] = back_ba[i + 1];
    if (s[i] == 'b') back_ba[i] += back_a[i];
}
for (int i = 1; i <= n; i++) {
    if (s[i] == 'b') ans += front_a[i] * back_ba[i + 1];
}