ABC-375-D - ABA · znzryb
## 题目大意
给定一个字符串 $S$，求有多少个三元组 $(i, j, k)$ 满足 $1 \le i < j < k \le |S|$ 且 $S_i = S_k$。
## AC代码与思路
可以想办法简化这个的计算(用前缀和)
比较具象化的就是这个
然后就AC了，记得开long long
AC [https://atcoder.jp/contests/abc375/submissions/58758528](https://atcoder.jp/contests/abc375/submissions/58758528)
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans=0;
long long sum[30],cnt[30];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int n=s.size();
for(int i=0;i<n;i++) {
int idx=s[i]-'A';
ans+=(i*cnt[idx]-sum[idx]-cnt[idx]);
sum[idx]+=i;
cnt[idx]++;
}
cout<<ans<<endl;
return 0;
}
```
## 心路历程（其他超时代码）
我写的逻辑简单但超时代码
[https://atcoder.jp/contests/abc375/submissions/58745887](https://atcoder.jp/contests/abc375/submissions/58745887)
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
string s;
long long ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int n=s.size();
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(s[i]==s[j])
ans+=j-i-1;
}
}
cout<<ans<<endl;
return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58745887
```
优化了一下，现在只TLE 4个点了
[https://atcoder.jp/contests/abc375/submissions/58746864](https://atcoder.jp/contests/abc375/submissions/58746864)
```cpp
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
map<char,vector<int> > a;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int n=s.size();
for(int i=0;i<n;i++) {
a[s[i]].push_back(i);
}
for(map<char,vector<int> >::iterator it=a.begin();it!=a.end();it++) {
vector<int> temp=it->second;
for(int i=0;i<temp.size();i++) {
for(int j=i+1;j<temp.size();j++)
ans+=temp[j]-temp[i]-1;
}
}
cout<<ans<<endl;
return 0;
}
//TLE https://atcoder.jp/contests/abc375/submissions/58746864
```
AI的AC代码：
[https://atcoder.jp/contests/abc375/submissions/58722299](https://atcoder.jp/contests/abc375/submissions/58722299)
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
long long count_palindromic_triples(const string &S) {
int n = S.size();
// 左侧和右侧字符频率计数
unordered_map<char, long long> left_count, right_count;
// 初始化所有字符都在右侧
for (char c : S) {
right_count[c]++;
}
long long result = 0;
// 遍历每一个可能的中间字符
for (int j = 0; j < n; ++j) {
char middle_char = S[j];
// 把当前的中间字符从右侧移到左侧
right_count[middle_char]--;
// 统计左右侧相同字符的三元组个数
for (const auto& pair : left_count) {
char char_in_left = pair.first;
result += left_count[char_in_left] * right_count[char_in_left];
}
// 将当前中间字符添加到左侧计数
left_count[middle_char]++;
}
return result;
}
int main() {
string S;
cin >> S;
cout << count_palindromic_triples(S) << endl;
return 0;
}
```
算法优化了，但WA了6个点
[https://atcoder.jp/contests/abc375/submissions/58757772](https://atcoder.jp/contests/abc375/submissions/58757772)
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <iterator>
using namespace std;
string s;
long long ans;
int sum[30],cnt[30];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int n=s.size();
for(int i=0;i<n;i++) {
int idx=s[i]-'A';
ans+=i*cnt[idx]-sum[idx]-cnt[idx];
sum[idx]+=i;
cnt[idx]+=1;
}
cout<<ans<<endl;
return 0;
}
```
我说怎么会没过，原来是没开long long