Day1 省选衔接题 思路总结

Day1 省选题 思路


取数

题面1
可反悔的贪心。我们开一个双向链表记录此时每个数的前/后一个数是什么。一个简单但不一定正确的贪心策略即为:每次都取走当前值最大的且可取的数,并更新列表。考虑如何使这个贪心思路正确。

p r e x pre_x prex 表示 x x x 的前一个元素, n x t x nxt_x nxtx 表示 x x x 的后一个元素, w ( x ) w(x) w(x) 表示 x x x 的值。则在取走 x x x 后,显然 p r e x , n x t x pre_x,nxt_x prex,nxtx 在这之后都不能被选取。**但如果发现选择 p r e x , n x t x pre_x,nxt_x prex,nxtx 会比只选 x x x 更优呢?**考虑这个贪心每轮都至少新挑出一个元素出来,那么在选择 x x x 后放弃 x x x 选择了 p r e x , n x t x pre_x,nxt_x prex,nxtx,可以理解是将 x x x 替换为后两者中的一个(反悔操作),并新选出了后两者中的另一个。而将 x x x 替换为 p r e x , n x t x pre_x,nxt_x prex,nxtx 的收益为 w ( p r e x ) + w ( n x t t ) − w ( x ) w(pre_x)+w(nxt_t)-w(x) w(prex)+w(nxtt)w(x),所以我们就可以将这个值也当作一个可选的点,继续进行贪心。

细节部分,在选择了 x x x 后,可以将链表中的 x x x 直接替换为 p r e x , n x t x pre_x,nxt_x prex,nxtx 两点综合起来。具体地,在计算完 x x x 的贡献后,标记 n x t x , p r e x nxt_x,pre_x nxtx,prex 这两个单独的点分别标记为已选,然后就可以更新 w ( x ) ← w ( p r e x ) + w ( n x t t ) − w ( x ) w(x)\gets w(pre_x)+w(nxt_t)-w(x) w(x)w(prex)+w(nxtt)w(x)。因为 n x t x , p r e x nxt_x,pre_x nxtx,prex 都不能再单独被选,所以按照正常的链表删除操作删除 p r e x , n x t x pre_x,nxt_x prex,nxtx 两个单独的点。

取数2

在这里插入图片描述
题意即为:从 n n n 个集合中各选出一个数求和,求出前 k k k 大的和。为了顺应大家的习惯,这里将 n , k n,k n,k 的意义调换了。

显然最大的取法就是从每个集合中取一个最大值求和,我们设这个最优值为 a n s ans ans。考虑其可能的后几个略小一些的状态。我们将每个集合按照最大值减次大值的差从小到大排序,每个集合内部按从大到小排序。假设当前状态 { i , j , w } \{i,j,w\} {i,j,w} 表示枚举到第 i i i 个集合中的第 j j j 个数,考虑将 a n s ans ans 中第 i i i 个集合取的数更换为 j j j更换后的答案为 w w w。令 c ( i , j ) c(i,j) c(i,j) 表示集合 i i i 中第 j j j 大的值,最初始的状态即为 { 1 , 2 , a n s − c ( 1 , 1 ) + c ( 1 , 2 ) } \{1,2,ans-c(1,1)+c(1,2)\} {1,2,ansc(1,1)+c(1,2)}。对于每个状态会有三个可能的分支:

  • 如果 j < s i z i j<siz_i j<sizi,则一种可能的选择即为放弃更换为 j j j,考虑更换为 j + 1 j+1 j+1。新的状态为 { i , j + 1 , w − c ( i , j ) + c ( i + j ) } \{i,j+1,w-c(i,j)+c(i+j)\} {i,j+1,wc(i,j)+c(i+j)}
  • 如果 i i i 不是最后一个集合:
    • 一种可能的选择即为决定更换为 j j j,开始考虑 i + 1 i+1 i+1 集合的选择。新的状态为 { i + 1 , 2 , w − c ( i + 1 , 1 ) + c ( i + 1 , 2 ) } \{i+1,2,w-c(i+1,1)+c(i+1,2)\} {i+1,2,wc(i+1,1)+c(i+1,2)}
    • 另外,如果 j = 2 j=2 j=2,则一种可能的选择即为放弃更换 i i i 中的元素,直接考虑 i + 1 i+1 i+1 集合的选择。新的状态为 { i + 1 , 2 , w − c ( i , 2 ) + c ( i , 1 ) − c ( i + 1 , 1 ) + c ( i + 1 , 2 ) } \{i + 1,2,w - c(i,2) + c(i,1) - c(i+1,1) + c(i+1,2)\} {i+1,2,wc(i,2)+c(i,1)c(i+1,1)+c(i+1,2)}

开一个优先队列记录这些状态,从中取 k k k​ 轮即为答案。

文件列表

在这里插入图片描述在这里插入图片描述
可以说是 C++ 语法题

直接按照题意模拟即可,注意文件(夹)名可能会重复。

巧置挡板

在这里插入图片描述在这里插入图片描述

暴搜+剪枝。由于最终每一个矩形中都有且仅有一个 1 1 1,我们不妨在搜索的过程中,每次枚举所有包含某一个 1 1 1 的矩形。状态可以这样设计,我们用一个长度为 n n n 的序列来表示一条从右上到左下的单调分界线(序列中每一个元素表示该行分界线的位置),分界线左边为搜索过的区域,右边为未搜索的区域。这个状态的答案将表示完成右侧区域最少的边数。

为什么是单调的分界线?在任意一种分隔方案中,都一定存在一种矩形放置顺序,使得每次放置之后,分界线仍然是单调的。所以即使是仅考虑单调的分界线状态,也一定可以搜索到所有状态,这样可以简化状态降低复杂度。然而这样复杂度仍然较高。这里给出几种:剪枝的手段:

  • 状态可以记忆化,哈希之后用 map 存储;
  • 假设某一行有一个折角(分界线相比上一行发生左移),如果折角的右下方没有一个 1 1 1,则一定会出现空矩形,不合法;
  • 枚举当前矩形时, 1 1 1 的个数超过 1 1 1 后可以直接停止,不合法。

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

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

相关文章

OpenHarmony应用开发引入开源C/C++库---之Har包里的NDK

Har 包 HAR&#xff08;Harmony Archive&#xff09;是静态共享包&#xff0c;可以包含代码、C 库、资源和配置文件。通过 HAR 可以实现多个模块或多个工程共享 ArkUI 组件、资源等相关代码。HAR 不同于 HAP&#xff0c;不能独立安装运行在设备上&#xff0c;只能作为应用模块…

HTML基础(3)

1、内联框架 iframe用于在网页内显示网页&#xff0c;语法如下&#xff1a; <iframe src"URL"></iframe> URL指向隔离页面 hight&#xff0c;weight设置高宽&#xff0c;删除边框将frameborder设置为0 <td> <iframe frameborder"0&qu…

用C代码实现环形缓冲区(ring buf)

用C代码实现环形缓冲区&#xff08;ring buf&#xff09; 概述环境介绍launch.json(没改&#xff09;tasks.json注意 代码ringbuf.cringbuf.hmain.c 测试说明工程代码下载 概述 因嵌入式项目需要&#xff0c;串口接收的数据有很高的周期性发送频率&#xff0c;原方式通过查询接…

VideoGPT:Video Generation using VQ-VAE and Transformers

1.introduction 对于视频展示&#xff0c;选择哪种模型比较好&#xff1f;基于似然->transformers自回归。在没有空间和时间溶于的降维潜在空间中进行自回归建模是否优于在所有空间和时间像素级别上的建模&#xff1f;选择前者&#xff1a;自然图像和视频包括了大量的空间和…

java程序生成exe文件启动时,在没有java环境计算机运行

1.idea项目配置工件 2. 开始构建java程序成jar包 3. 生成exe启动程序 注&#xff1a;下面的输入框中写错了&#xff0c;应该是.\jre才对 4. 在已经选择的生成exe存放文件夹找到已经生成exe启动程序

一文详解静态图和动态图中的自动求导机制

01 静态图与动态图的区别 之前在[1]中提到过&#xff0c;自动求导&#xff08;AutoDiff&#xff09;机制是当前深度学习模型训练采用的主要方法&#xff0c;而在静态图和动态图中对于自动求导的处理是不一样的。作为前置知识&#xff0c;这里简单进行介绍。 我们都知道静态图…

Vue.js------vue基础

1. 能够了解更新监测, key作用, 虚拟DOM, diff算法2. 能够掌握设置动态样式3. 能够掌握过滤器, 计算属性, 侦听器4. 能够完成品牌管理案例 一.Vue基础_更新监测和key 1.v-for更新监测 目标&#xff1a;目标结构变化, 触发v-for的更新 情况1: 数组翻转情况2: 数组截取情况3…

QT:信号与槽

作业&#xff1a; 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和…

Platforms Jumping(贪心,处理策略)

文章目录 题目描述输入格式输出格式样例输入1样例输出1样例输入2样例输出2样例输入3样例输出3提交链接提示 解析参考代码 题目描述 有一条宽度为 n n n 的河流。河的左岸是 0 0 0 单元格&#xff0c;右岸是 n 1 n1 n1 单元格(更正式地说&#xff0c;这条河可以表示为一串从…

MySQL基础练习题:习题2-3

这部分主要是为了帮助大家回忆回忆MySQL的基本语法&#xff0c;数据库来自于MySQL的官方简化版&#xff0c;题目也是网上非常流行的35题。这些基础习题基本可以涵盖面试中需要现场写SQL的问题。上期帮助大家建立数据库&#xff0c;导入数据&#xff0c;接下来让我们继续练习。 …

代码随想录35期Day08-字符串

344.反转字符串 位运算 func reverseString(s []byte) {l : 0r : len(s) - 1for l < r {s[l] ^ s[r]s[r] ^ s[l]s[l] ^ s[r]lr--} }541. 反转字符串II 没技巧 func reverseStringRange(s []byte, l int, r int) {if r > len(s) {r len(s) - 1}for l < r {s[l] ^…

c++的学习之路:22、多态(1)

摘要 本章主要是说一些多态的开头。 目录 摘要 一、多态的概念 二、多态的定义及实现 2.1、多态的构成条件 2.2、虚函数 2.3、虚函数的重写 2.4、C11 override 和 final 2.5、重载、覆盖(重写)、隐藏(重定义)的对比 三、思维导图 一、多态的概念 多态的概念&#…

Harmony鸿蒙南向驱动开发-Regulator

Regulator模块用于控制系统中各类设备的电压/电流供应。在嵌入式系统&#xff08;尤其是手机&#xff09;中&#xff0c;控制耗电量很重要&#xff0c;直接影响到电池的续航时间。所以&#xff0c;如果系统中某一个模块暂时不需要使用&#xff0c;就可以通过Regulator关闭其电源…

Vue3---基础2(component)

主要讲解 component 的创建 以及vue插件的安装 Vue.js Devtools 为谷歌浏览器的Vue插件&#xff0c;可以在调试工具内查看组件的数据等 下载 有两种下载方式 1. 谷歌应用商店 打开Chrome应用商店去下载&#xff0c;这个方法需要魔法 2. 极简插件 极简插件官网_Chrome插件下载_…

【图论】详解链式前向星存图法+遍历法

细说链式前向星存图法 首先要明白&#xff0c;链式前向星的原理是利用存边来进行模拟图。 推荐左神的视频–建图、链式前向星、拓扑排序 比方说有这样一张图&#xff0c;我们用链式前向星来进行模拟时&#xff0c;可以将每一条边都进行编号&#xff0c;其中&#xff0c;红色的…

SQL注入sqli_labs靶场第五、六题

第五题 根据报错信息&#xff0c;判断为单引号注入 没有发现回显点 方法&#xff1a;布尔盲注&#xff08;太耗时&#xff0c;不推荐使用&#xff09; 1&#xff09;猜解数据库名字&#xff1a;&#xff08;所有ASCII码值范围&#xff1a;0~127&#xff09; ?id1 and length…

数字化浪潮下,制造业如何乘势而上实现精益生产

随着数字化技术的迅猛发展&#xff0c;制造业正迎来前所未有的变革机遇。本文将探讨如何利用数字化手段助推制造业实现精益生产&#xff0c;从而在激烈的市场竞争中脱颖而出。 1、构建智能化生产系统 借助物联网技术&#xff0c;实现设备之间的互联互通&#xff0c;构建智能化…

【Qt踩坑】ARM 编译Qt5.14.2源码-QtWebEngine

1.下载源码 下载网站&#xff1a;Index of /new_archive/qt/5.14/5.14.2/single 2.QWebEngine相关依赖 sudo apt-get install flex libicu-dev libxslt-dev sudo apt-get install libssl-dev libxcursor-dev libxcomposite-dev libxdamage-dev libxrandr-dev sudo apt-get …

3. Spring 注解存储对象 Bean的命名规范

从Java5.0开始&#xff0c;Java开始支持注解。Spring做为Java生态中的领军框架&#xff0c;从2.5版本后也开始支持注解。相比起之前使用xml来配置Spring框架&#xff0c;使用注解提供了更多的控制Spring框架的方式。 SpringFramework版本对应jdk版本重要特性SpringFramework 1…

Linux——fork复制进程

1)shell: 在计算机科学中&#xff0c;Shell俗称壳&#xff08;用来区别于核&#xff09;&#xff0c;是指“为使用者提供操作界面”的软件&#xff08;command interpreter&#xff0c;命令解析器&#xff09;。它类似于DOS下的COMMAND.COM和后来的cmd.exe。它接收用户命令&…