Hướng dẫn giải của Bedao Regular Contest 03 - KINDNESS


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Dễ dàng nhận thấy là các xâu khác xâu ban đầu nhận được bằng cách đổi chỗ ~2~ kí tự khác nhau. Gọi ~cnt_c~ là số lượng kí tự ~c~ có trong xâu và ~n~ là độ dài xâu trong xâu thì số xâu khác xâu ban đầu sẽ bằng: ~\frac{1}{2}\sum_{c=a}^{z} cnt_c\times(n-cnt_c)~

Tuy nhiên nếu trong xâu có kí tự ~c~ nào đó mà ~cnt_c>1~ thì khi đổi chỗ ~2~ kí tự giống nhau đó thì ta còn nhận được thêm xâu ban đầu. Nên nếu có ~cnt_c>1~ thì đáp án sẽ phải cộng thêm ~1~.

Độ phức tạp: ~O(n \times 26)~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int f[39];

int main()
{
    fastIO

    string s;
    cin>>s;

    int n = s.size();
    s = ' ' + s;

    ll cnt = 1;
    for (int i = 1;i <= n; ++i) f[s[i]-'a']++;

    bool flag = true;

    for (int i = 0; i < 26; ++i)
        if (f[i] > 1)
            flag = false;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 26; ++j)
                if (j != s[i] - 'a') cnt += f[j];
        --f[s[i]-'a'];
    }

    return cout<<cnt-flag, 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.