H题 - 关于交换求和次序的一点思考
前言
本场比赛的 H 题可以使用 交换求和次序 的方法从数学角度上来直观理解贡献。我之前一直不会交换求和次序来着（拖走）。
权值计算
链接：2026牛客寒假算法基础集训营2 - H
来源：牛客网
题目描述
function f(l, r, s)
展开全文
题目如上；
伪代码理解
题目定义了一个函数 f(l, r, s)，用于计算数组 s从索引 l 到 r 的子数组的“权值”。计算方式如下：
遍历子数组中的每个元素，维护一个集合记录已出现的不同元素，对于每个位置，将“到当前位置为止出现的不同元素个数”累加到总和中，返回这个总和。我们需要计算所有非空子数
展开全文
题目
输入
输出
思路
要算权值需要先理解f函数，f函数计算的是，数组中未重复数的前项个数的累加和。
如{1 3 1}，通过f算出来是1+2+2=5；
题目要求数组所有非空子数组的权值之和，即{1}，{3}，{1}，{1，3}，{3，1}，{1，3，1}权值和。
为了避免超时要用到贡献法。
贡
展开全文
H题 | 权值计算
解题思路：
我们观察题目给出的伪代码，发现任意一个子数组 () 的权值，是其每个前缀数组的数字种类数之和。
对于子数组 1 2 3 2，所有前缀及对应种类数为：
1 => 种数字
1 2 => 种数字
1 2 3 => 种数字
1 2 3 2 =>
展开全文
声明：本题解有参考验题人题解
题目描述
Algorithm 1 函数 f 用于计算数组 s 的权值
function f(l, r, s)
distinct ← ∅
total ← 0
current_count ← 0
for i ← l to r do
if s[i] ∉ distinct
展开全文
根据题目伪代码的意思，就是要求l和r上的前缀中不同元素个数的累加和，暴力的话会超时，所以在遍历的时候记录每个元素出现的位置，对于一个第一次出现的元素，对整个答案的贡献就为项数为n－该位置＋1的等差数列的和，所以每个元素对答案的贡献就是该位置减去该元素第一个出现的位置和那个等差数列的乘积
#in
展开全文
对于这道题,先解释一下一段数组的权值
从伪代码看,就是Σ_{i=l}^{r}dis(l,i),其中dis(l,i)代表s数组按下标(从一开始)从l到i多少个不同的元素,这就是一个数组的权值计算公式
但是,我们还需要计算所有子数组的权值,因此我们需要得到所有的子数组
最终答案也就是ans=Σ_{l=1
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
