首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

题解:AT_arc116_b [ARC116B] Products of Min-Max

编程知识
2024年09月08日 20:40

在题库里面乱翻,就翻到了。

因为在这道题里面子序列不需要考虑元素顺序,所以原序列无论是什么顺序都不会影响答案。

所以先把元素按照从大到小的顺序排列,然后考虑每个元素的贡献。

在当前序列中,对于元素 \(a_i\),不妨设其为最小值,并去寻找它能作为哪些序列的最小值。容易发现它作为最小值的时候只能和 \(1\sim i\) 中的元素产生贡献。

具体的,对于当前从 \(1\sim i\) 中选择的 \(a_j\),如果令其为最大值,那么由 \(a_i\)\(a_j\) 这两个值作为最值的序列元素一定都在 \(j\sim i\) 之间,学过集合的同学都知道,这样的序列显然有 \(2^{i-j-1}\) 个。

这样我们就可以得到一个 \(\mathcal{O}(n^2)\) 的解法,如下:

\[\sum_{i=1}^{n}(a_i\times(\sum_{j=1}^{i}(a_j\times 2^{i-j-1}))) \]

由于 \(i-j-1\) 中会出现负数,我们稍微变一下式子可以得到:

\[\sum_{i=1}^{n}(a_i\times(\sum_{j=1}^{i-1}(a_j\times 2^{i-j-1})+a_i)) \]

但是这样显然还不够,于是我们可以
\(j\) 的枚举进行优化。容易想到预处理。

我们用一个中间变量 \(sum\) 表示第二个括号里面的值。每次计算过答案以后,我们让 \(sum\gets sum\times 2+a_i\) 即可。

记得取模。

提交记录

From:https://www.cnblogs.com/Lydic/p/18403542
本文地址: http://www.shuzixingkong.net/article/1835
0评论
提交 加载更多评论
其他文章 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 在学习共享库时使用通过git拉取jenkinsfile时,报错在排查gitlab服务状态,网络通讯,防火墙规则以及Jenkins凭据均可以正常使
Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404 Pipeline流水线通过git拉取Jenkinsfile报错 error: RPC failed; result=22, HTTP code = 404
实现人形角色的攀爬
在Unity实现角色攀爬 前言 开放世界类型的游戏近年也热门起来了,自由攀爬也成了这一类游戏的一大特色。攀爬给了玩家更多探索路径的选择,也让地图设计有了更多思路。这次,我们就来尝试在Unity中制作一个人形角色的攀爬。 注:攀爬是一个角色完整动作系统的一部分,本文暂且抛开其它动作,也不涉及动画,仅针
实现人形角色的攀爬 实现人形角色的攀爬 实现人形角色的攀爬
红黑树
概述 红黑树(Red-Black Tree,R-BTree)是一种自平衡的二叉查找树,在红黑树的每个节点都多出一个存储位表示节点的颜色,颜色只能是红(Red)或者黑(Black)。 红黑树的特性如下: 每个节点或者是黑色的,或者是红色的 根节点是黑色的 每个叶子节点都是黑色的,这里的叶子节点指的是最
红黑树 红黑树 红黑树
关于求合法括号子序列个数
求合法括号子序列个数 题意 背景 合法括号串的定义如下: () 是合法括号串。 如果 A 是合法括号串,则 (A) 是合法括号串。 如果 A,B 是合法括号串,则 AB 是合法括号串。 子串与不同的子串的定义如下: 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。S 的子串可用起始位置 \
编译和分发 Chez Scheme 应用程序
参考 Building and Distributing Applications. 假设源码由两个文件组成,A.ss 和 B.ss,其中 A.ss 依赖 B.ss。下面我们将其编译为可供分发的二进制文件。 将源码转为 object file 在 Chez Scheme 的 REPL 中(下同)输入
Redis 入门 - 图形化管理工具如何选择,最全分类
Redis图形化管理工具可分为四类:命令行工具、桌面客户端工具、网页工具、插件工具。看看哪一款适合你呢?
Redis 入门 - 图形化管理工具如何选择,最全分类 Redis 入门 - 图形化管理工具如何选择,最全分类 Redis 入门 - 图形化管理工具如何选择,最全分类
什么样的人生才是幸福的一生?(与孩子争执过后有感而写)
围绕着你考研和工作的问题和你争执不下,我仔细想了一下,这种争执看似是因为考研或工作的方向,其实是我们两个人关于人生幸福观的不同观点的碰撞。 那么作为一个人,到底未来怎样的生活才能使自己舒服惬意也就是幸福? 我觉得你的观点可能是高薪有钱,生活休闲,这样就是一种幸福。你如今所有的努力和辛苦都是在为这种生
《痞子衡嵌入式半月刊》 第 107 期
痞子衡嵌入式半月刊: 第 107 期 这里分享嵌入式领域有用有趣的项目/工具以及一些热点新闻,农历年分二十四节气,希望在每个交节之日准时发布一期。 本期刊是开源项目(GitHub: JayHeng/pzh-mcu-bi-weekly),欢迎提交 issue,投稿或推荐你知道的嵌入式那些事儿。 上期回
《痞子衡嵌入式半月刊》 第 107 期 《痞子衡嵌入式半月刊》 第 107 期 《痞子衡嵌入式半月刊》 第 107 期