新年欢乐赛 解题报告

考试链接:[http://180.76.159.115:5283/contest/5] 学长的考试,渣渣的我就做了三道题,那就写个及结题报告吧,毕竟我才是个普及组蒟蒻

1.这是一道大水题

题目链接:[http://180.76.159.115:5283/problem/3]
学长真皮

简单解析


题目第一眼看过去n,m<=100那么很显然这是搜索大法可以做到的,然而dfs有这很大的 TLE 的风险,所以当然是bfs大法好了 对于人而言把他的范围都设为不可走就可以了

代码


#include <cstdio>
using namespace std;
struct node{
    int x,y,deep;
}st,dl[110000];
int n,m;
char te[110];//读入
int a[110][110];// 存图
int dx[4]={0,0,-1,+1};//dx[] dy[] 增量
int dy[4]={+1,-1,0,0};
bool x[110][110];// x[ ][ ]记录走过的路
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",te);// 字符串总是稳定的,毕竟总比字符读入个'\n'好qwq
        for(int j=0;j<m;j++){// 所以要对读入的字符串
            if(te[j]=='S') {// 是出口就放入s
                st.x=i;
                st.y=j;
            }
            if(te[j]=='#') a[i][j]=-1;// 桌子是不能过的
            if(te[j]=='!'){//愤怒的oier
                a[i][j]=-1;
                a[i-1][j]=-1;
                a[i+1][j]=-1;
                a[i][j-1]=-1;
                a[i][j+1]=-1;
            }
            if(te[j]=='D') a[i][j]=1;
        }
    }
    a[st.x][st.y]=0;// 开头可以走
// 加入队列
    int h,l;
    h=l=1;
    dl[1]=st;
    while(h<=l){//日常bfs
        node now;
        now=dl[h];
        for(int i=0;i<4;i++){// 模拟上下左右
            node temp=dl[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            if(temp.x>=0&&temp.x<n&&temp.y>=0&&temp.y<m){// 判断越界
                if(a[temp.x][temp.y]==0&&(!x[temp.x][temp.y])){// 可以走
                    temp.deep++;
                    x[temp.x][temp.y]=true;
                    dl[++l]=temp;
                }
                else if(a[temp.x][temp.y]==1){// 到了大门
                    printf("%d",temp.deep+1);
                    return 0;
                }
            }
        }
        h++;
    }
    printf("Ahhhhhhh!!!");// 搜完了都没做到,那么就死吧、
}

2.缘生意转

题目链接:[http://180.76.159.115:5283/contest/5/problem/2]
这种题目看过去第一眼就是打表啊,把该存1到100存到一个二维数组,然后挨个儿比对

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n,len[110],ans;
char dic[120][22]={"one","two","three","four","five","six","seven","eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty","twenty-one","twenty-two","twenty-three","twenty-four","twenty-five","twenty-six","twenty-seven","twenty-eight","twenty-nine","thirty","thirty-one","thirty-two","thirty-three","thirty-four","thirty-five","thirty-six","thirty-seven","thirty-eight","thirty-nine","forty","forty-one","forty-two","forty-three","forty-four","forty-five","forty-six","forty-seven","forty-eight","forty-nine","fifty","fifty-one","fifty-two","fifty-three","fifty-four","fifty-five","fifty-six","fifty-seven","fifty-eight","fifty-nine","sixty","sixty-one","sixty-two","sixty-three","sixty-four","sixty-five","sixty-six","sixty-seven","sixty-eight","sixty-nine","seventy","seventy-one","seventy-two","seventy-three","seventy-four","seventy-five","seventy-six","seventy-seven","seventy-eight","seventy-nine","eighty","eighty-one","eighty-two","eighty-three","eighty-four","eighty-five","eighty-six","eighty-seven","eighty-eight","eighty-nine","ninety","ninety-one","ninety-two","ninety-three","ninety-four","ninety-five","ninety-six","ninety-seven","ninety-eight","ninety-nine"};
char a[22];
int main(){
    for(int i=0;i<99;i++){// 存入长度
        len[i]=strlen(dic[i]);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a);// 读入
        int alen=strlen(a);
        for(int j=0;j<99;j++){// 比对
            if(len[j]!=alen) continue;// 字符串长度不同直接gg
            if(strcmp(a,dic[j])==0) {
                ans+=j+1;
                break;
            }
        }
    }
    printf("%d",ans);
}

3.绿豆沙冰

题目链接: [http://180.76.159.115:5283/problem/7]

简单分析


博主一上来就是floyd,然后被多组数据坑的…… 所以这次我们就要一换方法——spfa 先来介绍一下吧
inline void spfa(){
    int h,l;
    h=l=1;
    d[1]=0;
    x[1]=true;// 避免自己走到自己
    dl[1]=1;// 加入队列头
    while(h<=l){
        int temp=dl[h];
        for(int i=1;i<=n;i++){//尝试每一个点
            if(d[temp]+a[temp][i]<d[i]){// 优于就放入队列
                d[i]=a[temp][i]+d[temp];
                if(!x[i]){
                    x[i]=true;
                    dl[++l]=i;
                }
            }
        }
        x[temp]=false;
        h++;
    }
}
可以很明显的发现,这是个基于bfs并有贪心思路的算法; 首先是bfs模拟,其次是如果优于前者才放近队列; 虽然不是多源最短路,但是其速度是相当快的qwq

代码


#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int T,n,m,k;
int a[1100][1100];
int d[1100],dl[110000];
bool x[1100];
inline void init();
inline int read(){// 读入优化不解释
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void floyd(){// floyd,会超时的qwq
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            if(a[i][k]>k) continue;
            for(int j=1;j<i;j++){
                if(a[i][k]+a[k][j]<a[i][j]){
                    a[i][j]=a[i][k]+a[k][j];
                    a[j][i]=a[i][j];
                }
            }
        }
    }
}
inline void spfa(){// 不用解释了吧
    int h,l;
    h=l=1;
    d[1]=0;
    x[1]=true;
    dl[1]=1;
    while(h<=l){
        int temp=dl[h];
        for(int i=1;i<=n;i++){
            if(d[temp]+a[temp][i]<d[i]){
                d[i]=a[temp][i]+d[temp];
                if(!x[i]){
                    x[i]=true;
                    dl[++l]=i;
                }
            }
        }
        x[temp]=false;
        h++;
    }
}
inline void readin(){// 读入并加边
    n=read();m=read();k=read();
    init();
    for(int i=1;i<=m;i++){
        int u,v,t;
        u=read();v=read();t=read();
        a[u][v]=t;
        a[v][u]=t;
    }
}
inline void init(){ // 清空/初始化
    memset(dl,0,sizeof(0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=0x3fffffff;
        }
        d[i]=0x3fffffff;
        x[i]=false;
    }
}
int main(){
    scanf("%d",&T);
    for(int i=1;i<=T;i++){//多次数据
        readin();
//        floyd();
        spfa();
        if(/*a[1][n]*/d[n]*2<=k) printf("Yes \n");
        else printf("No\n");
    }
}

End

]]>

论 dfs 与 bfs 的优化:NOIP 2017 普及组 第三题 – 棋盘

题目

参考题目:[https://www.luogu.org/problemnew/show/P3956]
相信大家都做过这道题吧,毕竟真的是到很明显的搜索/dp dp就不说了,有兴趣可以去题解去瞅瞅,不过因为有可能往回走,dp写起来会很麻烦让你怀疑你写的不是dp 但是同样是因为有可能回走,dfs与bfs无法进行像 bool x[][] 这样的剪枝办法(已经走过的路不走的办法) 所以就需要优化

骗分

既然是考试题目,那么我就就可以骗分

5 分


输出特殊状况—’-1′

10 分


在5分的情况下考虑输出0的情况

15-65 分


dfs大法,不加任何优化版 但是分数可能会有一定波动,需要注意下面几点
  • 尽可能递归 RE
  • 做一点微小的剪枝
  • 平时代码习惯不好可能会比较容易得低
  • 小心魔法
注意完以上几点,你就是一等大佬了

65 分


在15-65分做法中去除向上和向左,防止打转

100 分做法

博主在这里说两种搜索法-bfs/dfs 最短路以及dp大家有心情可以试试 这题用最短路这是杀鸡用牛刀 使用这两种方法都要建一个best[][]数组表当前最优花费,这样就可以避免一些不必要的地方,达成剪枝的目的。 先单独拿出来一行代码讲一下
col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col
可以转化为这个
int wh(){
    if(col[now.x][now.y]!=0) return col[now.x][now.y];
    else return temp.tu.col;
}
wh();
这个符号我们叫三目运算符/问号表达式

bfs


#include <cstdio>
#include <cstring>
using namespace std;
struct que{
    int tu_col,money,x,y;
// tu_col 目前变化的颜色
// money 目前所花钱数
// x y 目前走到(x,y)上
}q[110000];// q[] 队列
int n,m,x,y,c;
// dx[] dy[] 增量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
// best[i][j] 目前位于(i,j)的已知最优解
// col[i][j] (i,j)格子上的颜色
int main(){
    memset(best,0x3f,sizeof(best));// 初始化
// 读入
   scanf("%d%d",&m,&n);
   for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
// 加入队列首
    q[1].x=q[1].y=1;
    q[1].money=q[1].tu_col=0;
    int h,t;
    h=t=1;
    best[1][1]=0;// 第一个格子设为0
    while(h<=t){// 开始bfs
        que now;
        now=q[h];
// now 仅仅为了方便写,在下面的循环中可替换为q[h],也就是用于储存队列首
        for(int i=0;i<4;i++){// 模拟上下左右
            que temp=q[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            // temp 用于临时修改
            if(temp.x<=0||temp.y<=0||temp.x>m||temp.y>m) continue;// 判断越界
            if(col[temp.x][temp.y]==0/*如果当前格子上没有颜色*/&&temp.tu_col==0/*并且上一个格子没有用魔法*/){
                if(temp.money+2<best[temp.x][temp.y]){// 如果当前解优于已知最优解,才能放入队列
                    temp.money+=2;
                    temp.tu_col=col[now.x][now.y];// 存入临时颜色
                    q[++t]=temp;// 加入队列
                    best[temp.x][temp.y]=temp.money;// 更新 best 数组
                }
            }
            else if(col[temp.x][temp.y]!=0&&col[temp.x][temp.y]!=(col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col)){// 颜色不相等
                 if(temp.money+1<best[temp.x][temp.y]){// 不解释
                    temp.money+=1;
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
            else if(col[temp.x][temp.y]!=0){// 接下来只有可能颜色相等
                if(temp.money<best[temp.x][temp.y]){
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
        }
        h++;// 踢出对首
    }
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);// 不是预设值就输出
    else printf("-1");// 是预设值说明没有路通向那,输出-1
}

dfs


请参照 bfs 方法的注释来理解这个,所有变量含义一样
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,c;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
void dfs(int x,int y,int tu_col,int money){
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>m) continue;
        if(col[tx][ty]==0&&tu_col==0){
            if(money+2<best[tx][ty]){
                best[tx][ty]=money+2;
                dfs(tx,ty,col[x][y],money+2);
            }
        }
        else if(col[tx][ty]!=0&&col[tx][ty]!=(col[x][y]!=0?col[x][y]:tu_col)){
            if(money+1<best[tx][ty]){
                best[tx][ty]=money+1;
                dfs(tx,ty,0,money+1);
            }
        }
        else if(col[tx][ty]!=0){
            if(money<best[tx][ty]){
                best[tx][ty]=money;
                dfs(tx,ty,0,money);
            }
        }
    }
}
int main(){
    memset(best,0x3f,sizeof(best));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
    best[1][1]=0;
    dfs(1,1,0,0);
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);
    else printf("-1");
}

END

要是考场上没有删掉自己的dp就好了qwq ]]>

Caioj 1047: 魔板

二维魔方,全是套路

题目


题目链接: [http://caioj.cn/problem.php?id=1047]
二维的魔方貌似并没有比三维的魔方简单到哪里 我们可以看出,这道题是一个搜索,并且求的是最优解,也就是宽搜的事了 然后再让我们想想哈希表的问题,首先我们知道只有八个数,并且还都是 1-8 ,显然就应该用康托展开了

部分代码 & 想法


我们要对这一串数字进行处理,显然是应当以数组方式存的(当然你也可以存成整数操作,如果你不觉得累的话),我们要输出操作,这是这道题中的一个大坑=.=,显然我们将操作以字符串的形式存起来内存会非常大,所以我们应当换一种方法. 我们知道,每中搜索都会有一颗对应的搜索树,以这个为基础,我们就可以想到,将他的父节点存下来,只在当前的结构体中存我们从父节点过来的操作,然后在输出时一路递归回到根节点,再逆序输出即可。 结构体:
struct node{
    int deep,a[3][5],k,last;
    char d;
}b[400000],ed;
deep – 当前深度(步数) a[][] – 当前魔板的状况 k – 康托展开 last – 父亲节点 d – 从父节点过来的操作 输出操作:
void sc2(int k){
    if(b[k].last!=-1) sc2(b[k].last);
    if(b[k].last!=-1) printf("%c",b[k].d);
    return ;
}
然后就是广搜的基本套路=.=,大家都会写的说

部分小坑


  1. 这个魔板是在第二列是从右往左读入的
  2. 别忘记输出 no !
  3. 处理时谨慎点
]]>

Caioj 1046: 8数码问题

广搜入门题,经典八数码 题库中已经说的很清楚了,这题是用广搜(又称宽搜),那么,何为宽搜,它与深搜区别何在?

1.深搜与广搜


这两种搜索的全名分别是: 深搜——深度优先搜索 广搜——广度优先搜索 其英文缩写分别是 dfs 与 bfs ,虽然只差一个字母,不过却有所不同 深搜的特点是短而难想 广搜的特点是长且难写 我们就根据八数码这道题,说一下深搜与广搜的区别,先看看下面这张图:
                  0
           /   |    |   \
        上 下 左  右(最优解)
    /  |    |    \
上 下 左 右(次右解)
如果你是用深搜他会这么寻找: 0->上->上->返回上一层->下->返回上一层->左->返回上一层->右(次优解)->返回上一层->下-》……最优解 然而广搜是这个样子的 0->上->下->左->右(最优解)->进入下一层-》上-》下-》左-》右-》次优解 以上应该就可以很明白的看出,深搜是将一步搜索到底再回头,广搜是在每一层搜索,所以广搜第一个搜到的一定是最优解。 不过为什么会右这样的差距,这就要看广搜的原理了

2.何为广搜


广度优先搜索
这不就是没解释 也就是说我们先把同一个步数的所有情况扩展完,然后进行判断,这也就是为什么第一个答案就是最优解 我们说这种情况,每一种情况搜完就不在需要了,而最近被搜到的应该放入最后,也就是说,先进先出——队列 那也就是说,这个东西需要我们开队列=.=,并且这种状况下,重复的可能性很高,关于如何这道题的剪枝方法,你可以看看这个 Caioj 1220:康托展开和康托展开的逆运算

3.题目&思路&部分代码


题目链接: http://caioj.cn/problem.php?id=1046
首先我们知道,这个题我们就是要模拟上下左右,也就是说我们读入初始与截止情况,将初始情况放入队列首,先来看看队列怎么写吧
struct FUCK{
    int a[4][4],x,y,deep;
}dl[400000],ed;
请忽略结构体名 dl[] 也就是队列
  • int a[][] 临时储存数码图
  • x,y 0 的坐标
  • deep 深度,也就是步数
ed 结尾情况 嗯对就是这样 然后就是判断重复,也就是上文所说的康托展开,我们吧每一中情况打成哈希表(坑爹玩意),然后就可以判断重复了,接下来就可以进行搜索
    while(l<=r){
        for(int i=0;i<4;i++){
            FUCK fir=dl[l];
            fir.x=dl[l].x+dx[i];
            fir.y=dl[l].y+dy[i];
            if(fir.x>=1&&fir.x<=3&&fir.y>=1&&fir.y<=3){
                int temp=fir.a[fir.x][fir.y];
                fir.a[fir.x][fir.y]=fir.a[dl[l].x][dl[l].y];
                fir.a[dl[l].x][dl[l].y]=temp;
                int temp_kt=zys(fir);
                fir.deep=dl[l].deep+1;
                if(!xd[temp_kt]){
                    xd[temp_kt]=true;
                    r++;
                    dl[r]=fir;
                    if(temp_kt==z){
                        printf("%d\n",fir.deep);
                        return 0;
                    }
                }
            }
        }
        l++;
    }
其中 l 是队列首指针, r 是队列尾指针, for 循环对应的就是 dx[] , dy[] 这两个增量然后我们就交换变量, 随意说这道题并不是特别的难 当然如果你不加判断重复就会 RE 了2333 ]]>