这题乍一看挺难的，没关系，我说过（其实并没有），做 CodeForces 的题的第一步是手推样例。

我们看一看下面一组样例。

CPP

10
1 2 1 2 3 3 2 1 3

如果你把为 1 2 3 的子序列列举出来就可以看到，要么开头往前跑，要么结尾往后跑。

可以证明，因为如果找到可以淘汰备选子串的子序列，它的元素顺序是不变的。所以只要头尾不跑开，中间元素因为要保持顺序，也没法跑出去。

那如何阻止头尾逃跑呢？

如果头元素为第一次出现，尾元素为最后一次出现，那么它们就都没地方跑，这个子串就符合要求。

代码实现：

对于一个位置，当这个位置为头元素时，它的贡献是它后面（包括它）所有最后出现的元素数量。这你要直接枚举的话，时间必爆。要用后缀和优化。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int T,n;
int a[N],sum[N];
map<int,int>mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n+1;i++) sum[i]=0;
		mp.clear();
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=n;i;i--){
			mp[a[i]]++;//技术思想 
			sum[i]=sum[i+1]+(mp[a[i]]==1);//后缀和 
		}
		long long ans=0;
		mp.clear();
		for(int i=1;i<=n;i++){
			mp[a[i]]++;
			ans+=sum[i]*(mp[a[i]]==1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

CF1883F You Are So Beautiful

文章操作

代码实现：

相关推荐

评论

CF1883F You Are So Beautiful