题目传送门: 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; }
Comments | NOTHING