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

八数码问题的研习笔记。

其实…现在…唯一能满足我的… 就只有用 Astar 把它解出来了。。。

#include 
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320};
int queue[362880], dist[362880]; bool hash[362880];
int head, tail, goal;
int a[9], b[2]; bool c[9];


int cantor(){
    int x = 0, t, i, j;
    for (i=0;i<9;i++){
        for (j=i+1,t=0;j<9;j++)
            if (a[i]>a[j]) t++;
        x = x * (9-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<9;i++){
        while (c[a[i]]) a[i]++;
        while (x >= F[8-i]){
            x -= F[8-i]; a[i]++;
            while (c[a[i]]) a[i]++;
        }
        c[a[i]] = true;
    }
}
int stat(){
    int  inversion_pair = 0;
    for (int i=0;i<8;i++){
        if (a[i]==0) continue;
        for (int j=i+1;j<9;j++){
            if (a[j]==0) continue;
            if (a[i]>a[j]) inversion_pair++;
        }
    }
    return inversion_pair;
}




void init(){

    int i, j, t;

    for (i=0;i<9;i++) cin >> a[i];
    queue[0] = cantor(); b[0] = stat();

    for (i=0;i<9;i++) cin >> a[i];
    goal = cantor(); b[1] = stat();
}

bool operate(int x, int y){
    swap(a[x], a[y]); queue[tail] = cantor(); swap(a[x], a[y]);

    if (hash[queue[tail]]) return false;
    dist[tail] = dist[head] + 1;
    if (queue[tail]==goal){
        cout << dist[tail] << endl;
        return true;
    }

    hash[queue[tail++]] = true;
    return false;
}

void bfs(){
    if (queue[0] == goal) {cout << 0 << endl; return;}
    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
    dist[0] = 0; head = 0; tail = 1;
    memset(hash, false, sizeof(hash));
    hash[queue[0]] = true;

    int p;
    while (true){
        recover(queue[head]);

        for (p=0;a[p]!=0;p++);
        if (p > 2) if (operate(p, p-3)) return;
        if (p < 6) if (operate(p, p+3)) return;
        if (p % 3) if (operate(p, p-1)) return;
        if ((p+1) % 3) if (operate(p, p+1)) return;
        head ++;
    }
}

int main(){
    int T; cin >> T;
    while (T--){
        init(); bfs();
    }
}
#include 
#define label exitus
using namespace std;
const int F[9] = {1,1,2,6,24,120,720,5040,40320}, FOUND = 3;
int queue[2][362880], dist[2][362880], hash[362880];
int head[2], tail[2], flag;
int a[9], b[2]; bool c[9];

int cantor(){
    int x = 0, t, i, j;
    for (i=0;i<9;i++){
        for (j=i+1,t=0;j<9;j++)
            if (a[i]>a[j]) t++;
        x = x * (9-i)  + t;
    }
    return x;
}

void recover(int x){
    memset(c, false, sizeof(c));
    memset(a, 0, sizeof(a));
    int i;
    for (i=0;i<9;i++){
        while (c[a[i]]) a[i]++;
        while (x >= F[8-i]){
            x -= F[8-i]; a[i]++;
            while (c[a[i]]) a[i]++;
        }
        c[a[i]] = true;
    }
}

int stat(){
    int  inversion_pair = 0;
    for (int i=0;i<8;i++){
        if (a[i]==0) continue;
        for (int j=i+1;j<9;j++){
            if (a[j]==0) continue;
            if (a[i]>a[j]) inversion_pair++;
        }
    }
    return inversion_pair;
}




void init(){
    
    int i;
    
    for (i=0;i<9;i++) cin >> a[i];
    queue[0][0] = cantor(); b[0] = stat();
    
    for (i=0;i<9;i++) cin >> a[i];
    queue[1][0] = cantor(); b[1] = stat();
}

inline void operate(int x, int y){
    swap(a[x], a[y]); queue[flag][tail[flag]] = cantor(); swap(a[x], a[y]);
    
    if (hash[queue[flag][tail[flag]]]==flag) return ;
    dist[flag][tail[flag]] = dist[flag][head[flag]] + 1;
    if (hash[queue[flag][tail[flag]]]== 1 - flag){
        int pos;
        for (pos=head[1-flag];queue[1-flag][pos]!=queue[flag][tail[flag]];pos++);
        cout << dist[flag][tail[flag]] + dist[1 - flag][pos] << endl;
        flag = FOUND;
        return;
    }
    
    hash[queue[flag][tail[flag]++]] = flag;
    return ;
}

inline void expand(){
    int p; recover(queue[flag][head[flag]]);
    for (p=0;a[p]!=0;p++);
    if (p > 2) {operate(p, p-3); if (flag == FOUND) return;}
    if (p < 6) {operate(p, p+3); if (flag == FOUND) return;}
    if (p % 3) {operate(p, p-1); if (flag == FOUND) return;}
    if ((p+1) % 3) {operate(p, p+1); if (flag == FOUND) return;}
    head[flag]++;
}

void bibfs(){
    if (queue[0][0] == queue[1][0]) {cout << 0 << endl; return;}
    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
    
    dist[0][0] = dist[1][0] = 0; head[0] = head[1] = 0; tail[0] = tail[1] = 1;
    memset(hash, -1, sizeof(hash)); hash[queue[0][0]] = 0; hash[queue[1][0]] = 1;
    
    while (true){
        
        //if (head[0]> T;
    while (T--){
        init(); bibfs();
    }
}
#include 
#include 
#define REP(I, N) for (int I=0;I x.f;
    }
} u, v;

priority_queue Q;




/*/
inline int h(){
    int s = 0; REP(i, 9) if (a[i] && a[i] != ed[i]) s++;
    return s;
}

/*/
 
inline int h(){
    int s = 0; REP(i, 9) s += w[i][a[i]];
    return s + s / 5; //#
}
//*/



inline int cantor(){
    int x = 0, t, i, j;
    for (i=0;i<9;i++){
        for (j=i+1,t=0;j<9;j++)
            if (a[i]>a[j]) t++;
        x = x * (9-i) + t;
    }
    return x;
}

inline void recover(int x){
    memset(c, false, sizeof(c));
    memset(a, 0, sizeof(a));
    int i;
    for (i=0;i<9;i++){
        while (c[a[i]]) a[i]++;
        while (x >= F[8-i]){
            x -= F[8-i]; a[i]++;
            while (c[a[i]]) a[i]++;
        }
        c[a[i]] = true;
    }
}

inline int stat(){
    int  inversion_pair = 0;
    for (int i=0;i<8;i++){
        if (a[i]==0) continue;
        for (int j=i+1;j<9;j++){
            if (a[j]==0) continue;
            if (a[i]>a[j]) inversion_pair++;
        }
    }
    return inversion_pair;
}




void init(){
    
    REP(i, 9){cin >> st[i]; a[i] = st[i];}
    start = cantor(); b[0] = stat();
    
    REP(i, 9){cin >> ed[i]; a[i] = ed[i];}
    goal = cantor(); b[1] = stat();
    
    REP(i, 9) st[ed[i]] = i; // #
    REP(i, 9) REP_1(j, 8) w[i][j] = abs(i/3 - st[j]/3) + abs(i%3 - st[j]%3);
    _found = false;
}



inline void operate(int x, int y){
    swap(a[x], a[y]), v.s = cantor();
    if (!hash[v.s]){
        v.d = u.d + 1;
        if (v.s==goal){
            cout << v.d << endl;
            _found = true;
        }
        else {
            v.f = v.d + h();
            Q.push(v);
        }
    }
    swap(a[x], a[y]);
}

void Astar(){
    if (start == goal) {cout << 0 << endl; return;}
    if (b[0]%2!=b[1]%2) {cout << -1 << endl; return;}
    
    while (!Q.empty()) Q.pop(); //#
    u.s = start, u.d = 0, Q.push(u);
    memset(hash, false, sizeof(hash));
    
    int p;
    while (true){
        u = Q.top(); Q.pop(); if (hash[u.s]==true) continue;
        hash[u.s] = true; recover(u.s);
        
        for (p=0;a[p]!=0;p++);
        if (p > 2) operate(p, p-3);
        if (p < 6) operate(p, p+3);
        if (p % 3) operate(p, p-1);
        if ((p+1) % 3) operate(p, p+1);
        if (_found) return;
    }
}

int main(){
    int T; cin >> T;
    while (T--){
        init(); Astar();
    }
}


http://acm.hit.edu.cn/judge/show.php?Proid=1868&Contestid=0

1. 状态的存储
状态的存储采用康托展开对排列进行编码起到 hash 的作用,唯一的缺点呢则是在应用操作符的时侯需要解码恢复一次。
(参见代码中的 void cantor() 和 void recover() 过程。。。。。)

2. 判断无解
另一个重要的想法是利用逆序对的奇偶性将状态划分成两个等价类,不同等价类的里状态不能相互达到,这样在宽搜之前就可以排除掉输出-1的情况。

3. 关于 Astar
目前关于 Astar 还存在一些疑问有待解决 …
在这题里而言,首先同普通 BFS 的一个显著不同,虽然边权值都只有+1而已,但是只能保证在取出队列的时侯所得到的值最优,(这点又类似 Dijkstra 了)因此理因,在每次更新状态的时侯先要判断这个状态在优先队列中是否已经存在,如果存在则进行比较并更新。(但是这一份代码并没有这么做,而是让两个状态同时加入到结点中,而在取出队列的时侯对状态进行标记,这样会有一些不好的地方,但是这是在用 STL 写的时侯无法获得 堆中元素的 Pos 数组而采取的一种替代方式。)

另外,关于 八数码问题 的两种启发函数,(每个元素到自己理应所在点的哈密顿距离,以及所有不在自己位置上的数。)(注意不能考虑数字 0 ,具体原因。。。)也有一些值得讨论的地方呢。

状态压缩DP

还有几道题正在整理。。还有几道题不会做。。
这几份题目都是类TSP问题。某一个参数小。可以用状态压缩DP可以解~~~

#include 
#include 
#include 
using namespace std;
const int N = 10, M = 1 << 10;
int w[N][N]; int dp[M][N];
string s[N];
int n, m, ans;


// updata the w[a][b] with the offset o;
int f(int a, int b, int o){
    int res = 0, o1, o2;
    if (o<0) o1 = -o, o2 = 0; else o1 = 0, o2 = o;

    for (int i=o1,j=o2;i> s[i];

    memset(w, 0, sizeof(w));
    for (int i=0;i> n;
    while (n!=0){
        init(); solve();
        cout << ans << endl;
        cin >> n;
    }
}
#include 
using namespace std;
const int N = 15, M = (1 << 15) - 1;
const int INF = 10000000;
int dp[M][N], w[N][N];
int n, m, k;
int ans;

void init(){
    int i, j;
    m = (1 << n); k--;
    int a[N], b[N];

    for (i=0;i> a[i] >> b[i];

    for (i=0;i> w[i][j];
            if (i==j) w[i][j] = -INF;
            else  w[i][j] = b[j] - a[j] - w[i][j];
        }

    for (i=0;i> n >> k){
        init();  solve(); // patch();
        cout << ans << endl;
    }
}

HOJ 2491. Sequences

Brief description :

将数列 {an} 划分成一些长度在 [l, r] 之间的子段,每个子段的得分等于首尾项的和。(注意是完美划分,不要留空隙。~)

Note :

单调队列练习题。。
dp[i] = max{dp[j] + a[j+1]} + a[i] | j 要满足条件
把 dp[i] 和 a[i+1] 存在一起简化维护。。

#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 500002;

int a[N], d[N], q[N], cz, op;
int n, l, r;

void push(int x){
    while (cz <= op && d[x] >= d[q[op]])
        op--;
    q[++op] = x;
}

void init(){
    scanf("%d%d", &l, &r);
    for (int i=1;i<=n;i++) scanf("%d", &a[i]);
    a[n+1] = 0;
}

void solve(){
    d[0] = a[1]; cz = 0, op = -1;

    for (int i=1;i> n){
        init(); solve();
        cout << d[n] << endl;
    }
}

External link :


http://acm.hit.edu.cn/judge/show.php?Proid=2941