基本情况
A题秒了,B题卡了一年。
B. Erase First or Second Letter
卡题分析
两方面原因
- 没有变通，一开始的思路是公式算出总字串数再想办法找重复的减掉，但搞了一个小时都不可行，应该早点换成正着来找的思路。
- 没有更深入的分析样例。
最后虽然出来了，但是 +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';
}