新年欢乐赛 解题报告

考试链接:[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

]]>

加入对话

5条评论

留下评论

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