3.31学习总结

算法

解题思路

使用dfs,对蛋糕每层可能的高度和半径进行穷举.通过观察我们可以知道第一层的圆面积是它上面所有蛋糕层的圆面积之和,所以我们只要去求每层的侧面积就行了.

因为题目要求Ri > Ri+1且Hi > Hi+1,所以我们可以求出每层的最小体积和侧面积,用两个数组分别储存起来.

然后进入dfs我们从最上层开始对每层的高度和半径进行穷举,要注意的是这道题有很多的剪枝要做不然就会超时.

剪枝1:如果接下来每一层都按照最小的来算,依然大于了总体积则可以剪去.

剪枝2:如果接下来每一层都按照最小的来算,结果已经大于了求出的最优值,可以剪去.

剪枝3:通过变形公式,如果接下来的体积用完所需的最小表面积已经大于了最优值,可以剪去.

然后我们在穷举到最后一层的时候用一个变量来记录最小的面积就好了.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int n,m;
int sv[35];
int st[35];
int min1=2147483647;
int dfs(int deep,int v,int s,int lr,int lh)
{
    if(deep==0)
    {
        if(v==n&&min1>s)
            min1=s;
        return 0;
    }
    if(v+sv[deep-1]>n)
        return 0;
    if(s+st[deep-1]>min1)
        return 0;
    if(s+2*(n-v)/lr>=min1)
        return 0;
    for(int i=lr-1;i>=deep;i--)
    {
        if(deep==m)
        {
            s=i*i;
        }
        int h=min(lh-1,(n-v-sv[deep-1])/(i*i));
        for(;h>=deep;h--)
        {
            dfs(deep-1,v+i*i*h,s+2*i*h,i,h);
        }
    }
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int x=1;x<=m;x++)
    {
        sv[x]=sv[x-1]+x*x*x;
        st[x]=st[x-1]+x*x*2;
    }
    dfs(m,0,0,n,n);
    if(min1==2147483647)
        min1=0;
    printf("%d",min1);
    return 0;
}

 

解题思路

这道题我们用bfs来求逃出迷宫的最短时间.这道题目不同的点在于它多了对应的钥匙和门,并且有的时候还会走回头路.

经过观察可以发现只有找到新的钥匙后走回头路才有意义,所以我们要将钥匙的状态保存下来,这里我们要用到位运算符:&和|.

他们都是在二进制的基础上进行运算的.

&:只有当对应位置都为一运算结果才为一.举例:010&110=010.

|:只有当对应位置都为零运算结果才为一.举例:010|110=110.

了解了这两个位运算符我们就可以用一个值来表示钥匙状态了,我们只要在碰见钥匙时用 '|' 将对应的一加上去,碰到门时用 '&' 判断是否有钥匙就行了.

要注意的是当点所用的时间超过规定时间时就不进入队列.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[25][25];
int j[25][25][1030];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct ss
{
    int x;
    int y;
    int k;
    int t;
}d[650000];
int l,r;
int n,m,t;
int bfs()
{
    ss a;
    while(l<r)
    {
        for(int x=0;x<4;x++)
        {
            a.x=d[l].x+ne[x][0];
            a.y=d[l].y+ne[x][1];
            a.k=d[l].k;
            a.t=d[l].t;

            if(a.x<0||a.y<0||a.x>=n||a.y>=m)
                continue;
            if(g[a.x][a.y]!='*'&&j[a.x][a.y][a.k]!=1)
            {
                if(g[a.x][a.y]=='.'||g[a.x][a.y]=='@')
                {
                    a.t++;
                    if(a.t>=t)
                        return -1;
                    d[r].x=a.x;
                    d[r].y=a.y;
                    d[r].t=a.t;
                    d[r++].k=a.k;
                    j[a.x][a.y][a.k]=1;
                }
                if(g[a.x][a.y]=='^')
                {
                    a.t++;
                    if(a.t>=t)
                        return -1;
                    return a.t;
                }

                if(g[a.x][a.y]>='a'&&g[a.x][a.y]<='z')
                {
                    a.t++;
                    if(a.t>=t)
                        return -1;
                    a.k=a.k|(1<<(g[a.x][a.y]-'a'));
                    d[r].x=a.x;
                    d[r].y=a.y;
                    d[r].t=a.t;
                    d[r++].k=a.k;
                    j[a.x][a.y][a.k]=1;
                }
                if(g[a.x][a.y]>='A'&&g[a.x][a.y]<='Z')
                {if(a.k&(1<<(g[a.x][a.y]-'A')))
                {
                    a.t++;
                    if(a.t>=t)
                        return -1;
                    d[r].x=a.x;
                    d[r].y=a.y;
                    d[r].t=a.t;
                    d[r++].k=a.k;
                    j[a.x][a.y][a.k]=1;
                }}
            }
        }
        l++;
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&t))
    {
        memset(j,0,sizeof(int )*25*25*1030);
        l=r=0;
        for(int x=0;x<n;x++)
        {
            scanf("%s",g[x]);
        }
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<m;y++)
            {
                if(g[x][y]=='@')
                {
                    d[r].x=x;
                    d[r].y=y;
                    d[r].t=0;
                    d[r++].k=0;
                    j[x][y][0]=1;
                }
            }
        }
        printf("%d\n",bfs());
    }
    return 0;
}
类似的题

 解题思路

这道题目与上面的题非常相像只是在进行位运算是有所不同,进行一点小小的处理就行了.

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[100][100];
int j[100][100][100];
int ne[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct ss
{
    int x;
    int y;
    int k;
    int t;
}d[650000];
int l,r;
int n,m,t;
int bfs()
{
    ss a;
    while(l<r)
    {
        for(int x=0;x<4;x++)
        {
            a.x=d[l].x+ne[x][0];
            a.y=d[l].y+ne[x][1];
            a.k=d[l].k;
            a.t=d[l].t;
            if(a.x<0||a.y<0||a.x>=n||a.y>=m)
                continue;
            if(g[a.x][a.y]!='#'&&j[a.x][a.y][a.k]!=1)
            {
                if(g[a.x][a.y]=='.'||g[a.x][a.y]=='*')
                {
                    a.t++;
                    d[r].x=a.x;
                    d[r].y=a.y;
                    d[r].t=a.t;
                    d[r++].k=a.k;
                    j[a.x][a.y][a.k]=1;
                }
                if(g[a.x][a.y]=='X')
                {
                    a.t++;
                    return a.t;
                }

                if(g[a.x][a.y]>='a'&&g[a.x][a.y]<='z')
                {
                    a.t++;
                    int p;
                    switch(g[a.x][a.y])
                    {
                        case 'b':p=1;break;
                        case 'y':p=2;break;
                        case 'r':p=3;break;
                        case 'g':p=4;break;
                    }
                    if(a.k|(1<<p))
                        a.k=a.k|(1<<p);
                    d[r].x=a.x;
                    d[r].y=a.y;
                    d[r].t=a.t;
                    d[r++].k=a.k;
                    j[a.x][a.y][a.k]=1;
                }
                if(g[a.x][a.y]>='A'&&g[a.x][a.y]<='Z')
                {
                    int p;
                    switch(g[a.x][a.y])
                    {
                        case 'B':p=1;break;
                        case 'Y':p=2;break;
                        case 'R':p=3;break;
                        case 'G':p=4;break;
                    }
                    if(a.k&(1<<p))
                    {
                        a.t++;
                        d[r].x=a.x;
                        d[r].y=a.y;
                        d[r].t=a.t;
                        d[r++].k=a.k;
                        j[a.x][a.y][a.k]=1;
                    }
                }
            }
        }
        l++;
    }
    return -1;
}
int main()
{
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(n==0&&m==0)
            break;
        memset(j,0,sizeof(int )*100*100*100);
        l=r=0;
        for(int x=0;x<n;x++)
        {
            scanf("%s",g[x]);
        }
        for(int x=0;x<n;x++)
        {
            for(int y=0;y<m;y++)
            {
                if(g[x][y]=='*')
                {
                    d[r].x=x;
                    d[r].y=y;
                    d[r].t=0;
                    d[r++].k=0;
                    j[x][y][0]=1;
                }
            }
        }
        int p;
        p=bfs();
        if(p==-1)
        {
            printf("The poor student is trapped!\n",p);
        }
        else
        {
            printf("Escape possible in %d steps.\n",p);
        }
    }
    return 0;
}

java知识学习

多态(补充)

通过这两天对多态的学习,我学会了多态的一些知识,所以在此补充.

多态的弊端是无法调用子类特有的方法,只能调用父类和子类共有的方法,这时我们可以通过强制转换然后赋值给另一个子类的对象来调用子类特有的方法.

public class person {
    private String name;
    private int age;
    public person() {
    }

    public person(String name, int age) {
        this.name = name;
        this.age = age;
    }


    public String getName() {
        return name;
    }


    public void setName(String name) {
        this.name = name;
    }


    public int getAge() {
        return age;
    }


    public void setAge(int age) {
        this.age = age;
    }
    public void show(){
        System.out.println(name+","+age);
    }
}
public class student extends person {
    @Override
    public void show() {
        System.out.println("学生的信息:"+getName()+","+getAge());
    }
    public void play(){
        System.out.println("子类的特有方法");
    }
}

以上是两个类,它们两个是继承关系person是student的父类.

public class Main {
    public static void main(String[] args) {
        person a=new student();
        a.setAge(18);
        a.setName("张三");

        a.show();
        a.play();
    }
}

当如此调用这两个类时,会报错,无法使用子类特有的play方法

当我们使用强制转换后就可以使用

public class Main {
    public static void main(String[] args) {
        person a=new student();
        a.setAge(18);
        a.setName("张三");

        a.show();
        student  b=(student) a;
        b.play();
    }
}

运行结果

注意:考虑到当数据量变大时无法记住谁是谁的父类时,进行强制类型转换时可能出现异常,因此进行类型转换之前应先通过instanceof运算符来判断是否可以成功转换.

运算符:instanceof

instanceof 运算符的前一个操作数通常是一个引用类型变量,后一个操作数通常是一个类(也可以 是接口,可以把接口理解成一种特殊的类),它用于判断前面的对象是否是后面的类,或者其子类、实现类的实例。如果是,则返回true,否则返回 false。

在使用 instanceof 运算符时需要注意: instanceof 运算符前面操作数的编译时类型要么与后面的类相 同,要么与后面的类具有父子继承关系,否则会引起编译错误.

使用方法

student  b=new student();
if(a instanceof student==true)
{
     b=(student)a;
}

总结

这个周末学习java的时间有点短,学习的有点慢需要加快速度

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505441.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

教你一键轻松领取阿里云优惠券

随着云计算的普及&#xff0c;越来越多的企业和个人开始选择使用云服务。阿里云作为国内领先的云计算服务提供商&#xff0c;以其稳定、高效、安全的服务赢得了广大用户的信赖。为了吸引用户上云&#xff0c;阿里云推出了优惠券活动&#xff0c;本文将教大家如何一键领取阿里云…

【Linux】深入理解进程状态、优先级和调度:Linux 内核中的实现原理探析

文章目录 前言1. 进程状态1.1. 轻量进程排队这件事情——队列1.2. 进程状态的表述及其影响&#xff1a;1.3. 挂起状态及处理&#xff1a;1.4.理解 Linux 内核源代码中的状态表述&#xff1a; 2. 进程优先级Linux 为什么要调整优先级是要受限的&#xff1f; 3. Linux的调度与切换…

Typora下载激活方案

一、下载 1.在typora官网下载最新版本&#xff0c;并安装: 官网地址 2.获取激活工具 感谢Typora激活方法&#xff08;2023年最新版&#xff09; - AI小智的文章 - 知乎 https://zhuanlan.zhihu.com/p/669618741 二、激活 1.把两个.exe文件复制到typora安装目录下 2.在typor…

ubuntu下给不同串口设置别名

目录 一、绑定设备ID 1.查看设备ID 2.编写usev规则 3.重新加载usev规则 4.查看 二、绑定USB端口号 1.先插入一个串口&#xff0c;查看USB设备信息 2.查看USB转串口信息 3.编写usev规则 4.重新加载usev规则 5.查看 在Ubuntu环境下&#xff0c;有时候工控机或者arm开…

推挽输出与开漏输出

推挽输出与开漏输出 文章目录 推挽输出与开漏输出前言一、推挽输出二、开漏输出总结 前言 在使用GPIO口时&#xff0c;会遇到两种配置&#xff0c;一种叫推挽输出&#xff0c;一种叫开漏输出&#xff0c;今天就简聊一聊这两种模式的差异和选择。 一、推挽输出 如图所示&#…

Lazarus远控组件NukeSped分析

静态信息&#xff1a; 样本md5&#xff1a;9b656f5d7e679b94e7b91fc3c4f313e4 由此可见为假的Adobe Flash Player 的攻击样本 样本分析 通过五个函数&#xff0c;内部调用sub_40159D函数动态获取API函数 利用IDA python解密字符串。。 完整python代码 Python> idc.get_…

扫雷(蓝桥杯)

题目描述 小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下&#xff0c; 在一个二维平面上放置着 n 个炸雷&#xff0c;第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处存在一个炸雷&#xff0c;它的爆炸范围是以半径为 ri 的一个圆。 为了顺利通过这片土…

Mac air 个人免费版VMWare Fusion安装及配置教程

Mac air 安装免费版VMWare Fusion教程及问题解决 1、下载VMWare Fusion2、下载wins镜像文件3、开始配置4、出现的问题及解决方法4.1 如何跳过启动时的网络连接4.2 启动后&#xff0c;无法连接网络怎么办4.3 怎么实现将文件拖拽到虚拟机中 当你手上是一台Mac电脑&#xff0c;却需…

【博弈论3——二人博弈的纳什均衡】

1.俾斯麦海之战 2. 零和博弈的定义 零和博弈&#xff08;Zero-Sum Game&#xff09;是一种博弈论的基本概念&#xff0c;指的是在博弈过程中&#xff0c;博弈参与者之间的收益和损失之和总是一个常数&#xff0c;特别是总和为零。即博弈一方的收益必然等于另一方的损失&#x…

RCG自条件是如何添加到 Pixel Generator上的?

在自条件的训练过程中&#xff0c;需要将图像经过Pretrained encoder的表征Rep输入进已有的Pixel Generator上&#xff0c;目前RCG是向四种Pixel Generator上加入了自条件&#xff0c;关于它是如何将rep加到Pixel Generator上的&#xff0c;我来总结一下&#xff1a; 一、Pixel…

[SpringCloud] Feign Client 的创建 (一) (四)

文章目录 1.FeignClientsRegistrar2.完成配置注册2.1 registerDefaultConfiguration方法2.2 迭代稳定性2.3 registerFeignClients方法 1.FeignClientsRegistrar FeignClientsRegistrar实现ImportBeanDefinitionRegistrar接口。 2.完成配置注册 public void registerBeanDefinit…

JQ 查看图片的好插件

效果图 插件官网 https://blog.51cto.com/transfer?https://github.com/fengyuanchen/viewer 使用 <!DOCTYPE html> <html lang"en"> <head><meta charset"utf-8"><link rel"stylesheet" href"css/viewer.c…

攻防世界——catfly

这道题我觉得很难&#xff0c;我当初刷题看见这道题&#xff0c;是唯一一道直接跳过的&#xff0c;现在掌握了一点知识才回来重新看 这道题在linux运行下是这样&#xff0c;我首先猜测是和下面这个time有关&#xff0c;判断达到一定次数就会给我flag 但是我找了好久都没找到那…

(九)信息融合方式简介

目录 前言 一、什么是信息融合&#xff1f; 二、集中式信息融合与分布式信息融合 &#xff08;一&#xff09;集中式融合 &#xff08;二&#xff09;分布式融合 1.简单信息融合 2.CI&#xff08;协方差交叉&#xff09;信息融合 3.无反馈的最优分布式融合 4.有反馈的…

反应式编程(一)什么是反应式编程

目录 一、背景二、反应式编程简介2.1 定义2.2 反应式编程的优势2.3 命令式编程 & 反应式编程 三、Reactor 入门3.1 Reactor 的核心类3.2 Reactor 中主要的方法1&#xff09;创建型方法2&#xff09;转化型方法3&#xff09;其他类型方法4&#xff09;举个例子 四、Reactor …

论文笔记:GPT-4 Is Too Smart To Be Safe: Stealthy Chat with LLMs via Cipher

ICLR 2024 reviewer评分 5688 1 论文思路 输入转换为密码&#xff0c;同时附上提示&#xff0c;将加密输入喂给LLMLLM输出加密的输出加密的输出通过解密器解密 ——>这样的步骤成功地绕过了GPT-4的安全对齐【可以回答一些反人类的问题&#xff0c;这些问题如果明文问的话&…

【C++】set和map

set和map就是我们上篇博客说的key模型和keyvalue模型。它们属于是关联式容器&#xff0c;我们之前说过普通容器和容器适配器&#xff0c;这里的关联式容器就是元素之间是有关联的&#xff0c;通过上篇博客的讲解我们也对它们直接的关系有了一定的了解&#xff0c;那么下面我们先…

蓝桥杯-python-常用库归纳

目录 日期和时间 datetime模块 date日期类&#xff0c;time时间类&#xff0c;datetime日期时间类 定义date&#xff08;年&#xff0c;月&#xff0c;日&#xff09; data之间的减法 定义时间&#xff08;时&#xff0c;分&#xff0c;秒&#xff09; 定义datetime&#xf…

42.HarmonyOS鸿蒙系统 App(ArkUI)实现横屏竖屏自适应

HarmonyOS鸿蒙系统 App(ArkUI)实现横屏竖屏自适应 媒体查询作为响应式设计的核心&#xff0c;在移动设备上应用十分广泛。媒体查询可根据不同设备类型或同设备不同状态修改应用的样式。媒体查询常用于下面两种场景&#xff1a; 针对设备和应用的属性信息&#xff08;比如显示…

【Linux】进程实践项目 —— 自主shell编写

送给大家一句话&#xff1a; 不管前方的路有多苦&#xff0c;只要走的方向正确&#xff0c;不管多么崎岖不平&#xff0c;都比站在原地更接近幸福。 —— 宫崎骏《千与千寻》 自主shell命令编写 1 前言2 项目实现2.1 创建命令行2.2 获取命令2.3 分割命令2.4 运行命令 3 源代码…