首页 > 其他分享 >2681. 英雄的力量 (Hard)

2681. 英雄的力量 (Hard)

时间:2023-06-14 09:26:49浏览次数:47  
标签:nums Hard times num 英雄 力量 2681 mod

问题描述

2681. 英雄的力量 (Hard) 给你一个下标从 0 开始的整数数组 nums ,它表示英雄的能 力值。如果我们选出一部分英雄,这组英雄的 力量 定义为:

  • i₀i₁ ,... iₖ 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i₀],nums[i₁] ... nums[iₖ])² * min(nums[i₀],nums[i₁] ... nums[iₖ])

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案 可能非常大,请你将结果对 10⁹ + 7 取余。

示例 1:

输入:nums = [2,1,4]
输出:141
解释:
第 1 组:[2] 的力量为 2² * 2 = 8 。
第 2 组:[1] 的力量为 1² * 1 = 1 。
第 3 组:[4] 的力量为 4² * 4 = 64 。
第 4 组:[2,1] 的力量为 2² * 1 = 4 。
第 5 组:[2,4] 的力量为 4² * 2 = 32 。
第 6 组:[1,4] 的力量为 4² * 1 = 16 。
第 7 组:[2,1,4] 的力量为 4² * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 
。

示例 2:

输入:nums = [1,1,1]
输出:7
解释:总共有 7 个英雄组,每一组的力量都是 1 。所以所有英雄组
的力量之和为 7 。

提示:

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁹

解题思路

首先,对数组相关的问题,我们要思考了能不能先对数组进行排序,由于这题是选择子序列,即可以不连续,因此数组的顺序对结果没有影响。

然后,我们可以采取贡献法的思路,即对每个元素,考虑它作为最大值时,对结果的贡献。

例如,考虑 $[1,\ 2,\ 3,\ 4,\ 5]$,$4$ 作为最大值时,对结果的贡献为 $4^2 \times(1 \times 2^2 + 2\times 2^1 + 3 \times 2^0 ) + 4^3$,记为 $a_3^2 s_3 + a_3^3$,$5$ 作为最大值时,对结果的贡献为 $5^2\times (1\times 2^3 + 2\times 2^2+ 3\times2^1 + 4) + 5^3$,记为 $a_4^2 s_4 + a_4^3$。

有 $s_i = 2 * s_{i - 1} + a_{i - 1}$。

因此,我们可以在 $O(1)$ 时间内计算出结果,注意取模防止溢出!。

代码

class Solution {
  public:
    int sumOfPower(vector<int> &nums) {
        int mod = 1000000007;
        sort(nums.begin(), nums.end());
        long res = 0;
        long s = 0;
        int n = nums.size();
        for (long num : nums) {
            res = (res + ((num * num) % mod) * ((num + s) % mod)) % mod; // 防止溢出
            s = (2 * s + num) % mod;
        }
        return res;
    }
};

标签:nums,Hard,times,num,英雄,力量,2681,mod
From: https://www.cnblogs.com/zwyyy456/p/17479221.html

相关文章

  • 41.缺失的第一个正数 (Hard)
    问题描述41.缺失的第一个正数(Hard)给你一个未排序的整数数组nums,请你找出其中没有出现的最小的正整数。请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。示例1:输入:nums=[1,2,0]输出:3示例2:输入:nums=[3,4,-1,1]输出:2示例3:输入:nums=[......
  • 2646. 最小化旅行的价格总和 (Hard)
    问题描述2646.最小化旅行的价格总和(Hard)现有一棵无向、无根的树,树中有n个节点,按从0到n-1编号。给你一个整数n和一个长度为n-1的二维整数数组edges,其中edges[i]=[aᵢ,bᵢ]表示树中节点aᵢ和bᵢ之间存在一条边。每个节点都关联一个价格。给你一个......
  • send it failed() The virtual circuit was reset by the remote side executing a ha
    串口调试助手报错提示Thevirtualcircuitwasresetbytheremotesideexecutingahardorabortiveclose.forupdsocket,theremotehostwasunabletodeliverapreviouslysentUDPdategramandrespondedwithaportunreachableICMPpackettheapplicationsh......
  • 【每日一题】LeetCode 913.猫和老鼠(hard题)
    题目两位玩家分别扮演猫和老鼠,在一张无向图上进行游戏,两人轮流行动。图的形式是:graph[a]是一个列表,由满足ab是图中的一条边的所有节点b组成。老鼠从节点1开始,第一个出发;猫从节点2开始,第二个出发。在节点0处有一个洞。在每个玩家的行动中,他们必须沿着图中与所在当前......
  • CF1559D2 Mocha and Diana (Hard Version) 题解
    Luogu|Codeforces题意给定两个森林\(A\)和\(B\),均有编号\(1\)到\(n\)的节点,边数分别为\(m_1,m_2\)。现在进行加边操作,但是有两个要求:如果在第一个森林加一条\((u,v)\)的边,第二个森林也要进行同样的操作。反之同理。加边后两个森林依旧是森林。一棵树也是森林。......
  • 爬取网站的背景是获取《王者荣耀》游戏中各个英雄的详细属性数据
    一,选题背景 此次爬取网站的背景是获取《王者荣耀》游戏中各个英雄的详细属性数据,以便进行游戏分析和比较。《王者荣耀》是一款非常流行的多人在线战斗竞技游戏,拥有大量的英雄角色,每个英雄都有其独特的属性和技能。游戏玩家需要通过了解每个英雄的属性和技能,才能更好地制定游戏......
  • ShardingSphere 荣获一等奖!2022 年中国开源创新大赛成绩单公布
    ​......
  • 英雄之旅:为入迷而改变
      英雄之旅:我选择,我存在,我自由。寂静。不再像以前,能到生命力像水流一样在身上流动。不能再像以前那样入迷一件事情,心里想的都是Ta。我再次追溯Ta们的缘由,这次不再是【毫无头绪】,我发现了一些根本的【性质】了。正如苏格拉底所说:“不经过审视的人生,是不值得过的”。这是我寻找Ta......
  • ChatGPT 背后的英雄——AI芯片
    本文分享自天翼云开发者社区《ChatGPT背后的英雄——AI芯片》,作者:w****nAI芯片能为人工智能应用提供所需的基础算力;按技术架构主要分为GPU、FPGA和ASIC。ChatGPT有着大量复杂计算需求的AI模型,AI芯片专门用于处理人工智能应用中的大量计算任务,是不可或缺的底层硬件。随着A......
  • ElasticSearch Shard——本质上是做分布式扩展,副本对于集群的稳定性有很强的影响
    什么是一个Shard?Shard就是一个LuceneIndex,参照文章(深入理解Shard和LuceneIndex)。Index需要多少个Shard?回答这个问题,我们需要先谈谈节点,一个集群有多个节点,具体需要多少个节点合适,是另外一个问题,但是这个数字也会影响我们对Shard数的设置。Shard数=Node数?总体上说,当我们节点数......