BZOJ 1330: Editing a Book – [BFS/双向搜索]

题目传送门(BZOJ)
>原文链接<

题解 :

网上大片大片的 IDA* 然鹅并不需要那个。

手推最坏情况 9 8 7 6 5 4 3 2 1 后你会发现答案不超过5。

所以我们可以折半搜索,从初始状态搜 3 步,再从排好序的状态搜两步。

然后你发现这样做需要20多秒。

所以我尝试着把状态哈希,减少重复状态带来的影响。效果显而易见,我们压到了3秒。

然鹅我们那场考试时限是 1s, 所以我还是只得了部分分。毕竟复杂度还是不对。

但是你发现,如果从左边搜两步,右边搜两步之后,没有交集的话,答案必然是5,

所以我们初始状态只搜两步。

这…. 神仙复杂度。

注意 :初始输入可能是有序的,如果不把这个状态放到map里,可以被卡掉的。

代码 :

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using namespace std::tr1;
unordered_mapf, g;
maphadans;
queue >q;
int n, a[10];
inline int merge(int* tmp) {
    int ret = 0;
    for(int i = n; i >= 1; i -- )ret = (ret<<3)+(ret<<1) + tmp[i];
    return ret;
}
inline void split(int x, int* a) {
    for(int i = 1; i <= n; i ++, x/=10) a[i] = x%10;
}
int ans = 0;
void Get_Front() {
    int x = 0;
    for(int i = n; i >= 1; i -- )x = (x<<3)+(x<<1) + a[i];
    pairpa;
    pa.first = x, pa.second = 0;
    q.push(pa);
    while(!q.empty()) {
        int u = q.front().first, stp = q.front().second;
        q.pop();
        stp++;
        if(stp >= 3) break;
        split(u, a);
        for(int l = 1; l <= n; l ++ ) for(int r = l; r <= n; r ++ ) 
        for(int k = 1; k+r-l <= n; k ++ ) {
            int tmp[10];
            int p1 = k, p2 = l;
            while(p2 <= r) tmp[p1++] = a[p2++];
            p1 = 1, p2 = 1;
            while(p1 <= n) {
                if(p1 == k) p1 = k+r-l+1;
                if(p2 == l) p2 = r+1;
                tmp[p1++] = a[p2++];
            }
            int now = merge(tmp);
            if(!f[now]) {
                f[now] = stp;
                pa.first = now, pa.second = stp;
                q.push(pa);
            }
        }
    }
}
void Find_Ans() {
    while(!q.empty()) q.pop();
    int x = merge(a);
    if(f[x]) ans = min(ans, f[x]);
    q.push(make_pair(x, 0));
    while(!q.empty()) {
        int u = q.front().first, stp = q.front().second;
        q.pop();
        stp++;
        if(stp >= 3) break;
        split(u, a);
        for(int l = 1; l <= n; l ++ ) for(int r = l; r <= n; r ++ )
        for(int k = 1; k+r-l <= n; k ++ ) {
            int tmp[10];
            int p1 = k, p2 = l;
            while(p2 <= r) tmp[p1++] = a[p2++];
            p1 = 1, p2 = 1;
            while(p1 <= n) {
                if(p1 == k) p1 = k+r-l+1;
                if(p2 == l) p2 = r+1;
                tmp[p1++] = a[p2++];
            }
            int now = merge(tmp);
            if(f[now]) ans = min(ans, f[now] + stp);
            if(!g[now]) {
                g[now] = 1;
                q.push(make_pair(now, stp));
            }
        }
    }
}
int main() {
    while(scanf("%d", &n), n != 0) {
        f.clear();
        g.clear();
        ans = 5;
        while(!q.empty()) q.pop();
        for(int i = 1; i <= n; i ++ ) a[i] = i;
        int y = merge(a);
        for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        int x = merge(a);
        if(x==y) {
            puts("0");
            continue;
        }
        if(hadans[x]) {
            printf("%d\n", hadans[x]);
            continue;
        }
        Get_Front();
        for(int i = 1; i <= n; i ++ ) a[i] = i;
        Find_Ans();
        printf("%d\n", hadans[x]=ans);
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注