解题报告 P2534 [AHOI2012]铁盘整理

题目内容

P2534

若干个铁盘,乱摆的,每次操作可以反转最上面的若干铁盘,求最少操作次数使得从上往下铁盘半径依次递增

解题思路

纪念人生中第一道紫题虽然这道题我不觉得他配紫

这种题可以使用IDA*进行玄学的搜索,好的进入正题。

众所周知,IDA*是需要一个估价函数的,而这道题的关键就在于估价函数如何来设计。一开始想过不在预定位置上的铁盘个数作为估价函数,发现不行,因为有可能你4个铁盘都不在指定位置上,但是反转一下就得到结果了,这样的估价函数显然是不行的。

所以这里的估价函数只好使用不应该相邻的铁盘的个数,因为只有这样才能得到最接近的结果。至于如何判断不应该相邻的铁盘,我使用了 map 因为疯狂使用 stl 导致我跑的龟慢,然后就是常规的 IDA*,每次枚举一个深度 idt,然后让 dfs 在这个限定的深度里面跑,如果跑得出结果那就输出,跑不出那就加大 idt 继续跑。

细节上使用的是用 vector 模拟状态,(虽然好用但是跑的龟慢),每次操作使用 reverse 函数模拟,然后进行操作模拟的时候就不要只翻转第一层了,翻了等于没翻。

注意 stl 函数的尿性都是左闭右开区间,差点被坑了

代码:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n;
vector<int> r0,r1;//r0是从上到下的初始顺序,r1是整理过的从上到下递增的顺序
map<int,int> m1,m2;//m1存储他上面应该是什么,m2存储他下面应该是什么

int h(vector<int> rcur)//估价函数
{
    int cnt=0;
    for(int i=0;i<r1.size()-1;i++)
    {
        if(m1[rcur[i]]!=rcur[i+1]&&m2[rcur[i]]!=rcur[i+1])
            cnt++;
    }
    return cnt;
}

bool iddfs(vector<int> rcur,int d,int idt)//迭代加深搜索
{
    if(d+h(rcur)>idt)//如果估价函数显示直接挂就返回
        return 0;
    if(d>idt)//如果深度挂了,返回
        return 0;
    if(rcur==r1)//如果到达目标了,返回
        return 1;
    for(int i=2;i<=rcur.size();i++)//开始枚举翻的盘片
    {
        vector<int> tmp=rcur;
        reverse(tmp.begin(),tmp.begin()+i);//注意左闭右开
        if(iddfs(tmp,d+1,idt))//继续下一层搜索
            return 1;
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        r0.push_back(x);
    }
    r1=r0;
    sort(r1.begin(),r1.end());//将排好序的铁盘做预处理
    for(int i=0;i<r1.size();i++)//对m1,m2进行预处理
    {
        if(i!=0)
            m1[r1[i]]=r1[i-1];
        if(i!=r1.size()-1)
            m2[r1[i]]=r1[i+1];
    }
    for(int idt=1;idt<=2<<n;idt++)//idt 的上限随便搞一个很大的数就行了
    {
        if(iddfs(r0,0,idt))
        {
            printf("%d\n",idt);
            return 0;
        }
    }
    return 0;
}

解题报告 P2324/LOJ2151 [SCOI2005]骑士精神

题目内容

洛谷2324

LOJ2151

大意:在一个 5\times5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士,且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为 1,纵坐标相差为 2 或者横坐标相差为 2,纵坐标相差为 1 的格子)移动到空位上。

给定一个初始的棋盘,怎样才能经过移动变成给定目标棋盘:

解题思路

该题明显是一个裸的搜索,但是暴搜铁定超时,再看到限制15步以内,于是想到打随机化使用来迭代加深。

同时这里还可以使用启发式搜索来进行剪枝,这里的估价函数可设为不在应有位置的骑士个数,然后每次枚举移动步数进行迭代加深即可。

像这种移动棋子的题选择移动空位会更好想一点,然后记得处理读入

代码(这个代码不知道为什么洛谷上没输出 LOJ 就 AC 了:

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int tar[5][5]={//目标状态,1表示黑子,0表示白子,2表示空位
    {1,1,1,1,1},
    {0,1,1,1,1},
    {0,0,2,1,1},
    {0,0,0,0,1},
    {0,0,0,0,0}
};
int board[5][5],idt;
const int fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1};//移动的数组

int h()//估价函数
{
    int res=0;//统计多少枚棋子不在目标位置上
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            if(board[i][j]!=tar[i][j]) res++;
    return res;
}

bool dfs(int x,int y,int d)//x,y为空位坐标,d为当前枚举的深度
{
    if(d+h()>idt+1) return false;//如果估价函数显示这个限制深度铁定过不了就剪枝
    if(!h()) return true;//如果已经到达目标状态,直接返回true
    for(int k=0;k<8;k++)//枚举各个方向
    {
        int x1=x+fx[k],y1=y+fy[k];
        if(x1>4||x1<0||y1>4||y1<0) continue;//判定越界
        swap(board[x][y],board[x1][y1]);//否则交换棋子和空位的位置
        if(dfs(x1,y1,d+1)) return true;//继续dfs,如果搜到了目标状态,返回
        swap(board[x][y],board[x1][y1]);//回溯
    }
    return false;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)//毒瘤题目有很多组数据
    {
        int x0,y0;
        for(int i=0;i<5;i++)
        {
            char s[5];
            scanf("%s",s);
            for(int j=0;j<5;j++)
            {
                if(isdigit(s[j])) board[i][j]=s[j]-'0';
                if(s[j]=='*')
                {
                    board[i][j]=2;
                    x0=i;
                    y0=j;
                }
            }
        }
        bool flag=0;
        for(idt=1;idt<=15;idt++)//枚举深度
        {
            if(dfs(x0,y0,0)){flag=1;break;}//如果当前限制搜到了,那么停止
        }
        printf("%d\n",flag?idt:-1);
    }
    return 0;
}