某岛

… : "…アッカリ~ン . .. . " .. .
August 5, 2010

Summer Contest VIII. 搜索练习

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 更好一些。。。