本文主要是介绍AcWing 4261.孤独的照片，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题其实也是和子串分值的题是一样的，运用贡献法的思路来算的。
这里需要强调一一点：这里的说的是不小于3的子序列，而不是全部序列。
所以，在我们算出来这个值之后，需要进行减法处理，首先需要减去只有一个字符的子字符串。然后就是两个的，之后就是正确答案了。
注意：在减去两个长度的子子串的时候需要每个子串多减去一次，因为轮流对于G和H进行贡献处理，会对于同一个字符串进行操作。
上代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<map>
#include<limits.h>
#include<set>
#define MAX 500050
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;LL n, m, counts, num;
char s[MAX];
int l[MAX];
int r[MAX];
int p[MAX];
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;cin >> s + 1;int size = strlen(s + 1);for (int i = 1; i <= size; i++) {int tmp = s[i] - 'A';l[i] = p[tmp];p[tmp] = i;}for (int i = 0; i < 26; i++)p[i] = n + 1;for (int i = size; i; i--) {int tmp = s[i] - 'A';r[i] = p[tmp];p[tmp] = i;}for (int i = 1; i <= size; i++) {counts += (LL)(i - l[i]) * (r[i] - i);}for (int i = 1; i <= size-1; i++) {if (s[i] != s[i + 1])num++;}counts = counts - num*2 - n;cout << counts << endl;return 0;
}这篇关于AcWing 4261.孤独的照片的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
