吉安企业做网站,做网站和微信小程序,做做网站需要多少钱,外贸网站建设长沙Day1 省选题 思路 取数 可反悔的贪心。我们开一个双向链表记录此时每个数的前/后一个数是什么。一个简单但不一定正确的贪心策略即为#xff1a;每次都取走当前值最大的且可取的数#xff0c;并更新列表。考虑如何使这个贪心思路正确。
设 p r e x pre_x prex 表示 x x …Day1 省选题 思路 取数 可反悔的贪心。我们开一个双向链表记录此时每个数的前/后一个数是什么。一个简单但不一定正确的贪心策略即为每次都取走当前值最大的且可取的数并更新列表。考虑如何使这个贪心思路正确。
设 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,ans−c(1,1)c(1,2)}。对于每个状态会有三个可能的分支
如果 j s i z i jsiz_i jsizi则一种可能的选择即为放弃更换为 j j j考虑更换为 j 1 j1 j1。新的状态为 { i , j 1 , w − c ( i , j ) c ( i j ) } \{i,j1,w-c(i,j)c(ij)\} {i,j1,w−c(i,j)c(ij)}。如果 i i i 不是最后一个集合 一种可能的选择即为决定更换为 j j j开始考虑 i 1 i1 i1 集合的选择。新的状态为 { i 1 , 2 , w − c ( i 1 , 1 ) c ( i 1 , 2 ) } \{i1,2,w-c(i1,1)c(i1,2)\} {i1,2,w−c(i1,1)c(i1,2)}。另外如果 j 2 j2 j2则一种可能的选择即为放弃更换 i i i 中的元素直接考虑 i 1 i1 i1 集合的选择。新的状态为 { 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(i1,1) c(i1,2)\} {i1,2,w−c(i,2)c(i,1)−c(i1,1)c(i1,2)}。
开一个优先队列记录这些状态从中取 k k k 轮即为答案。
文件列表 可以说是 C 语法题
直接按照题意模拟即可注意文件夹名可能会重复。
巧置挡板 暴搜剪枝。由于最终每一个矩形中都有且仅有一个 1 1 1我们不妨在搜索的过程中每次枚举所有包含某一个 1 1 1 的矩形。状态可以这样设计我们用一个长度为 n n n 的序列来表示一条从右上到左下的单调分界线序列中每一个元素表示该行分界线的位置分界线左边为搜索过的区域右边为未搜索的区域。这个状态的答案将表示完成右侧区域最少的边数。
为什么是单调的分界线在任意一种分隔方案中都一定存在一种矩形放置顺序使得每次放置之后分界线仍然是单调的。所以即使是仅考虑单调的分界线状态也一定可以搜索到所有状态这样可以简化状态降低复杂度。然而这样复杂度仍然较高。这里给出几种剪枝的手段
状态可以记忆化哈希之后用 map 存储假设某一行有一个折角分界线相比上一行发生左移如果折角的右下方没有一个 1 1 1则一定会出现空矩形不合法枚举当前矩形时 1 1 1 的个数超过 1 1 1 后可以直接停止不合法。
