B - Reverse and Compare 小小思维题

http://agc019.contest.atcoder.jp/tasks/agc019_b

一开始的做法是，

用总数减去回文子串数目，因为回文子串怎么翻转都不影响答案。

然后，如果翻转afucka，那么和翻转fuck，得到的串是一样的。

但是如果是先是用total - 回文子串数目，再减去afucka这样的，一头一尾相同，但是又不是回文串的字符串，复杂度要O(n^2)

考虑到回文串也是一头一尾相同的，那么相当于翻转一头一尾不相同的字符串才能得到新的贡献

相当于total - （一头一尾相同的）

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn =  *  + ;

char str[maxn];

int num[maxn];

void work() {

    scanf("%s", str + );

    int lenstr = strlen(str + );

    LL ans = 1LL * lenstr * (lenstr - ) /  + ;

    for (int i = ; i <= lenstr; ++i) {

        num[str[i]]++;

    }

    for (int i = 'a'; i <= 'z'; ++i) {

        ans -= 1LL * num[i] * (num[i] - ) / ;

    }

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

B - Reverse and Compare 小小思维题

最新文章

热门文章