基本情况

A题秒了,B题卡了一年。

B. Erase First or Second Letter

Problem - B - Codeforces

卡题分析

两方面原因

没有变通，一开始的思路是公式算出总字串数再想办法找重复的减掉，但搞了一个小时都不可行，应该早点换成正着来找的思路。
没有更深入的分析样例。

最后虽然出来了，但是 +6，而且也不如正解。

oid solve()
{
	ll n, ans = 0;
	cin >> n;
	string s;
	cin >> s;
	set<char> st;
	map<char, bool> mp;
	for (int i = 0; i < n; i++)
	{
		if (!mp[s[i]]) ans++;
		mp[s[i]]=true;
	}
	st.insert(s[0]);
	for (int i = 1; i < n; i++)
	{
		set<string> ss;
		for (auto x : st)
		{
			string temp;
			temp += x; x += s[i]; ss.insert(temp);
		}
		ans += ss.size();
		st.insert(s[i]);
	}
	cout << ans << '\n';
}

正解思路

第一种思路

从第四个样例入手：

14
bcdaaaabcdaaaa

第一种操作不好直接入手考虑，直接先考虑第二种。

对于第一个 b
- 可以删 c cd cda cdaa...共 \(13\) 种，加上自己本身就有 \(14\) 种字串。
- 删除 b。
对于第一个 c
- 可以删 d da daa daaa等共 \(12\) 种，加上自己本身就有 \(13\) 种字串。
- 删除 \(c\)
对于第一个 d
- 总共有 \(12\) 种字串。
- 删除 \(d\)
对于第一个 \(a\)
- 总共有 \(11\) 种字串。
- 删除 \(a\)

注意

此时 \(14 + 13 + 12 + 11 = 50\) 已经是正确答案了。

那么后面全是重复的，属于是从结果反过来推思路。

考虑为什么重复，因为之前出现一次的字母，其构成的子串就一定包含了后面再次出现的子串（不严谨的证明，但是这方法就是对的）。

代码实现

void solve()
{
	int n, ans = 0;
	cin >> n;
	string a;
	cin >> a;
	set<char> st;
	for (int i = 0; i < n; i++)
	{
		if (st.count(a[i])) continue;
		ans += n - i; st.insert(a[i]);
	}
	cout << ans << '\n';
}

第二种思路

考虑两种操作

如果只有操作二那就是留下第一个字母加任意一个后缀。
如果只有操作一那就是删去任意一个前缀，当然留下一个后缀。

推导

一定会有个后缀留下来，就枚举这个后缀是哪个。

然后这个后缀前面的位置，根据操作二还可以选一个字母。

那就记录一下不同字母个数，就是每一个后缀能贡献的个数了。

把每个后缀的贡献加起来就是答案。

代码实现

void solve()
{
	int n, ans = 0;
	cin >> n;
	string a;
	cin >> a;
	set<char> st;
	for (int i = 0; i < n; i++)
	{
		st.insert(a[i]);
		ans += (int) st.size();
	}
	cout << ans << '\n';
}