编程题目 writeup

  • A+

鉴于你校人均OI背景,我这种弱者得自己找时间补补了。

模拟题

铺地毯(洛谷)

https://www.luogu.org/problem/P1003

编程题目 writeup

这题是一道模拟题,但是有坑。如果直接照着题目文字流程硬写,内存会炸得妥妥的。于是想到既然只判断某个点最上层覆盖的地毯编号,可以尝试逆序分析,储存所有输入,然后从最后一个输入开始判断,如果目标点地毯基点 (x,y) 坐标差值大于等于零且小于等于边长即可找到最上层地毯。

#include <stdio.h>
#include <string.h>

int main()
{
    int n;
    int a[10001], b[10001], g[10001], k[10001], x, y;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d %d", &a[i], &b[i], &g[i], &k[i]);
    }
    scanf("%d %d", &x, &y);
    for (int j = 0; j < n; j++)
    {
        if ((x - a[n - j - 1]) <= g[n - j - 1] && (x - a[n - j - 1]) >= 0 && (y - b[n - j - 1]) <= k[n - j - 1] && (y - b[n - j - 1]) >= 0)
        {
            //这里要稍微留意,地毯编号从1开始,所以n-1才是最后一项
            printf("%d", n - j); //返回编号
            return 0;
        }
    }
    printf("%d", -1); //如果没有覆盖则返回-1
    return 0;
}

数据结构题

小球下落——二叉树入门

编程题目 writeup

分析

这题用的是满的二叉树,所以可以不用写结构体的形式,用数组模拟即可。因此需要掌握一些满树常用的性质,如:D为深度,则节点数为2^D-1;内节点k的左节点编号为2k,右节点编号为2k+1。

代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>

using namespace std;

const int maxd=20;
int s[1<<maxd]; //利用位移运算符
/*
左移以为相当于1*2,那么左移maxd位就可以得到2^(maxd)-1,相当总节点数-1
而数组下标最大值正好是2^(maxd)-1
*/
int main(){
    int D,I;
    while(scanf("%d %d",&D,&I)==2){
        memset(s,0,sizeof(s));//每次重新下落都要重置开关状态为0
        int k,n=(1<<D)-1;//n为最大节点编号
        for(int i=0;i<I;i++){
            k=1; //结点指针,指向目标节点
            while(1){
                s[k]=!s[k]; //下落到节点第一件事是改变开关状态,否则k改变后就不好操作了
                k=s[k]? k*2:k*2+1; //按照改变后的状态为为改变前的小球选方向(反选)
                if(k>n) break; //越界
            }
        }
        printf("%d\n",k/2);//舍去余数
    }
    return 0;
}

注意点

这是一道比较简单的例题,但是还有有几个值得注意和借鉴的技巧,比如

  • 利用1的位移运算表示2的x次幂:(1<<X)==pow(2,X);
  • 注意合理安排节点状态改变的先后顺序,可以用一些逻辑技巧提高程序效率如k=s[k]? k*2;k*2+1;
  • "?"运算符使用方法:var=[表达式1]? [表达式2]:[表达式3]; 当[表达式1]结果为真时var的值等于[表达式2]的结果,否则等于[表达式3]的结果。
  • 关于越界的判断

*算法优化

在理解纯模拟方法的基础上,利用一些技巧可以大大提高算法效率。

比如,我们可以直接分析最后一个球的路线:

由于开关只有两种状态,所以第一个和第二个小球一定会分别落入左右子树,也就是说,对于根节点而言,只需分析小球编号奇偶性就可以知道落到哪个子树。对于子树中的内节点而言同样存在类似规律

规律总结:对于任意一个节点而言,节点的流量规律是一样的,第I个进入该节点的小球如果是奇数,那么它时往走的第(I+1)/2个小球;如果是偶数则是往走的第I/2个小球。然后每次都把下一个节点当成新的根节点重设流量进行判断可得答案。

    while(scanf("%d %d",&D,&I)==2){
        k=1;//入口点为根节点
        for(int i=0;i<D-1;i++){//判断N次时,球应该处于N+1层
            if(I%2){
                k=k*2; I=(I+1)/2;//重设下一节点的流量
            }
            else{
                k=k*2+1; I=I/2;
            }
        }
        printf("%d\n",k); 
    }

树的层次遍历

油田——DFS求连通块

题目概述

输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符所在格子相邻(横、竖方向或者对角线方向),就说它们同属于一个8连块。

#input:
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
#output:
2

分析

这是入门的DFS搜索,关键将问题分析清除即可。首先应搜索到一个区块起点,然后从改起点像洪水一样用同一个编号覆盖所有连通块(Floodfill)。对于一个被覆盖的块而言,需要通过递归调用去遍历其周围八个方向的块,直到达到连通块边界后逐层返回。

总体思路较为简单,关键对于各种边界判定遍历条件判断要细心,否则很容易犯错。

完整代码+注释

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>

const int maxn=100+5;

char pic[maxn][maxn];
int m,n,idx[maxn][maxn];

void print_graph(){ //调试输出
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
            printf("[%c:%d] ",pic[i][j],idx[i][j]);
        printf("\n");
        }
    printf("____________________\n");
}

void dfs(int r,int c,int id){ //i j cnt
    if(r>m||r<0||c>n||c<0)
        return; //防止出格
    if(idx[r][c]>0||pic[r][c]!='@')
        return; //跳过遍历过的和非@的格子
    idx[r][c]=id;//编号
    print_graph();
    //system("CLS");
    for(int dr=-1;dr<=1;dr++) //遍历当前格子的八个方向
        for(int dc=-1;dc<=1;dc++)
            if(dr!=0||dc!=0) //有偏移量才能搜,防止搜自己
                dfs(r+dr,c+dc,id);
                
}

int main(){
    while(scanf("%d%d",&m,&n)==2&&m&&n){
        for(int i=0;i<m;i++)
            scanf("%s",pic[i]);
        memset(idx,0,sizeof(idx));//初始化编号
        int cnt=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(pic[i][j]=='@' && idx[i][j]==0)
                    dfs(i,j,++cnt);//每次找到一个起始点将编号自增后再搜
        printf("%d\n",cnt);//输出编号最后的值就是八连块的数量
    }
    return 0;
}

调试输出信息

[*:0] [*:0] [*:0] [*:0] [@:1] 
[*:0] [@:0] [@:0] [*:0] [@:0]
[*:0] [@:0] [*:0] [*:0] [@:0] 
[@:0] [@:0] [@:0] [*:0] [@:0]
[@:0] [@:0] [*:0] [*:0] [@:0] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:0] [@:0] [*:0] [@:1] 
[*:0] [@:0] [*:0] [*:0] [@:0]
[@:0] [@:0] [@:0] [*:0] [@:0] 
[@:0] [@:0] [*:0] [*:0] [@:0]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:0] [@:0] [*:0] [@:1]
[*:0] [@:0] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:0] 
[@:0] [@:0] [*:0] [*:0] [@:0]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:0] [@:0] [*:0] [@:1] 
[*:0] [@:0] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:1]
[@:0] [@:0] [*:0] [*:0] [@:0]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1] 
[*:0] [@:0] [@:0] [*:0] [@:1] 
[*:0] [@:0] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:1] 
[@:0] [@:0] [*:0] [*:0] [@:1]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:0] [*:0] [@:1] 
[*:0] [@:0] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:1]
[@:0] [@:0] [*:0] [*:0] [@:1] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:2] [*:0] [@:1] 
[*:0] [@:0] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:1] 
[@:0] [@:0] [*:0] [*:0] [@:1] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:2] [*:0] [@:1] 
[*:0] [@:2] [*:0] [*:0] [@:1]
[@:0] [@:0] [@:0] [*:0] [@:1] 
[@:0] [@:0] [*:0] [*:0] [@:1]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:2] [*:0] [@:1] 
[*:0] [@:2] [*:0] [*:0] [@:1] 
[@:2] [@:0] [@:0] [*:0] [@:1]
[@:0] [@:0] [*:0] [*:0] [@:1] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:2] [*:0] [@:1] 
[*:0] [@:2] [*:0] [*:0] [@:1]
[@:2] [@:2] [@:0] [*:0] [@:1] 
[@:0] [@:0] [*:0] [*:0] [@:1] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1] 
[*:0] [@:2] [@:2] [*:0] [@:1]
[*:0] [@:2] [*:0] [*:0] [@:1] 
[@:2] [@:2] [@:2] [*:0] [@:1]
[@:0] [@:0] [*:0] [*:0] [@:1] 
____________________
[*:0] [*:0] [*:0] [*:0] [@:1]
[*:0] [@:2] [@:2] [*:0] [@:1] 
[*:0] [@:2] [*:0] [*:0] [@:1]
[@:2] [@:2] [@:2] [*:0] [@:1] 
[@:0] [@:2] [*:0] [*:0] [@:1]
____________________
[*:0] [*:0] [*:0] [*:0] [@:1] 
[*:0] [@:2] [@:2] [*:0] [@:1]
[*:0] [@:2] [*:0] [*:0] [@:1] 
[@:2] [@:2] [@:2] [*:0] [@:1]
[@:2] [@:2] [*:0] [*:0] [@:1] 
____________________
2
eqqie

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:3   其中:访客  2   博主  1

    • arttba3 arttba3 1

      🐧🐧🐧🐧企鹅TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL

      • Reverier Reverier 1

        紫书上我记得有一个古代象形文字识别的题,用DFS求连通块写还挺有意思的……大哥这么强不如尝试一下😛