T1 学习减法

考察减法中的借位

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

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

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

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

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

#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 的循环上吃草，那么当时间 $t$ 满足 $t \% 3 = 1$ 的时候，牛牛 A 此刻吃草最多，满足 $t \% 3 = 2$ 的时候，牛牛 B 此刻吃草最多，满足 $t \% 3 = 0$ 的时候，牛牛 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 的循环变成大小为 $2 \sim 10$ 不等的循环。我们用 maxx[k][j] 表示所有处于大小为 $i$ 的环的牛牛，它的第 $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; // 记录牛牛的编号
		}
	}
}

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

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

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 学习加法

题目提到每次进位都有可能发生或者不发生，正好对应动态规划的两种转移方式，因此可以考虑动态规划。
考虑如何设计动态规划的状态，不难想到要把题面中给出的进位添加到状态内，即 $dp[i][0]$ 表示考虑了 $0\sim i-1$ 位，且这些位对第 $i$ 位没有发生进位的方案数。 $dp[i][1]$ 表示考虑了 $0\sim i-1$ 位，且这些位对第 $i$ 位发生进位的方案数。
不妨设 $a$ 位数较多，然后 $b$ 高位填 $0$ 对齐二者方便编写代码。则考虑第 $i$ 位时，将 $a[i],b[i]$ 与进位相加，如果大于等于 $10$ ，则可考虑进位或者不进位，即为两种转移方式。具体转移方程可见代码，与题解定义一致。
设 $a$ 共有 $n$ 位，则输出 $dp[n][0] dp[n][1]$ 即可。分别表示最高位是否发生了进位。

T4 嘤嘤的子串权值和

先记字符串长度为 $n$ ，然后定义接下来出现的 "abba" 子序列的字母的位置分别是 $l,ml,mr,r(l<ml<mr<r)$ 。

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

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

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

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