E. Swapping Characters 一个喳喳的做法

http://codeforces.com/contest/903/problem/E

题意是，对于每个字符串都要交换两个位置的字符（id），使得结果所有字符串是一样的，输出那个字符串。

正解是，先比较两个字符串，如果他们不同的位置 > 4那就是不行的了

有4个不同的还是可行的，比如：

abab

baba

因为每个字符串都有一次交换机会，所以可以变成

baab即可

如果小于4，那么暴力枚举每一个不同的位置，和任意一个位置交换，暴力check，复杂度5000^2

我的渣渣做法。

因为n*k<5000

预处理每一个字符串，所有交换情况后得到字符串的hash值，知道原串的hash值，交换两个字符后，得到的hash值可以O（1）搞出来

然后相当于给k个数组，问是否存在一个数字在这k个数组中都存在过。

复杂度n^2 log n

#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][maxn];

unsigned long long int po[maxn];

const int seed = ;

int cnt[maxn], DFN;

struct Node {

    unsigned long long int val;

    int one, two;

    Node(unsigned long long int _val, int _one, int _two) {

        val = _val, one = _one, two = _two;

    }

    bool operator < (const struct Node & rhs) const {

        return val < rhs.val;

    }

};

vector<Node> vc[maxn];

void work() {

    int k, n;

    scanf("%d%d", &k, &n);

    for (int i = ; i <= k; ++i) scanf("%s", str[i] + );

    if (k == ) {

        swap(str[][], str[][]);

        printf("%s\n", str[] + );

        printf("\n");

        return;

    }

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

        unsigned long long int now = ;

        bool can = false;

        DFN++;

        for (int j = ; j <= n; ++j) {

            now = now * seed + str[i][j];

            can |= cnt[str[i][j]] == DFN;

            cnt[str[i][j]] = DFN;

        }

        if (can) vc[i].push_back(Node(now, , ));

        for (int j = ; j <= n; ++j) {

            for (int f = j + ; f <= n; ++f) {

                if (str[i][j] == str[i][f]) {

                    if (can) continue;

                    can = true;

                }

                unsigned long long int ha = now - str[i][j] * po[n - j] - str[i][f] * po[n - f] + str[i][f] * po[n - j] + str[i][j] * po[n - f];

                vc[i].push_back(Node(ha, j, f));

//                swap(str[i][j], str[i][f]);

//                cout << str[i] + 1 << "  " << ha << endl;

//                swap(str[i][j], str[i][f]);

            }

        }

//        cout << endl;

        sort(vc[i].begin(), vc[i].end());

    }

//    for (int i = 1; i <= k; ++i) {

//        for (int j = 0; j < vc[i].size(); ++j) {

//            cout << vc[i][j].val << " ";

//        }

//        cout << endl;

//    }

    for (int i = ; i < vc[].size(); ++i) {

        int t = ;

        for (int j = ; j <= k; ++j) {

            if (vc[][i].val > vc[j].back().val) break;

            int pos = lower_bound(vc[j].begin(), vc[j].end(), vc[][i]) - vc[j].begin();

            if (vc[j][pos].val != vc[][i].val) break;

            t++;

        }

        if (t == k) {

            int id1 = vc[][i].one, id2 = vc[][i].two;

            swap(str[][id1], str[][id2]);

            printf("%s\n", str[] + );

            return;

        }

    }

    printf("-1\n");

}

int main() {

#ifdef local

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

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

#endif

    po[] = ;

    for (int i = ; i <= maxn - ; ++i) po[i] = po[i - ] * seed;

    work();

    return ;

}

巴特西

E. Swapping Characters 一个喳喳的做法

最新文章

热门文章