1. 题目描述
由$n \times n, n \in [1, 5]$的正方形由$2 \times n \times (n+1)$根木棍组成，可能已经有些木棍被破坏，求至少还需破坏多少木根，可以使得不存在任何正方形？
2. 基本思路
这是一道非常有趣的题目，可以使用IDA*解也可以用DLX解。可以试试5 0这组数据比较两者的性能差异。
(1) IDA*
使用IDA*处理，是因为最后的解的范围一定不是很大，因为数据很小。至多也就60根木棍。
首先可以预处理分别对正方形和木棍进行编号，进而预处理破坏每根木棍可以影响的正方形。
由于木棍和正方形都不超过60个，因此可以采用longlong进行状态压缩，一定要装压，否则就哭吧。
每次选择当前仍然存在的最小正方形，然后枚举它的每条边进行深搜。
(2) DLX
使用DLX解这道题很容易理解， 而且解5 0这组数据也很快。
首先仍然可以使用上述的预处理方法。从而可以得到当前木棍中仍然存在的正方形。
如果，当前不存在正方形则直接输出0。否则以正方形的个数初始化DLX。
接下来，枚举每条边，搜索它可以影响到的正方形，建立一个可行方案。
直接套用DLX可解，注意DLX加入H函数可以加速，而且效果还是挺明显的。
3. 代码
(1)IDA*
/* 1084 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define INF 0x3f3f3f3f
#define mset(a, val) memset(a, (val), sizeof(a)) #define LL long long typedef struct {
vector<LL> sq;
int sz;
} sqInfo_t; const int maxm = ;
int rowId[][];
int colId[][];
int n, tot;
LL st;
sqInfo_t sqInfo[]; void init_sq(int n) {
int cnt = ;
sqInfo_t& info = sqInfo[n];
vector<LL>& sq = info.sq;
int& sz = info.sz; rep(i, , n) {
rep(j, , n)
rowId[i][j] = cnt++;
rep(j, , n+)
colId[i][j] = cnt++;
}
rep(j, , n)
rowId[n][j] = cnt++; cnt = ;
rep(i, , n) {
rep(j, , n) {
rep(k, , n+) {
if (i+k>n || j+k>n)
break; LL val = ; // Top
rep(l, , k) {
val |= (1LL << rowId[i][j+l]);
} // Left
rep(l, , k) {
val |= (1LL << colId[i+l][j]);
} // Down
rep(l, , k) {
val |= (1LL << rowId[i+k][j+l]);
} // Right
rep(l, , k) {
val |= (1LL << colId[i+l][j+k]);
} sq.pb(val);
++sz;
}
}
}
} void init() {
rep(i, , )
init_sq(i);
} bool dfs(int m, LL cst) {
const int& sz = sqInfo[n].sz;
const vector<LL>& sq = sqInfo[n].sq;
int h = ;
LL st = -, tmp = cst; rep(i, , sz) {
if ((tmp & sq[i]) == sq[i]) {
++h;
tmp ^= sq[i];
if (st < )
st = sq[i];
}
} if(h == )
return true; if (m < h)
return false; rep(i, , tot) {
if (st & (1LL << i)) {
if ( dfs(m-, cst^(1LL<<i)) ) return true;
}
}
return false;
} void solve() {
int ans = -; for (int i=; i<=tot; ++i) {
if (dfs(i, st)) {
ans = i;
break;
}
} printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t; init();
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
tot = n*(n+)*;
int k, x;
st = (1LL << tot) - ; scanf("%d", &k);
while (k--) {
scanf("%d", &x);
--x;
st ^= (1LL << x);
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
(2)Dancing Links
/* 1084 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define INF 0x3f3f3f3f
#define mset(a, val) memset(a, (val), sizeof(a)) #define LL __int64 typedef struct {
static const int maxr = ;
static const int maxc = ;
static const int maxn = maxr * maxc; int n, sz;
int S[maxc];
bool visit[maxc]; int col[maxn];
int L[maxn], R[maxn], U[maxn], D[maxn]; int ansd; void init(int _n) {
n = _n; rep(i, , n+) {
L[i] = i - ;
R[i] = i + ;
U[i] = i;
D[i] = i;
col[i] = i;
} L[] = n;
R[n] = ; sz = n + ;
memset(S, , sizeof(S));
ansd = INF;
} void addRow(const vi& columns) {
int first = sz;
int size = SZ(columns); rep(i, , size) {
const int& c = columns[i]; L[sz] = sz - ;
R[sz] = sz + ; D[sz] = c;
U[sz] = U[c];
D[U[c]] = sz;
U[c] = sz; col[sz] = c; ++S[c];
++sz;
} L[first] = sz - ;
R[sz-] = first;
} void remove_col(int c) {
for (int i=D[c]; i!=c; i=D[i]) {
L[R[i]] = L[i];
R[L[i]] = R[i];
--S[col[i]];
}
} void restore_col(int c) {
for (int i=D[c]; i!=c; i=D[i]) {
L[R[i]] = i;
R[L[i]] = i;
++S[col[i]];
}
} int H() {
int ret = ; memset(visit, false, sizeof(visit));
for (int i=R[]; i; i=R[i]) {
if (visit[col[i]])
continue; ++ret;
visit[col[i]] = true;
for (int j=D[i]; j!=i; j=D[j]) {
for (int k=R[j]; k!=j; k=R[k]) {
visit[col[k]] = true;
}
}
} return ret;
} void dfs(int d) {
int delta = H(); if (d+delta >= ansd)
return ; if (R[] == ) {
ansd = d;
return ;
} int c = R[];
for (int i=R[]; i; i=R[i]) {
if (S[i] < S[c])
c = i;
} for (int i=D[c]; i!=c; i=D[i]) {
remove_col(i);
for (int j=R[i]; j!=i; j=R[j]) {
remove_col(j);
}
dfs(d + );
for (int j=L[i]; j!=i; j=L[j]) {
restore_col(j);
}
restore_col(i);
}
} } DLX; typedef struct {
vector<LL> sq;
int sz;
} sqInfo_t; DLX solver;
const int maxm = ;
bool mark[maxm];
int valid[maxm];
int rowId[][];
int colId[][];
int n, tot;
LL st;
sqInfo_t sqInfo[]; void init_sq(int n) {
int cnt = ;
sqInfo_t& info = sqInfo[n];
vector<LL>& sq = info.sq;
int& sz = info.sz; rep(i, , n) {
rep(j, , n)
rowId[i][j] = cnt++;
rep(j, , n+)
colId[i][j] = cnt++;
}
rep(j, , n)
rowId[n][j] = cnt++; cnt = ;
rep(i, , n) {
rep(j, , n) {
rep(k, , n+) {
if (i+k>n || j+k>n)
break; LL val = ; // Top
rep(l, , k) {
val |= (1LL << rowId[i][j+l]);
} // Left
rep(l, , k) {
val |= (1LL << colId[i+l][j]);
} // Down
rep(l, , k) {
val |= (1LL << rowId[i+k][j+l]);
} // Right
rep(l, , k) {
val |= (1LL << colId[i+l][j+k]);
} sq.pb(val);
++sz;
}
}
}
} void init() {
rep(i, , )
init_sq(i);
} void solve() {
const vector<LL>& sq = sqInfo[n].sq;
const int& sz = sqInfo[n].sz;
int m = ; rep(i, , sz) {
if ((st & sq[i]) == sq[i]) {
valid[m++] = i;
}
} if (m == ) {
puts("");
return ;
} solver.init(m); rep(i, , tot) {
if (mark[i]) {
vi vc; rep(j, , m) {
if (sq[valid[j]] & (1LL << i))
vc.pb(j+);
} if (SZ(vc) > ) {
solver.addRow(vc);
}
}
} solver.dfs();
int ans = solver.ansd; printf("%d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t; init();
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
memset(mark, true, sizeof(mark));
tot = n*(n+)*;
int k, x;
st = (1LL << tot) - ; scanf("%d", &k);
while (k--) {
scanf("%d", &x);
mark[--x] = false;
st ^= (1LL << x);
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
4. 数据生成器
import sys
import string
from random import randint, shuffle def GenData(fileName):
with open(fileName, "w") as fout:
t = 20
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(1, 5)
tot = n * (n + 1)
taken = randint(1, tot)
L = range(1, tot+1)
shuffle(L)
fout.write("%d %d\n" % (n, taken))
fout.write(" ".join(map(str, L[:taken])) + "\n") def MovData(srcFileName, desFileName):
with open(srcFileName, "r") as fin:
lines = fin.readlines()
with open(desFileName, "w") as fout:
fout.write("".join(lines)) def CompData():
print "comp"
srcFileName = "F:\Qt_prj\hdoj\data.out"
desFileName = "F:\workspace\cpp_hdoj\data.out"
srcLines = []
desLines = []
with open(srcFileName, "r") as fin:
srcLines = fin.readlines()
with open(desFileName, "r") as fin:
desLines = fin.readlines()
n = min(len(srcLines), len(desLines))-1
for i in xrange(n):
ans2 = int(desLines[i])
ans1 = int(srcLines[i])
if ans1 > ans2:
print "%d: wrong" % i if __name__ == "__main__":
srcFileName = "F:\Qt_prj\hdoj\data.in"
desFileName = "F:\workspace\cpp_hdoj\data.in"
GenData(srcFileName)
MovData(srcFileName, desFileName)