CodeForces – 727E [字符串哈希]

发布于 2019-02-09  4,375 次阅读


题目传送门: http://codeforces.com/problemset/problem/727/E

题目大意是说给出n个长度均为k的字符串(两两不同),它们可以排成一个环,这些字符串以排列好的一个环的形式给出。问能否从​\( g(g\ge n) \)​个长度为k的字符串(两两不同)中选出n个形成之前给出的字符串环排列。如果可以请给出环排列的一个线排列。

将给出的长n*k的字符串后面放一个相同的字符串,这样从任何位置向后读n*k个字符形成的都是一个合法的环。由于是环排列,不计起点的差异, 只需要枚举前k个位置作为起点即可。从起点开始连续读取n个长度为k的字符串, 比较这n个字符串是否出现在给出的g个字符串中, 比较的时候采用hash来比较, 预处理一下给出的g个字符串, 如果hash一样就可以认为两个字符串一样。我看别人写的代码单hash可以AC, 我写的就是要碰撞, 换了MOD还是要碰撞,就写了个双hash。就算用了hash还是会TLE,采用线段树来计算hash。由于不涉及到区间的修改, 所以线段树只需要写query的部分就行了。

AC代码:

(其实这份代码基本上是卡着时限过的, 也不知道有没有什么更好的办法可以过)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef unsigned long long int ulg;
const int MAXN = (int) 2e6 + 5;
const ulg MOD1 = (ulg) 1e9 + 7;
const ulg MOD2 = (ulg) 1e9 + 9;
ulg pow1[MAXN];
ulg pow2[MAXN];

inline void init() {
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        pow1[i] = pow1[i - 1] * 0x13 % MOD1;
        pow2[i] = pow2[i - 1] * 0x13 % MOD2;
    }
}

inline pair<ulg, ulg> getstrhash(const char s[]) {
    ulg ret1 = 0;
    ulg ret2 = 0;
    int idx = -1;
    while (s[++idx] != '\0') {
        ret1 = (ret1 + (s[idx] - 'a') * pow1[idx]) % MOD1;
        ret2 = (ret2 + (s[idx] - 'a') * pow2[idx]) % MOD2;
    }
    return make_pair(ret1, ret2);
}

inline int find(const vector<pair<ulg, ulg>> &v, pair<ulg, ulg> val) {
    for (unsigned i = 0; i < v.size(); ++i) {
        if (v[i] == val) { return i; }
    }
    return -1;
}

struct segTreeNode {
    pair<ulg, ulg> data;
    int l, r;

    inline int mid() { return (l + r) >> 1; }

    inline int len() { return (r - l + 1); }
} segTree[MAXN << 2];

void build(int root, const char a[], int l, int r) {
    if (l > r)return;
    segTree[root].l = l;
    segTree[root].r = r;
    if (l == r) {
        segTree[root].data.first = segTree[root].data.second = (ulg) a[r] - 'a';
        return;
    }
    int mid = segTree[root].mid();
    build(root << 1, a, l, mid);
    build(root << 1 | 1, a, mid + 1, r);
    segTree[root].data.first = (segTree[root << 1].data.first +
                                segTree[root << 1 | 1].data.first * pow1[segTree[root << 1].len()] % MOD1) % MOD1;
    segTree[root].data.second = (segTree[root << 1].data.second +
                                 segTree[root << 1 | 1].data.second * pow2[segTree[root << 1].len()] % MOD2) % MOD2;
}

pair<ulg, ulg> query(int root, int ql, int qr) {
    if (segTree[root].l > qr || segTree[root].r < ql) {
        return make_pair(0, 0);
    }
    if (segTree[root].l >= ql && segTree[root].r <= qr) { return segTree[root].data; }
    int mid = segTree[root].mid();
    if (mid < ql) { return query(root << 1 | 1, ql, qr); }
    else if (mid >= qr) {
        return query(root << 1, ql, qr);
    }
    else {
        auto hl = query(root << 1, ql, mid);
        auto hr = query(root << 1 | 1, mid + 1, qr);
        return make_pair((hl.first + hr.first * pow1[mid - ql + 1] % MOD1) % MOD1,
                         (hl.second + hr.second * pow2[mid - ql + 1] % MOD2) % MOD2);
    }
}

int main() {
    init();
    char str[MAXN];
    char tmp[MAXN];
    int n, k;
    scanf("%d%d", &n, &k);
    scanf("%s", str);
    for (int j = n * k; j < 2 * n * k; ++j) { str[j] = str[j - n * k]; }
    str[2 * n * k] = '\0';
    build(1, str, 0, 2 * n * k);
    int g;
    scanf("%d", &g);
    vector<pair<ulg, ulg>> hsh;
    for (int c = 0; c < g; ++c) {
        scanf("%s", tmp);
        hsh.push_back(getstrhash(tmp));
    }
    vector<int> res;
    bool valid = true;
    int mark[MAXN];
    fill(mark, mark + MAXN, 0);
    for (int st = 0; st < k; ++st) {
        valid = false;
        res.clear();
        for (int j = 1; j <= n; ++j) {
            pair<ulg, ulg> hs = query(1, st + (j - 1) * k, st + j * k - 1);
            int idx = find(hsh, hs);
            if (idx == -1 || mark[idx])break;
            mark[idx] = 1;
            res.push_back(idx);
        }
        if (res.size() == n) {
            printf("YES\n");
            for (auto it = res.begin(); it != res.end(); ++it) {
                printf("%d%s", 1 + *it, it == res.end() - 1 ? "\n" : " ");
            }
            valid = true;
            break;
        }
        for (auto &i:res) { mark[i] = 0; }
    }
    if (!valid) printf("NO\n");
    return 0;
}

终有一日, 仰望星空