Znzryb's Blog
0%

ABC-375-D - ABA

Posted on Edited on

题目大意

给定一个字符串 SS，求有多少个三元组 (i,j,k)(i, j, k) 满足 1≤i<j<k≤∣S∣1 \le i < j < k \le |S| 且 Si=SkS_i = S_k。

AC代码与思路

image

可以想办法简化这个的计算(用前缀和)

比较具象化的就是这个

image

然后就AC了，记得开long long

AC https://atcoder.jp/contests/abc375/submissions/58758528

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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