解题报告 P2901 [USACO08MAR]Cow Jogging G

题目内容

P2901

给定一有向带权图,求从 n 到 1 的前 k 短路的长度

解题思路

求 k 短路的一个常用的方法是使用 A*,怎么求呢?

首先,预处理出所有点到 1 的最短距离(使用反向图跑最短路),然后从 n 开始进行广搜,只不过队列改为优先队列,估价方式为 f+dis[now] 小的先出队,其中 f 为已经走过的路,dis[now]now 到 1 的最短距离,这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展,最先进入到 1 号的就是最短路,随后次短路,第三短路。。。会依次进入到 1 号点,每次输出走过路径长即可。

#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>

typedef long long ll;
using namespace std;

const int maxn=1e3+5;

struct node
{
    ll pos,f;
    node(){}
    node(int _p,int _f)
    {
        pos=_p;
        f=_f;
    }
};

struct edge
{
    ll from,to,dist;
    edge(){}
    edge(ll u,ll v,ll w)
    {
        from=u;
        to=v;
        dist=w;
    }
};

//快读省略

vector<edge> g1[maxn],g2[maxn];//g1存正向图,g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];

bool operator<(const node &_a,const node &_b)
{
    return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}

void dijsktra()//反向跑dij获取每个点的距离
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    memset(dis,0x3f,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g2[now])
            {
                if(dis[e.to]>dis[now]+e.dist)
                {
                    dis[e.to]=dis[now]+e.dist;
                    q.push(make_pair(dis[e.to],e.to));
                }
            }
        }
    }
    return;
}

void astar()//开始A*
{
    priority_queue<node> q;
    q.push(node(n,0));
    while(!q.empty())
    {
        ll now=q.top().pos,f=q.top().f;
        q.pop();
        if(now==1)//如果到终点了
        {
            printf("%lld\n",f);//直接输出
            if(!(--k))//如果已经求完前k短路,结束
                return;
        }
        else
            for(auto i:g1[now])//然后就是扩展
                q.push(node(i.to,i.dist+f));
    }
    while(k--)//如果还有没搞完的
        printf("-1\n");
    return;
}

inline void ins(ll u,ll v,ll w)
{
    g1[u].push_back(edge(u,v,w));
    g2[v].push_back(edge(v,u,w));
    return;
}

int main()
{
    n=read(),m=read(),k=read();
    ll u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ins(u,v,w);
    }
    dijsktra();
    astar();
    return 0;
}

解题报告 P1019 单词接龙【NOIP2000TGT3】

题目内容

P1019

大意:给出 n 个单词,每个单词最多出现两遍,求最长的龙的长度,前单词和后单词之间不能包含。

解题思路

这题一看就很难调细节,直到我看了题解才发现了新世界。

大体的思路非常好想,就是无脑 dfs 下去,但是整道题的难点就在于字符串的拼接处理。

每次 dfs 的时候函数长这样:dfs(string now,int l),其中 now 是上一个单词,l 是龙的长度,所以根本没必要存龙(我是sb),直接存上一个单词,然后接着拼接就可以了。

然后拼接有一个原则(贪心):为了保证最后接出来的龙最长,相交的字符串部分需要尽可能的短,所以定义了一个 link() 函数返回的是两个单词之间最小重叠部分的长度。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string word[22];
int vis[21];
int ans=0;

int link(string a,string b)//返回两个字符串的最小重叠部分的长度
{
    for(int i=1;i<min(a.size(),b.size());i++)//枚举重叠部分的长度
    {
        bool flag=1;
        for(int j=0;j<i;j++)
            if(a[a.size() - i + j] != b[j])//每一位来判
                flag = 0;
        if(flag)
            return i;
    }
    return 0;
}

void dfs(string now,int l)//now为上一个单词,l为龙的长度
{
    ans=max(ans,l);//每次更新一下答案
    for(int i=0;i<n;i++)//枚举下一个单词
    {
        if(vis[i]>=2)//如果已经用过两次了
            continue;
        int c=link(now,word[i]);//获取两个单词间的重叠长度
        if(c)
        {
            vis[i]++;
            dfs(word[i],l+word[i].size()-c);//继续搜
            vis[i]--;
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<=n;i++)
        cin>>word[i];
    dfs(" "+word[n],1);//这里的空格防link函数错误返回
    cout<<ans<<endl;
    return 0;
}

解题报告 P1126 机器人搬重物

题目内容

P1126

题面很长,大意就是控制一个机器人,但是这题最恶心的地方就是机器人的位置是点的坐标,但障碍物是格子

解题思路

这题调了我真的好久,是我见过最难调的搜索题之一,考验代码能力。从去年的 9 月份调了几个小时放弃之后直到今天再拿起此题,然后调半个小时过去了,其中两次 WA 一次是因为没判 -1,一次是因为判断边界的函数把 m 写成 n。

具体的思路就是,进行 bfs,每次转移的时候存储机器人左上角的坐标,判断障碍和越界的时候只需要判断他四个格子有没有障碍就可以了。然后就是一些 trick,比如采用 kln 和 kcol 数组来进行方便的向前移动的坐标转移,然后就是 vis 数组记得多开一维存储方向,再就是记得 x 和 y 分别代表的是行还是列,搞明白之后还是比较好写的。

查错真的是花了我不少时间,输出中间变量太香了,可以很方便的快速定位到错误的发生位置

然后这个狗东西其实也可以用双向搜索,但是我懒得用了,单向也可以过的

#include <cstdio>
#include <queue>
using namespace std;

int n,m;
//n is line, m is col
int sx,sy,fx,fy;//存起终点
int maze[52][52];//存迷宫
int kln[4][4],kcol[4][4];//第一维是朝向,第二维是要移动的步数
bool vis[52][52][4];//存储每个点的方向是否访问过

struct node
{
    int x,y;//机器人左上角坐标
    int face;//目前的朝向
    int step;//目前已经走的时间
    node(){}
    node(int _x,int _y,int _face,int _step)
    {
        x=_x;
        y=_y;
        face=_face;
        step=_step;
    }
};

queue<node> q;

void updk()//kln和kcol数组的初始化函数
{
    kln[1][1]=1,kln[1][2]=2,kln[1][3]=3;
    kln[3][1]=-1,kln[3][2]=-2,kln[3][3]=-3;
    kln[0][1]=kln[0][2]=kln[0][3]=0;
    kln[2][1]=kln[2][2]=kln[2][3]=0;
    kcol[1][1]=kcol[1][2]=kcol[1][3]=0;
    kcol[3][1]=kcol[3][2]=kcol[3][3]=0;
    kcol[0][1]=1,kcol[0][2]=2,kcol[0][3]=3;
    kcol[2][1]=-1,kcol[2][2]=-2,kcol[2][3]=-3;
    return;
}

inline bool isvalid(int x,int y)//判断一个机器人的位置是否合法
{
    if(x<1||x>n-1||y<1||y>m-1)//判边界,当时就是因为m写成n了WA第3个点
        return false;
    if(maze[x][y]||maze[x+1][y]||maze[x+1][y+1]||maze[x][y+1])//判障碍物
        return false;
    return true;
}

int bfs()
{
    int ans=0x3f3f3f3f;
    bool flag=0;
    while(!q.empty())
    {
        int nowx=q.front().x,nowy=q.front().y,nowdir=q.front().face,nowstep=q.front().step;
        q.pop();
        if(!isvalid(nowx,nowy))
            continue;
        if(nowx==fx && nowy==fy)
        {
            ans=nowstep<ans?nowstep:ans;
            flag=1;
        }
        if(!vis[nowx][nowy][(nowdir+1)%4])//这里是方向的处理,适当运用模运算可以简化思维
        {
            vis[nowx][nowy][(nowdir+1)%4]=1;//记得vis数组更新
            q.push(node(nowx,nowy,(nowdir+1)%4,nowstep+1));
        }
        if(!vis[nowx][nowy][(nowdir+3)%4])//一样的道理,换一个方向而已
        {
            vis[nowx][nowy][(nowdir+3)%4]=1;
            q.push(node(nowx,nowy,(nowdir+3)%4,nowstep+1));
        }
        for(int s=1;s<=3;s++)//枚举向前走的步数
        {
            int xx=nowx+kln[nowdir][s],yy=nowy+kcol[nowdir][s];
            if(!isvalid(xx,yy))//如果发现走1步不行就要及时break,否则WA
                break;
            if(!vis[xx][yy][nowdir])//如果没有重就加入队列
            {
                vis[xx][yy][nowdir]=1;
                q.push(node(xx,yy,nowdir,nowstep+1));
            }
        }
    }
    return flag?ans:-1;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&maze[i][j]);
    updk();
    char dir;
    scanf("%d %d %d %d %c",&sx,&sy,&fx,&fy,&dir);
    if(dir=='E') dir=0;
    if(dir=='S') dir=1;
    if(dir=='W') dir=2;
    if(dir=='N') dir=3;
    vis[sx][sy][dir]=1;
    q.push(node(sx,sy,dir,0));
    printf("%d\n",bfs());
    return 0;
}

这题细节还是很多的,可以锻炼代码能力和调试能力。

解题报告 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;
}