HDU_2518
这个题目明显就是裸的Dancing Links，只不过由于情况实在太多了，写起来超级繁琐，而且写完之后几乎不可能在规定时间内出解（大家交的都是0ms的，估计都是打表交的），于是就只好把6种情况的结果存到数组里直接输出了。
View Code // 打表程序 #include#include #define MAXN 5810#define MAXM 80#define MAXD 35510#define HASH 100007#define SIZE 100010#define INF 0x3f3f3f3ftypedef long long LL;int dx[8][12][4] ={ { // 0 { 1, 2, 2, 2}, // 1 { 0, 0, 0, 0}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 1, 1}, // 4 { 1, 1, 1, 1}, // 5 { 1, 1, 2, 2}, // 6 { 1, 1, 1, 1}, // 7 { 1, 1, 1, 2}, // 8 { 1, 1, 2, 2}, // 9 { 1, 2, 2, 2}, // 10 { 0, 1, 1, 1}, // 11 { 0, 0, 1, 1}, // 12 }, { // 1 { 1, 2, 2, 2}, // 1 { 1, 2, 3, 4}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 2, 2}, // 4 { 1, 2, 3, 3}, // 5 { 1, 1, 2, 2}, // 6 { 1, 2, 2, 3}, // 7 { 0, 1, 2, 2}, // 8 { 1, 1, 1, 2}, // 9 { 1, 1, 1, 2}, // 10 { 0, 1, 1, 2}, // 11 { 1, 2, 2, 3}, // 12 }, { // 2 { 0, 0, 1, 2}, // 1 { 0, 0, 0, 0}, // 2 { 1, 1, 1, 2}, // 3 { 0, 0, 1, 1}, // 4 { 0, 0, 0, 1}, // 5 { 0, 1, 1, 2}, // 6 { 0, 0, 0, 1}, // 7 { 1, 1, 1, 2}, // 8 { 0, 1, 1, 2}, // 9 { 0, 0, 1, 2}, // 10 { 0, 0, 1, 1}, // 11 { 0, 1, 1, 1}, // 12 }, { // 3 { 0, 0, 1, 2}, // 1 { 1, 2, 3, 4}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 2, 2}, // 4 { 0, 1, 2, 3}, // 5 { 0, 1, 1, 2}, // 6 { 1, 1, 2, 3}, // 7 { 0, 1, 2, 2}, // 8 { 1, 1, 1, 2}, // 9 { 1, 1, 1, 2}, // 10 { 1, 1, 2, 2}, // 11 { 1, 1, 2, 3}, // 12 }, { // 4 { 1, 2, 2, 2}, // 1 { 0, 0, 0, 0}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 1, 1}, // 4 { 1, 1, 1, 1}, // 5 { 1, 1, 2, 2}, // 6 { 1, 1, 1, 1}, // 7 { 1, 1, 1, 2}, // 8 { 1, 1, 2, 2}, // 9 { 1, 2, 2, 2}, // 10 { 0, 1, 1, 1}, // 11 { 0, 0, 1, 1}, // 12 }, { // 5 { 0, 0, 1, 2}, // 1 { 1, 2, 3, 4}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 2, 2}, // 4 { 0, 1, 2, 3}, // 5 { 0, 1, 1, 2}, // 6 { 1, 1, 2, 3}, // 7 { 0, 1, 2, 2}, // 8 { 1, 1, 1, 2}, // 9 { 1, 1, 1, 2}, // 10 { 1, 1, 2, 2}, // 11 { 1, 1, 2, 3}, // 12 }, { // 6 { 0, 0, 1, 2}, // 1 { 0, 0, 0, 0}, // 2 { 1, 1, 1, 2}, // 3 { 0, 0, 1, 1}, // 4 { 0, 0, 0, 1}, // 5 { 0, 1, 1, 2}, // 6 { 0, 0, 0, 1}, // 7 { 1, 1, 1, 2}, // 8 { 0, 1, 1, 2}, // 9 { 0, 0, 1, 2}, // 10 { 0, 0, 1, 1}, // 11 { 0, 1, 1, 1}, // 12 }, { // 7 { 1, 2, 2, 2}, // 1 { 1, 2, 3, 4}, // 2 { 1, 1, 1, 2}, // 3 { 0, 1, 2, 2}, // 4 { 1, 2, 3, 3}, // 5 { 1, 1, 2, 2}, // 6 { 1, 2, 2, 3}, // 7 { 0, 1, 2, 2}, // 8 { 1, 1, 1, 2}, // 9 { 1, 1, 1, 2}, // 10 { 0, 1, 1, 2}, // 11 { 1, 2, 2, 3}, // 12 },};int dy[8][12][4] ={ { // 0 { 0, 0, 1, 2}, // 1 { 1, 2, 3, 4}, // 2 {-1, 0, 1, 0}, // 3 { 2, 0, 1, 2}, // 4 { 0, 1, 2, 3}, // 5 { 0, 1, 1, 2}, // 6 {-1, 0, 1, 2}, // 7 {-2, -1, 0, -2}, // 8 { 0, 1, -1, 0}, // 9 { 0, -1, 0, 1}, // 10 { 1, -1, 0, 1}, // 11 { 1, 2, -1, 0}, // 12 }, { // 1 { 0, -2, -1, 0}, // 1 { 0, 0, 0, 0}, // 2 {-1, 0, 1, 0}, // 3 { 1, 1, 0, 1}, // 4 { 0, 0, 0, -1}, // 5 {-1, 0, -2, -1}, // 6 { 0, -1, 0, 0}, // 7 { 1, 1, 1, 2}, // 8 {-1, 0, 1, 1}, // 9 {-2, -1, 0, 0}, // 10 { 1, 0, 1, 1}, // 11 { 0, 0, 1, 1}, // 12 }, { // 2 { 1, 2, 2, 2}, // 1 { 1, 2, 3, 4}, // 2 {-1, 0, 1, 0}, // 3 { 1, 2, 0, 2}, // 4 { 1, 2, 3, 3}, // 5 { 1, 1, 2, 2}, // 6 { 1, 2, 3, 2}, // 7 {-2, -1, 0, -2}, // 8 { 1, -1, 0, 0}, // 9 { 1, 2, 1, 1}, // 10 { 1, 2, 0, 1}, // 11 { 1, -2, -1, 0}, // 12 }, { // 3 { 1, 2, 0, 0}, // 1 { 0, 0, 0, 0}, // 2 {-1, 0, 1, 0}, // 3 { 1, 0, 0, 1}, // 4 { 1, 0, 0, 0}, // 5 { 1, -1, 0, -1}, // 6 { 0, 1, 0, 0}, // 7 { 1, 1, 1, 2}, // 8 { 0, 1, 2, 1}, // 9 { 0, 1, 2, 0}, // 10 { 0, 1, 0, 1}, // 11 { 0, 1, 1, 1}, // 12 }, { // 4 { 0, -2, -1, 0}, // 1 { 1, 2, 3, 4}, // 2 {-1, 0, 1, 0}, // 3 { 2, 0, 1, 2}, // 4 {-3, -2, -1, 0}, // 5 {-1, 0, -2, -1}, // 6 {-2, -1, 0, 1}, // 7 { 0, 1, 2, 2}, // 8 {-1, 0, 0, 1}, // 9 { 0, -1, 0, 1}, // 10 { 1, 0, 1, 2}, // 11 { 1, 2, 2, 3}, // 12 }, { // 5 { 1, 2, 2, 2}, // 1 { 0, 0, 0, 0}, // 2 {-1, 0, 1, 0}, // 3 { 1, 1, 0, 1}, // 4 { 1, 1, 1, 1}, // 5 { 1, 1, 2, 2}, // 6 {-1, 0, 0, 0}, // 7 {-1, -1, -2, -1}, // 8 {-2, -1, 0, -1}, // 9 {-2, -1, 0, 0}, // 10 {-1, 0, -1, 0}, // 11 {-1, 0, -1, -1}, // 12 }, { // 6 { 1, 2, 0, 0}, // 1 { 1, 2, 3, 4}, // 2 {-1, 0, 1, 0}, // 3 { 1, 2, 0, 2}, // 4 { 1, 2, 3, 0}, // 5 { 1, -1, 0, -1}, // 6 { 1, 2, 3, 1}, // 7 { 0, 1, 2, 2}, // 8 { 1, 1, 2, 1}, // 9 { 1, 2, 1, 1}, // 10 { 1, 2, 1, 2}, // 11 { 1, 1, 2, 3}, // 12 }, { // 7 { 0, 0, 1, 2}, // 1 { 0, 0, 0, 0}, // 2 {-1, 0, 1, 0}, // 3 { 1, 0, 0, 1}, // 4 { 0, 0, 0, 1}, // 5 { 0, 1, 1, 2}, // 6 { 0, 0, 1, 0}, // 7 { 1, 0, -1, 0}, // 8 {-1, 0, 1, -1}, // 9 { 0, 1, 2, 0}, // 10 { 1, 0, 1, 0}, // 11 { 0, -1, 0, -1}, // 12 },};struct HashMap{ int head[HASH], size, next[SIZE]; LL st[SIZE]; void init() { memset(head, -1, sizeof(head)), size = 0; } int find(LL _st) { int i, h = (_st & 0x7fffffff) % HASH; for(i = head[h]; i != -1; i = next[i]) if(_st == st[i]) break; return i; } void push(LL _st) { int i, h = (_st & 0x7fffffff) % HASH; st[size] = _st; next[size] = head[h], head[h] = size ++; }}hm;struct Info{ int d, id, x, y;}info[MAXD];int N, M, size, U[MAXD], D[MAXD], L[MAXD], R[MAXD], C[MAXD], Q[MAXN], ANS;int S[MAXM], H[MAXN], g[MAXM][MAXM], t[MAXM][MAXM];LL fac[MAXM], f[MAXM];inline int inside(int x, int y){ return x >= 1 && x <= N && y >= 1 && y <= M;}void prep(int m){ int i; for(i = 0; i <= m; i ++) { U[i] = D[i] = i; L[i + 1] = i, R[i] = i + 1; S[i] = 0; } R[m] = 0, size = m; memset(H, -1, sizeof(H));}void insert(int r, int c, int d, int id, int x, int y){ ++ size; C[size] = c, ++ S[c]; D[size] = D[c], U[size] = c; U[D[c]] = size, D[c] = size; if(H[r] == -1) H[r] = L[size] = R[size] = size; else { R[size] = R[H[r]], L[size] = H[r]; L[R[H[r]]] = size, R[H[r]] = size; } info[size].d = d, info[size].id = id, info[size].x = x, info[size].y = y;}inline int place(int d, int id, int x, int y){ int i; for(i = 0; i < 4; i ++) if(!inside(x + dx[d][id][i], y + dy[d][id][i])) return 0; return 1;}int appear(int d, int id, int x, int y){ int i; LL ans = (x - 1) * M + y; for(i = 0; i < 4; i ++) ans += f[i + 1] * ((x + dx[d][id][i] - 1) * M + y + dy[d][id][i]); if(hm.find(ans) != -1) return 1; hm.push(ans); return 0;}void init(){ int i, j, k, d, id, r = 0, c; prep(N * M + 12); hm.init(); for(d = 0; d < 8; d ++) for(id = 0; id < 12; id ++) for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) if(place(d, id, i, j) && !appear(d, id, i, j)) { ++ r; insert(r, id + 1, d, id, i, j), insert(r, (i - 1) * M + j + 12, d, id, i, j); for(k = 0; k < 4; k ++) { c = (i + dx[d][id][k] - 1) * M + j + dy[d][id][k] + 12; insert(r, c, d, id, i, j); } }}void remove(int c){ int i, j; R[L[c]] = R[c], L[R[c]] = L[c]; for(i = D[c]; i != c; i = D[i]) for(j = R[i]; j != i; j = R[j]) U[D[j]] = U[j], D[U[j]] = D[j], -- S[C[j]];}void resume(int c){ int i, j; for(i = U[c]; i != c; i = U[i]) for(j = L[i]; j != i; j = L[j]) U[D[j]] = j, D[U[j]] = j, ++ S[C[j]]; R[L[c]] = c, L[R[c]] = c;}LL encode(int g[][MAXM]){ int i, j, k = 0; LL ans = 0; for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) ans += fac[k ++] * g[i][j]; return ans;}void deal(int dep){ int i, j, k, d, id, x, y, flag = 0; LL ans; for(k = 0; k < dep; k ++) { j = Q[k]; d = info[j].d, id = info[j].id, x = info[j].x, y = info[j].y; g[x][y] = id; for(i = 0; i < 4; i ++) g[x + dx[d][id][i]][y + dy[d][id][i]] = id; } ans = encode(g); if(hm.find(ans) != -1) return; for(i = 1, x = N; i <= N; i ++, x --) for(j = 1, y = M; j <= M; j ++, y --) t[x][y] = g[i][j]; ans = encode(t); if(hm.find(ans) != -1) return; for(i = 1; i <= N; i ++) for(j = 1, y = M; j <= M; j ++, y --) t[i][y] = g[i][j]; ans = encode(t); if(hm.find(ans) != -1) return; for(i = 1, x = N; i <= N; i ++, x --) for(j = 1, y = M; j <= M; j ++, y --) g[x][y] = t[i][j]; ans = encode(g); if(hm.find(ans) != -1) return; ++ ANS, hm.push(encode(g));}void dance(int dep){ if(R[0] == 0) { deal(dep); return ; } int i, j, t = INF, id; for(i = R[0]; i != 0; i = R[i]) if(S[i] < t) t = S[i], id = i; remove(id); for(i = D[id]; i != id; i = D[i]) { for(j = R[i]; j != i; j = R[j]) remove(C[j]); Q[dep] = i, dance(dep + 1); for(j = L[i]; j != i; j = L[j]) resume(C[j]); } resume(id);}void solve(){ ANS = 0; hm.init(); dance(0); printf("%d\n", ANS);}int main(){ freopen("cin.in", "r", stdin); freopen("cout.out", "w", stdout); fac[0] = f[0] = 1; for(int i = 1; i <= 60; i ++) fac[i] = fac[i - 1] * 19, f[i] = f[i - 1] * 61; while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0;}
View Code // AC程序 #include#include #include int a[] = { 0, 0, 0, 2, 368, 1010, 2339};int main(){ int x, y; while(scanf("%d%d", &x, &y) == 2) { if(x > y) std::swap(x, y); printf("%d\n", a[x]); } return 0;}