首页 > 其他分享 >CF1692H Gambling 题解

CF1692H Gambling 题解

时间:2023-12-03 21:55:21浏览次数:38  
标签:CF1692H le val idx 题解 cnt 端点 区间 Gambling

题意:

思路:

考虑离散化:

枚举 $ x $ 中出现的每一个数 $ val $ , $ val $ 出现的次数为 $ cnt $ ,记录 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ 。设 $ x $ 中与 $ val $ 相等的数贡献为 $ +1 $ ,与 $ val $ 不相等的数贡献为 $ -1 $ ,那么问题转化为最大连续子段和。

由于已经知道 $ val $ 每一次出现的索引 $ idx_i(1 \le i \le cnt) $ ,设区间初始左端点 $ l = idx_1 $ ,区间初始右端点 $ r = idx_1 $ ,最大连续子段和 $ ans = 1 $ ,$ for \space i : 2 \to cnt - 1 $ 枚举每个区间右端点 $ r = idx_i $ ,当区间 $ [l,r] $ 贡献为 $ sum \le 0 $ 时,更新区间左端点为 $ l = idx_i $ ;否则,继续统计区间贡献 $ sum $ , $ ans = max(ans, sum) $ 。

对 $ x $ 中出现的每一个数 $ val $ 进行上述过程即可。

标签:CF1692H,le,val,idx,题解,cnt,端点,区间,Gambling
From: https://www.cnblogs.com/ShawyYum/p/17873870.html

相关文章

  • P1004 [NOIP2000 提高组] 方格取数 题解
    题意:思路:考虑四维$dp$:设$dp[i][j][k][l]$表示两条路径分别走到$(i,j)$和$(k,l)$时所能获取的最大和,显然会超时。考虑三维$dp$:设$dp[i][j][k]$表示两条路径走了$i$步分别走到第$j$行和第$k$行时所能获取的最大和,通过当前步数$i$以及当......
  • vue 编辑器+使用场景+问题解决
    vue编辑器组件添加依赖"dependencies":{"@codemirror/autocomplete":"^6.4.2","@codemirror/commands":"^6.2.1","@codemirror/lang-javascript":"^6.0.2","@codemirror/lan......
  • SP1716 GSS3 - Can you answer these queries III 题解
    题意:给定一个长度为$n$的序列$a$,$q$次操作,每次操作为以下之一:\(0\)\(x\)\(y\):将\(a_x\)修改为\(y\)\(1\)\(l\)\(r\):询问区间\([l,r]\)的最大连续子序列和思路:考虑线段树维护区间最大连续子序列和:线段树每个节点需要维护的信息:区间左端点$l$,区......
  • P3214 [HNOI2011] 卡农 题解
    Description给定\(n,m\),要从\(1,2,\dots,2^n-1\)中选\(m\)个无序的数,使得他们互不相同且异或和为\(0\),问有多少种选法。对\(998244353\)取模。Solution考虑求出有序的方案数的个数再除以\(m!\)。设\(f_i\)表示选出\(i\)个数的方案。那么如果随便选前\(i-1\)......
  • ABC331G题解
    ABC331G日常被bot吊打罢了。首先注意到一件事是你需要求一堆max的期望对吧。所以其实上来就应该试试上min-max容斥的。但是鉴于我没有脑子,所以其实没想到也可以理解。先来复习一下式子:\[Emax(S)=\sum_{T\subsetS}Emin(T)(-1)^{\midT\mid-1}\]所以带入要求的东西......
  • ICPC2022Hangzhou C No Bug No Game 题解
    LinkICPC2022HangzhouCNoBugNoGameQuestion给定\(n\)个物品和上限\(k\),要求最大化分数,物品的选择顺序可以任意第\(i\)个物品一行\(p_i\)代表个数,后面\(p_i\)个\(w_j\)代表容量,定义\(sum=\sum\limits_{j=1}^{i-1}\),对于第\(i\)个物品\(sum+p_i\lek\)......
  • ICPC2022Hangzhou A Modulo Ruins the Legend 题解
    LinkICPC2022HangzhouAModuloRuinstheLegendQuestion求$$\sum\limits_{i=1}^na_i+n\timess+\frac{n(n+1)}{2}\timesd\modm$$的最小值Solution我们把这个式子看成一一个二元不定方程\(ax+by+sum\modm\)的最小值,其中\(a=n,b=\frac{n(n+1)}{2},sum=\sum\limits......
  • ucup nanjing 题解
    比赛链接D收获很大的一道题首先考虑朴素的\(dp\),令\(f_{x,i}\)为\(x\)子树中的每一个叶子到\(x\)的距离都为\(i\)的最小代价不难列出\(dp\)式子为:\(f_{x,i}=\min\limits_{i\in\{0,1\}}\{cost(u,i)+\sum\limits_{v\inson(u)}f_{v,x-i}\}\),其中\(cost(u,i)\)为把......
  • CF1288题解
    CF1288EducationalCodeforcesRound80(RatedforDiv.2)A略CF1288BlinkCF1288B题意给定\(A,B\),问有多少个二元组\((a,b)\)满足\(1\lea\leA,1\leb\leB\)且\(a\cdotb+a+b=\operatorname{conc}(a,b)\)。其中\(\operatorname{conc}(a,b)\)表示将\(a,b\)......
  • [ABC017D] サプリメント 题解
    题目传送门~一道DP前缀和优化好题。题目分析首先,朴素DP非常好想。可以从后向前考虑,设\(f_i\)表示从第\(i\)个补品开始的摄取方法数。摄取一个补品:\(f_i=f_{i+1}\)摄取两个补品:\(f_i=f_{i+2}\)以此类推。则转移方程为:\[f_i=f_{i+1}+f_{i+2}+\dots+f_{j......