Background :
写总结，总的来说今天题目写的很慢，因为赛前知道考察的范围是搜索，毕竟除了一些基本的搜索方法还是知道这方面不是很有心得，总之今天的比赛我的时侯目标，是 “求不乱”，在代码不乱的基础上争取一次编码通过，不过看来呀今天的策略很成功的帮助我拿到了参加 Summer Contest集训队 的第一个Rank I（撒个花哦 \>. < ～）。。
先快速扫题，发现 Problem B，和 Problem C 都是做过的，而且第三题N皇后可以应用N皇后问题位运算方法快速编码实现，于是先拆这题，11min1A。
之后考虑先写 Problem A 还是 Problem B，因为那时A题有几个疑问的地方，决定还是动手写B。
ACM 的比赛因为数据会多组一起出现，所以换写周界搜索，还是比较有把握 1h.27min 出解。
（此题有一个可能造成 PE 的地方，就是当路径长度为 0 时，考虑到这两题在一中的时侯都给高一的新生们讲过课，所以可以直接看到，1A）
剩下的时间慢慢磕第三题，准备的也比较充分，在比赛结束15分钟前 1A ...
Archieve :
贴代码:。。。 patch() 部分是调试的时侯用的。。要保留比赛的气氛。。
#include
using namespace std;
const int N = 120+2;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0 , 1}};
char a[N][N], b[N][N];
int n, m, ans;
int r(int i){
if (i==0) return 1;
if (i==1) return 0;
if (i==2) return 3;
if (i==3) return 2;
}
void patch(){
for (int i=0;i> m;
int xx, yy, xxx, yyy, bonus;
for (int i=0;i<4;i++){
if (i==l) continue;
xx = x + dir[i][0]; yy = y + dir[i][1];
if (a[xx][yy]!='.') continue;
bonus = 1; xxx = xx + dir[i][0]; yyy = yy + dir[i][1];
while (a[xxx][yyy]=='.'){
a[xx][yy] = 'o'; bonus++;
xx = xxx; yy = yyy; xxx += dir[i][0]; yyy += dir[i][1];
}
ans = max(ans, s + bonus);
if (a[xxx][yyy]=='#')
dfs(xx, yy, r(i), s + bonus);
while (xx!=x||yy!=y) {
a[xx][yy]='.';
xx -= dir[i][0]; yy -= dir[i][1];
}
//cout << "dir:" << i << endl;
// patch(); cin >> m;
}
a[x][y] = '.';
}
void init(){
int x, y; char z;
memset(a, '.', sizeof(a));
for (int i=0;i> n >> m){
init(); ans = 1; dfs(1, 1, -1, 1);
cout << ans << endl;
}
}
#include
#include
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320};
int queue[40320], dist[40320], parient[40320]; char operation[40320];
int hash[40320];
int head, tail, goal;
int a[8]; bool c[8];
int cantor(){
int x = 0, t, i, j;
for (i=0;i<8;i++){
for (j=i+1,t=0;j<8;j++)
if (a[i]>a[j]) t++;
x = x * (8-i) + t;
}
return x;
}
void recover(int x){
memset(c, false, sizeof(c));
memset(a, 0, sizeof(a));
int t, i;
for (i=0;i<8;i++){
while (c[a[i]]) a[i]++;
while (x >= F[7-i]){
x -= F[7-i]; a[i]++;
while (c[a[i]]) a[i]++;
}
c[a[i]++] = true;
}
}
void patch(){
for (int i=0;i<8;i++)
cout << a[i] << " ";
cout << endl;
}
void enqueue(int code, char op){
if (hash[code][/code]==-1){
queue[tail] = code; dist[tail] = dist[head] + 1; parient[tail] = head; operation[tail] = op;
hash[code][/code] = tail++;
}
}
void operate_A(){
for (int i=0;i<4;i++) swap(a[i], a[7-i]); enqueue(cantor(), 'A');
for (int i=0;i<4;i++) swap(a[i], a[7-i]);
}
void operate_B(){
int t = a[0]; a[0] = a[3]; a[3] = a[2]; a[2] = a[1]; a[1] = t;
t = a[7]; a[7] = a[4]; a[4] = a[5]; a[5] = a[6]; a[6] = t; enqueue(cantor(), 'B');
t = a[0]; a[0] = a[1]; a[1] = a[2]; a[2] = a[3]; a[3] = t;
t = a[7]; a[7] = a[6]; a[6] = a[5]; a[5] = a[4]; a[4] = t;
}
void operate_C(){
int t = a[1]; a[1] = a[6]; a[6] = a[5]; a[5] = a[2]; a[2] = t; enqueue(cantor(), 'C');
t = a[1]; a[1] = a[2]; a[2] = a[5]; a[5] = a[6]; a[6] = t;
}
void bfs(){
dist[0] = 0; head = 0; tail = 1;
memset(hash, -1, sizeof(hash));
hash[queue[0]] = 0;
int p;
while (head
#include
using namespace std;
int n, m, s;
void dfs(int z, int l, int r){
// cout << z << endl;
if (z!=m){
int p, q;
q = m&~(z|l|r);
while (q!=0){
p = q&-q; q-=p;
dfs(z+p, (l+p)<<1, (r+p)>>1);
}
}
else s++;
}
int main(){
while (cin >> n){
m = (1 << n) - 1; s = 0; dfs(0, 0, 0);
cout << s << endl;
}
}
External link :
HIT ACM 2010 Summer Contest 08 搜索练习
M67 位运算讲解系列文章（目录）
IOI'96 Magic Squares 魔板 译 by Felicia Crazy
... PS ：前几天的时侯 xiaodai 说结拜OI兄弟，～ 我觉得前缀换成 ACM 更好一些。。。
ゆっくり読んでください ...