zoj 3817 Chinese Knot(hash+暴力)

题目链接：zoj 3817 Chinese Knot

题目大意：给出四个字符串，对应着同心结的四条边，现在给定一个目标串，可以从任意节点开始移动，问是否可以匹配目标串。

解题思路：用hash将四个字符串的正序和逆序处理出来，然后dfs枚举，每次保留起始位置和移动方向即可。

#include 
#include 
#include 
#include using namespace std;
typedef unsigned long long ull;
typedef pair pii;#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)const int maxn = 100005;
const ull X = 107;char str[maxn];
int N, M;
vector ans;
ull G[12][maxn], H[maxn], T[maxn];void init () {scanf("%d%d", &N, &M);for (int i = 0; i < 4; i++) {scanf("%s", str+1);G[lson(i)][N+1] = G[rson(i)][N+1] = 0;for (int j = N; j >= 1; j--) {G[lson(i)][j] = G[lson(i)][j+1] * X + (str[j] - 'a');G[rson(i)][j] = G[rson(i)][j+1] * X + (str[N-j+1] - 'a');}}scanf("%s", str+1);H[M+1] = 0;for (int j = M; j >= 1; j--)H[j] = H[j+1] * X + (str[j] - 'a');
}bool dfs (int k, int pos, int dir, int L) {if (L == 0)return true;int len = min(N - pos + 1, L);if (G[(k<<1)|dir][pos] - G[(k<<1)|dir][pos+len] * T[len] == H[M-L+1] - H[M-L+len+1] * T[len]) {ans.push_back(make_pair(k * N + (dir ? N + 1 - pos : pos), dir));L -= len;if (L == 0)return true;for (int i = 0; i < 4; i++) {for (int d = 0; d < 2; d++) {if (k == i && (d^1) == dir)continue;if (dfs(i, 1, d, L))return true;}}ans.pop_back();}return false;
}bool solve () {for (int i = 0; i < 4; i++) {for (int pos = 1; pos <= N; pos++) {for (int d = 0; d < 2; d++) {ans.clear();if (dfs(i, pos, d, M))return true;}}}return false;
}int main () {int cas;scanf("%d", &cas);T[0] = 1;for (int i = 1; i < maxn; i++)T[i] = T[i-1] * X;while (cas--) {init();if (solve()) {int p = 0;for (int k = 0; k < ans.size(); k++) {int u = (ans[k].first - 1) / N + 1, dir = ans[k].second;if (dir == 0) {for (int i = ans[k].first; i <= u * N && p < M; i++, p++) {if (p) printf(" ");printf("%d", i);}} else {for (int i = ans[k].first; i > (u-1) * N && p < M; i--, p++) {if (p) printf(" ");printf("%d", i);}}}printf("\n");} elseprintf("No solution!\n");}return 0;
}

题目链接：zoj 3817 Chinese Knot

题目大意：给出四个字符串，对应着同心结的四条边，现在给定一个目标串，可以从任意节点开始移动，问是否可以匹配目标串。

解题思路：用hash将四个字符串的正序和逆序处理出来，然后dfs枚举，每次保留起始位置和移动方向即可。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！