cf round917 B题讲解

Problem - B - Codeforces

假设我们有一串字符串，我们把它编为s1s2s3s4s5s6……sn,题目中所说对该字符串进行任意次数的1或者2操作，得到一个非空子串，问这样的子串有多少个。

1.假设我们对子串操作4次，这4次分别是什么操作我们暂时不管，那么，最终得到的子串长度是多少，肯定是n-4吧，再看看我们这4次能够触碰到的字符在什么范围，肯定是[s1,s5]之间吧。为什么是[s1,s5]之间，最简单的，你一直使用操作2是不是把s2到s5都删了，剩下s1s6……sn，我们都已经每次使用操作2了，及每次先删后头的，依旧无法触碰s6，说明我们的触碰范围在[s1,s5]之间。

2.明白了这个，我们再来看下一个知识点，既然是任意操作，是不是说明我们可以控制我们要剩下的字符，比如我们要剩下s3,我们可以先进行两次操作1删去s1s2，然后剩下的都进行操作2，删除s4和s5，最终是不是剩下了s3了，另外我们不难发现，固定次数的操作，比如操作k次，会留下[s1,sk+1]中的一个字符，而sk+2sk+3……sn这一段是不会变的，那么k次操作得到的不同字符串就是[s1,sk+1]中不同字符的个数不是吗。

我们再来捋一捋

1中我讲了，固定次数的操作剩下字符串的长度是固定的，也是唯一的，且操作范围也是固定的。

2中我讲了，我们可以通过操作剩下操作范围范围内的任意一个字符。及固定操作次数可以得到的不同子串是操作范围内的不同字符的数量。

综上，操作次数的范围是[0,n-1],如果操作n次得到的就是空子串了，我们只需要遍历字符串，并记录该字符串前面不相同字符的个数，并加和起来。

下面是代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<unordered_map>
#include<sstream>
#include<map>
#include <array>
#include <string>
#include<numeric>
#include<set>
#include <random>
#include <unordered_set>

using i64 = long long;
void solve() {
	int n;
	std::cin >> n;
	std::string s;
	std::cin >> s;
	std::array<int, 26>cnt{};
	int dist = 0,ans=0;
	for (auto c : s) {
		//统计该字符前面出现过的不同的字符
		dist += cnt[c - 'a']++ == 0;
		ans += dist;
	}
	std::cout << ans << '\n';
}
int main() {
	int t;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}