2019.10.9自主训练小结

一时失言乱红尘 2023-06-06 08:25 3阅读 0赞

# 2019.10.9自主训练小结 #

其实是昨天写的题，但是昨天晚上太累了就没写总结了，再加上昨天有两道题没有A出来心态有点小崩。。。。。。

感觉晚上还是不能刷题，熬夜暂且不说，反正不做题也熬了…，关键是基本上都会自闭，然后睡又睡不着，要等好久才能睡着，第二天早上的课太累了

昨天晚上到VJ上面找到了一套比较基础，但是我觉得还比较好的题，于是就做了做

[A：棋盘问题（DFS）][A_DFS]

做了A、B后深深发现自己深搜和广搜还是不太熟练，尤其是深搜，太不会变通了，这道题和八皇后问题就很相似啊，昨晚居然还卡着了，今天看了别人题解才A。。。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[110][110];    //判断能不能放棋子
    char mp[110][110];   //棋盘
    int col[110];        //表示每列是否有放棋子
    int n,k;     //题目给出：n表示棋盘大小，k表示要放多少个棋子
    int ans;       //最终结果
    
    void dfs(int row,int num)      //row表示当前扫描所在行、num表示放的棋子个数
    {
        
        if(num==k){
                  //以符合要求，答案加一
            ans++;
            return ;
        }
        if(row>=n)        //防止越界
            return ;
        for(int i=0;i<n;i++){
        
            if(a[row][i]==1&&col[i]==0){
        
                col[i]=1;
                dfs(row+1,num+1);
                col[i]=0;
            }
        }
        dfs(row+1,num);        //该行没有满足的情况，直接跳到下一行
        return ;
    }
    int main(){
        
        while(~scanf("%d%d",&n,&k)){
        
            if(n==-1&&k==-1)
                break;
            ans=0;
            memset(a,0,sizeof(a));
            memset(mp,0,sizeof(mp));
            memset(col,0,sizeof(col));
            for(int i=0;i<n;i++){
        
                scanf("%s",mp[i]);
            }
            for(int i=0;i<n;i++){
        
                for(int j=0;j<n;j++){
        
                    if(mp[i][j]=='#')
                        a[i][j]=1;     //表示能放
                }
            }
            dfs(0,0);
            printf("%d\n",ans);
        }
        return 0;
    }

[B:迷宫问题（BFS）][B_BFS]

一道BFS的模板题，很好的复习了一下BFS，这里可能稍微高级点的就是打印路径，直接手写队列，每次记录前缀即可

但是这题有个比较坑的地方就是：空格！空格！空格！

打印路径时：x和y之间除了要有逗号外还要有空格

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int mp[5][5];        //迷宫
    int vis[5][5];         //标记数组
    int dir[4][2]={
        -1,0,0,1,1,0,0,-1};       //方向数组
    struct node{
        
        int x;
        int y;
        int s;
        int pre;
    };
    node que[1100];     //手写队列，方便打印路径
    
    void print_path(int i){
                //运用递归，加上pre打印路径
        if(que[i].pre!=-1)
            print_path(que[i].pre);
        printf("(%d, %d)\n",que[i].x,que[i].y);
    }
    void bfs(int sx,int sy){
        
        int front=0;
        int rear=1;
        vis[sx][sy]=1;
        que[front].x=sx;
        que[front].x=sy;
        que[front].s=0;
        que[front].pre=-1;
        int flag=0;
        while(front<rear){
        
            int fx,fy;
            for(int k=0;k<4;k++){
        
                fx=que[front].x+dir[k][0];
                fy=que[front].y+dir[k][1];
                if(fx<0||fy<0||fx>=5||fy>=5){
        
                    continue;
                }
                if(mp[fx][fy]==0&&vis[fx][fy]==0){
        
                    vis[fx][fy]=1;
                    que[rear].x=fx;
                    que[rear].y=fy;
                    que[rear].s=que[front].s+1;
                    que[rear].pre=front;
                    rear++;
                }
                if(fx==4&&fy==4)
                {
        
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
            front++;
        }
        if(flag==1){
        
            print_path(front);
            printf("(4, 4)\n");
        }
    }
    int main(){
        
        for(int i=0;i<5;i++){
        
            for(int j=0;j<5;j++){
        
                scanf("%d",&mp[i][j]);
            }
        }
        bfs(0,0);
        return 0;
    }

[C：Allowance（贪心）][C_Allowance]

开始看题目就觉得是贪心，但是一直没找贪心策略，导致昨天没A出来，今天看了下面这篇博客才 有了些许思路，还是一道很好的贪心题  
[https://blog.csdn.net/zwj1452267376/article/details/50429521][https_blog.csdn.net_zwj1452267376_article_details_50429521]

**1. 按照面值从大到小取，面值大于等于C的，直接取光。  
2. 再按面值从大到小取，凑近C，可以小于等于C，但不能大于C。  
3.最后从小到大取，凑满C，这里的凑满可以等于大于C。然后将上述2,3步取到的面值全部取走，再转入步骤2，这样每次找到的取法就是当前最优取法，直到所剩下的金币总价值不够C结束。**

很好的题目，很能表现贪心思想：从局部的最优解找出总体最优解。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    int use[30];         //记录当前取法的第i种面值取的个数
    struct node{
        
        int v,b;
    };
    node a[30];
    bool cmp(node x,node y){
        
        return x.v<y.v;
    }
    int main(){
        
        int n,c;
        int cnt,ans,k,m;        //ans即表示最终答案（最多能有多少天）
        scanf("%d%d",&n,&c);
        for(int i=0;i<n;i++){
        
            scanf("%d%d",&a[i].v,&a[i].b);
        }
        sort(a,a+n,cmp);
        ans=0;
        for(int i=n-1;i>=0;i--){
        
            if(a[i].v>=c){
        
                ans+=a[i].b;
                a[i].b=0;
            }
        }
        while(1){
                 //找出当前最优取法
            int flag=0;
            cnt=c;
            memset(use,0,sizeof(use));
            for(int i=n-1;i>=0;i--){
        
                if(a[i].b){
        
                    k=cnt/a[i].v;
                    m=min(k,a[i].b);
                    cnt-=m*a[i].v;
                    use[i]=m;
                    if(cnt==0){
        
                        flag=1;
                        break;
                    }
                }
            }
            if(cnt>0){
        
                for(int i=0;i<n;i++){
        
                    if(a[i].b>use[i]){
        
                        while(use[i]<a[i].b){
        
                            cnt-=a[i].v;
                            use[i]++;
                            if(cnt<=0){
        
                                flag=1;
                                break;
                            }
                        }
                    }
                    if(flag)
                        break;
                }
            }
            if(!flag)
                break;
            m=INF;
            for(int i=0;i<n;i++){
        
                if(use[i])
                    m=min(m,a[i].b/use[i]);
            }
            ans+=m;
            for(int i=0;i<n;i++){
        
                if(use[i])
                    a[i].b-=m*use[i];
            }
        }
        printf("%d\n",ans);
        return 0;
    }

[D：数塔（DP）][D_DP]

一道DP的模板题，也是很经典的dp题，就不啰嗦了

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int dp[110][110];
    int a[110][110];
    int n;
    int main(){
        
        int t;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d",&n);
            memset(a,0,sizeof(a));
            memset(dp,0,sizeof(dp));
            for(int i=0;i<n;i++){
        
                for(int j=0;j<=i;j++){
        
                    scanf("%d",&a[i][j]);
                }
            }
            for(int i=0;i<n;i++){
        
                dp[n-1][i]=a[n-1][i];
            }
            for(int i=n-1;i>=0;i--){
        
                for(int j=0;j<=n;j++){
        
                    dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
                }
            }
            printf("%d\n",dp[0][0]);
        }
        return 0;
    }

[E：母牛的故事（DP）][E_DP]

类似于斐波拉契数列和楼梯问题，也是一道水题

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    ll f[60];
    int main(){
        
        for(int i=1;i<55;i++){
        
            if(i==1)
                f[i]=1;
            else if(i==2)
                f[i]=2;
            else if(i==3)
                f[i]=3;
            else
                f[i]=f[i-1]+f[i-3];
        }
        int n;
        while(~scanf("%d",&n)){
        
            if(n==0)
                break;
            printf("%lld\n",f[n]);
        }
        return 0;
    }

[F：River Hopscotch（二分）][F_River Hopscotch]

这道题感觉还是有点懵，虽然告诉我用二分，但是都还是有点不会，看了别人的博客才有所领悟，居然还有这种操作，归根结底：题做少了。。。

[https://blog.csdn.net/qq\_28954601/article/details/54766798][https_blog.csdn.net_qq_28954601_article_details_54766798]

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[50010];
    int l,n,m;
    int main(){
        
        scanf("%d%d%d",&l,&n,&m);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
        }
        a[0]=0;
        a[n+1]=l;
        n+=2;
        sort(a,a+n);
        int low=99999999;
        int high=l;
        for(int i=1;i<n;i++){
        
            low=min(low,a[i]-a[i-1]);
        }
        while(low<=high){
        
            int mid=(low+high)/2;
            int cnt=0;
            int s=0,e=1;
            while(e<n){
        
                if(a[e]-a[s]>=mid){
        
                    s=e;
                    e++;
                }
                else{
        
                    e++;
                    cnt++;
                }
            }
            if(cnt>m){
        
                high=mid-1;
            }
            else
                low=mid+1;
        }
        printf("%d\n",high);
        return 0;
    }

这几道题感觉还挺好的，虽然都不是太难，但是还是再一次提醒了我许多

[A_DFS]: http://poj.org/problem?id=1321
[B_BFS]: http://poj.org/problem?id=3984
[C_Allowance]: http://poj.org/problem?id=3040
[https_blog.csdn.net_zwj1452267376_article_details_50429521]: https://blog.csdn.net/zwj1452267376/article/details/50429521
[D_DP]: http://acm.hdu.edu.cn/showproblem.php?pid=2084
[E_DP]: http://acm.hdu.edu.cn/showproblem.php?pid=2018
[F_River Hopscotch]: http://poj.org/problem?id=3258
[https_blog.csdn.net_qq_28954601_article_details_54766798]: https://blog.csdn.net/qq_28954601/article/details/54766798