蓝桥杯第三周算法竞赛D题E题
发现更多计算机知识,欢迎访问Cr不是铬的个人网站
D迷宫逃脱
拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢?
这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候,会消耗一把钥匙。当没有钥匙的时候就不能移动了。想到这里,我们可以定义一个三维的dp数组.
- 定义dp
dp[i][j][k]表示从位置(1,1)到(i,j)消耗k把钥匙的最大值
- 初始化
memset(dp,-0x3f3f,sizeof(dp))
dp[i][j][0] = a[1][1]
- 状态转移方程
dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k] + a[i][j])
dp[i][j][k] = max(dp[i][j][k],dp[i-1][j][k-1] + a[i][j])互质
dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k] + a[i][j])
dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1] + a[i][j])互质
- 输出答案
从dp[n][m][0] ~ dp[n][m][k]找到最大的即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=1e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int main()
{//不加不能AC//优化输入/输出操作的性能,并精确控制输出的格式ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int n,m,p;//读入行宽与高还要钥匙数目cin>>n>>m>>p;//适当开大一点//dp[i][j][k]表示从(1,1)到(i,j)消耗k把钥匙的最大路径和LL dp[n+5][m+5][p+5];LL a[n+5][m+5];for(int i = 1; i <= n;i++)for(int j = 1; j <= m;j++)cin>>a[i][j];//初始化memset(dp,-0x3f3f,sizeof(dp));dp[1][1][0] = a[1][1];for(int i = 1; i<= n; i++)for(int j = 1; j <= m;j++)for(int k = 0; k <= p; k++){//能够从上转移if(i > 1){if(gcd(a[i-1][j],a[i][j]) == 1) {if (k > 0)//不可能出现互质且没消耗一把钥匙的情况{ dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + a[i][j]); }}else { dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k] + a[i][j]); }}//能够从左边转移if(j > 1){if(gcd(a[i][j-1],a[i][j]) == 1) {if (k > 0)//不可能出现互质且没消耗一把钥匙的情况{ dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + a[i][j]); }}else { dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k] + a[i][j]); }}}//适当小一点LL maxx = -1e18;for(int i = 0; i <= p; i++)maxx = max(maxx,dp[n][m][i]);if(maxx>0)cout<<maxx<<endl;elsecout<<-1<<endl;return 0;
}
E深秋的苹果
这个是一道二分的题目,中规中矩写就行,但是注意此题右端点要开很大!
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N=2e05+10;
const LL mod=1e09+7;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >t;
priority_queue<LL> q;
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n,m;
int a[N];
bool check (LL mid)
{LL pre = 0, sum = 0,group = 1;//刚开始就是一组for(int i = 0; i < n;i++){if(pre + sum * a[i] <= mid)//可以分在一组{pre += sum*a[i];sum += a[i];}else//新开一组{group++;pre = 0;sum = a[i];//这组开始就是a[i]}if(group > m)return false;}return true;
}
int main() {//优化输入/输出操作的性能,并精确控制输出的格式ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);cin>>n>>m;for(int i = 0; i < n;i++)cin>>a[i];//二分思路LL l = 0, r = 3e18;//开大点,防止意外while( l < r){LL mid = l + (r - l)/ 2; //避免可能的超界if(check(mid)) { r = mid; }else { l = mid + 1; }}cout<<l<<endl;return 0;
}
本文由博客一文多发平台 OpenWrite 发布!
相关文章:
蓝桥杯第三周算法竞赛D题E题
发现更多计算机知识,欢迎访问Cr不是铬的个人网站 D迷宫逃脱 拿到题目一眼应该就能看出是可以用动态规划来解决。但是怎么定义dp呢? 这个题增加难度的点就在当所在位置与下一个要去的位置互质的时候,会消耗一把钥匙。当没有钥匙的时候就不能移动了。想…...
国家大基金三期线上金融正式倒计时!11月17日,共启芯片产业新篇章
国家大基金三期线上金融正式倒计时!11月17日,共启芯片产业新篇章 新时代浪潮下,全球化进程不断推动各科技大国的核心发展,芯片作为强有力的竞争标志,是国与国之间的重要技术战争焦点。同时,国内基金发展势…...
Chrony让内网设备时间同步
Centos 搭建NTP服务器 背景:公司服务器时间不同步导致一些认证功能无法使用,网络设备时间不同步日志信息不准确,因此想要在内网搭建一个NTP服务器,作为客户端同步网络时间服务器,作为服务端为内网其他终端提供授时服务…...
在docker中部署MySQL
目录 1、拉取最新的镜像 2、创建mysql容器实例 3、启动mysql实例 4、进入mysql 交互环境 5、登录MySQL数据库 6、尽情享用mysql 1、拉取最新的镜像 docker image pull mysql 2、创建mysql容器实例 第一次执行,需要先创建容器并启动(容器名是mys…...
百家网约车平台发布“阳光五条” 多举措加强司机保障
11月17日,免佣联盟百家网约车平台发布“阳光五条”,通过加大免佣力度、实行车费保镖司机版、72小时保护期等措施,加强对网约车司机的权益保障。 近年,交通运输部推动交通运输新业态平台企业落实“阳光行动”等工作,加…...
JXLS 导出多sheet,带页眉页脚
/*** 生成多sheet Excel* 带自定义页眉页脚** param templatePath* param sheetList* return* throws IOException*/public static byte[] generateMultiSheet(String templatePath, List<JxlsHelper2.SheetContext> sheetList) throws IOException {ByteArrayOutputStre…...
docker数据卷详细讲解及数据卷常用命令
docker数据卷详细讲解及数据卷常用命令 Docker 数据卷是一种将宿主机的目录或文件直接映射到容器中的特殊目录,用于实现数据的持久化和共享。Docker 数据卷有以下特点: 数据卷可以在一个或多个容器之间共享和重用,不受容器的生命周期影响。…...
智能井盖传感器能不能监测井盖位移
智能井盖传感器能够精准监测井盖的位移。这些传感器运用了前沿科技对井盖状态进行实时监测。一旦井盖出现异常移动传感器会立即捕捉到信号,并通过与互联网相连接的智能系统发出警报或记录数据。这种智能监测仪为城市或相关部门的井盖管理提供了实时数据支持…...
.bashrc文件中环境变量配置错误,导致linux命令无法正常使用
问题描述 配置环境变量时出错,导致linux命令无法使用 解决方案: 执行下面命令 export PATH/bin:/usr/local/sbin:/usr/local/bin:/sbin:/bin:/usr/sbin:/usr/bin vim就可以使用了,将错误纠正 vim ~/.bashrc 环境生效 source ~/.bashrc…...
HTML易忽略的角落【目录】
目前已有文章 **** 篇 本专栏是汇集了一些HTML常常被遗忘的知识,这里算是温故而知新,往往这些零碎的知识点,在你开发中能起到炸惊效果。我们每个人都没有过目不忘,过久不忘的本事,就让这一点点知识慢慢渗透你的脑海。 …...
mysql8.0递归
sql举例: WITH recursive c1 AS( select * from course_category where id 1-1union allselect t2.* from course_category t2 INNER JOIN c1 where t2.parentidc1.id) select * from c1 ORDER BY orderby; 解释: WITH recursive c1 AS( //相当于创…...
处理机器学习数据集中字符串列(pandas.get_dummies)
如图,在数据集中week列的数据不是数值型,会导致我们在训练过程中难以处理。 而pandas库中有一个非常好用的函数,独热编码pandas.get_dummies(df) 使用此函数之后,会在原数据中新建各列代表Fri-Sun,值为0或1ÿ…...
一个UE无法注册的问题
问题场景是环境中只有一个小区,UE在找到这个小区,收到MIB SIB1后一直不发起注册。我想这大概是和S准则不满足有关系了,这个问题基本是又没啥好看的了,太简单了,在SIB1周围找找就解决了,于是我发现了以下log…...
自媒体剪辑必备,6个音效素材网站,你值得拥有。
这6个剪辑必备的音效素材网站一定要收藏好了,有了这几个网站能让你在剪辑的时候事半功倍,还不用担心版权问题。话不多说,直接上干货。 1、菜鸟图库 https://www.sucai999.com/audio.html?vNTYwNDUx 菜鸟图库是一个综合性素材网站ÿ…...
uniapp Android如何授权打开系统蓝牙Bluetooth?
uniapp Android如何授权打开系统蓝牙? 使用uniapp开发蓝牙项目过程中,涉及到检测手机系统蓝牙是否打开功能,这里介绍Android,iOS暂时没有找到优方法。朋友们如果有好的方案,欢迎评论分享~ 文章目录 uniapp Android如何…...
图论与网络优化2
CSDN 有字数限制,因此笔记分别发布,目前: 【笔记1】概念与计算、树及其算法【笔记2】容量网络模型 4 最大流及其算法 4.1 容量网络模型 4.1.1 容量网络 容量网络:如果一个加权有向网络 D D D 满足如下三个条件:①…...
ES Kibana windows 安装
ES & Kibana windows 安装 声明: 本文没有实际操作过,只记录。具体操作请参考 ES & Kibana 安装 该文章 JDK1.8,最低要求!ElasticSearch客户端,界面工具! Java开发,ElasticSearch的版…...
分布式事务seata的使用
分布式事务介绍 在微服务架构中,完成某一个业务功能可能需要横跨多个服务,操作多个数据库。这就涉及到到了分布式事务,需要操作的资源位于多个资源服务器上,而应用需要保证对于多个资源服务器的数据操作,要么全部成功&…...
使用宝塔面板安装mysql
1.第一步 在官网https://www.bt.cn/new/download.html下载页面直接在服务器控制面板复制这里的代码下载即可 2.第二步 下载好后按照服务器面版上有个公网地址,含有用户名和密码,保存好,然后通过公网地址打开一个网页,绑定自己注册…...
Flink 支持三种时间语义
在 Apache Flink 中,时间在流处理中是一个重要的概念,而时间语义则用于定义事件发生的时间。Flink 支持三种时间语义,分别是: Processing Time(处理时间): 以机器的系统时间为基准,…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...
渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用
阻止除自定义标签之外的所有标签 先输入一些标签测试,说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时(如通过点击或键盘导航&…...
