蒟蒻第一次打 USACO，只打了 Bronze 就跑路了。不得不说也有很有意思的题目。接下来就看看题目吧。

由于现在还看不到题目，只给出加工后的题目大意。

T1 Lonely Photo

Content

有一个长度为 \(n\) 的字符串 \(s\)，仅包含两种字符：G 和 H。定义字符串 \(s'\) 是孤独的，当其仅当 \(s'\) 中恰好只有一个 G 或 H 且 \(|s'|\geqslant 3\)。例如，字符串 GHGGG、GHHHH 是孤独的，而字符串 GH、GHGHG 不是。现在，请你求出 \(s\) 的所有孤独的子串的个数。

数据范围：\(n\leqslant 5\times 10^5\)。

Solution

我们很容易想到一个 \(\mathcal O(n^2)\) 的做法，即暴力模拟每个子串并判断其是否是孤独的。但是有没有更优的方法？确实有。我们可以先预处理出当前字符前面、后面有多少个连续的与当前字符不同的字符，设在 \(i\) 位置上的字符前面连续的与当前字符不同的字符有 \(\textit{bef}_i\) 个，后面连续的与当前字符不同的字符有 \(\textit{aft}_i\) 个。那么，我们就可以对于每个位置直接算其对答案的贡献就好了。具体地，对于当前位置 \(i\)：

• 如果 \(\textit{bef}_i>0\) 且 \(\textit{aft}_i>0\)，那么当前位置对答案的贡献加上 \(\textit{bef}_i\cdot\textit{aft}_i\)。
• 如果 \(\textit{bef}_i>1\)，那么那么当前位置对答案的贡献加上 \(\textit{bef}_i-1\)。
• 如果 \(\textit{aft}_i>1\)，那么那么当前位置对答案的贡献加上 \(\textit{aft}_i-1\)。

综上，当前位置 \(i\) 对答案的贡献是 \(\textit{bef}_i\cdot\textit{aft}_i+\max(0,\textit{bef}_i-1)+\max(0,\textit{aft}_i-1)\)。

由此，我们将算法优化到了 \(\mathcal{O}(n)\)，就可以通过这道题目了。

Code

赛时代码。

namespace Solution {
	const int N = 5e5 + 7;
	int n, cntg, cnth, g[N], h[N], numg[N], numh[N], bef[N], aft[N];
	char a[N];
	
	iv Sub1_work() {
		ll ans = 0;
		F(int, i, 1, n) {
			if(i <= n - 2 && ((a[i] == 'G' && a[i + 1] == 'H' && a[i + 2] == 'H') || (a[i] == 'H' && a[i + 1] == 'G' && a[i + 2] == 'G'))) {
				int cur = i + 2;
				for(; cur < n && a[cur + 1] == a[i + 2]; cur++);
				ans += (cur - (i + 2) + 1);
			}
			if(i > 1 && i < n && ((a[i] == 'G' && a[i - 1] == 'H' && a[i + 1] == 'H') || (a[i] == 'H' && a[i - 1] == 'G' && a[i + 1] == 'G'))) {
				int curl = i - 1, curr = i + 1;
				for(; curl > 1 && a[curl - 1] == a[i - 1]; curl--);
				for(; curr < n && a[curr + 1] == a[i + 1]; curr++);
				ans += 1ll * ((i - 1) - curl + 1) * (curr - (i + 1) + 1);
			}
			if(i >= 3 && ((a[i] == 'G' && a[i - 1] == 'H' && a[i - 2] == 'H') || (a[i] == 'H' && a[i - 1] == 'G' && a[i - 2] == 'G'))) {
				int cur = i - 2;
				for(; cur > 1 && a[cur - 1] == a[i - 2]; cur--);
				ans += ((i - 2) - cur + 1);
			}
		}
		write(ans);
	}
	iv Sub2_work() {
		F(int, i, 1, n) if(a[i] == 'G') g[++cntg] = i, numg[i] = cntg;
		F(int, i, 1, n) if(a[i] == 'H') h[++cnth] = i, numh[i] = cnth;
		int cnt = 0;
		F(int, i, 1, n) {
			if(a[i] == 'G') cnt++;
			else {
				bef[i] = cnt;
				if(numh[i] != 1) aft[h[numh[i] - 1]] = cnt;
				cnt = 0;
			}
		}
		aft[h[cnth]] = cnt, cnt = 0;
		F(int, i, 1, n) {
			if(a[i] == 'H') cnt++;
			else {
				bef[i] = cnt;
				if(numg[i] != 1) aft[g[numg[i] - 1]] = cnt;
				cnt = 0;
			}
		}
		aft[g[cntg]] = cnt;
		ll ans = 0;
		F(int, i, 1, n) {
			ans += 1ll * bef[i] * aft[i];
			if(bef[i] >= 2) ans += bef[i] - 1;
			if(aft[i] >= 2) ans += aft[i] - 1;
		}
		write(ans);
	}
	
	iv Main() {
#ifdef LOCAL
		double st = clock();
#endif
		read(n), scanf("%s", a + 1);
		if(n <= 5000) Sub1_work();
		else Sub2_work();
#ifdef LOCAL
		double ed = clock();
		printf("\nTime: %.3lfs", (ed - st) / 1000000.0);
#endif
		return;
	}
}

T2 Air Cownditioning

Content

有两个长度为 \(n\) 的数组 \(a,b\)。每次操作你可以选择一个区间 \([l,r]\)，然后将下标在这个区间里面的所有 \(b_i\) 加 \(1\) 或者减 \(1\)，求最少需要多少操作才能够使得 \(\forall i\in[1,n],a_i=b_i\)。

数据范围：\(1\leqslant n\leqslant 10^5\)。

Solution

首先我们令 \(c_i=a_i-b_i\)，然后就把这道题目转换成了最少需要多少次操作使得 \(\forall i\in[1,n],c_i=0\)。然后我们就发现有一道经典的差分题目和这题非常相像，就是洛谷 P4552，只不过 P4552 是要求最少多少次操作使得所有数相等，而这道题是要求最少多少次操作使得所有数为 \(0\) 罢了。