首页 > 其他分享 >CF1995 题解

CF1995 题解

时间:2024-11-08 14:59:19浏览次数:1  
标签:10 le 一个 题解 合法 CF1995 序列 dp

B

有 n 种物品,每种物品价格为 $a_i$,数量为 $c_i$。
要求选取物品的方案,满足价格极差不超过 1,价格总和不超过 m。
最大化价格总和。
$n\le 10^5,m\le 10^{18},a_i,c_i\le 10^9,a_i\neq a_j$

显然只有 \(x\) 和 \(x,x+1\) 两种选择情况。
\(x\) 直接贪心选即可,考虑 \(x,x+1\)。
发现可以先尽量选 \(x\),再尽量选 \(x+1\),再试图进行调整即可。

调整法是解决这种二元规划问题的利器。

C

给定一个序列,可以单点作平方,求使得序列单调不降最小操作步数。
$n\le 10^5,a_i\le 10^6$

存在不是前缀的 1 时无解。
显然从左到右考虑,然而这个数可以积累到很大,我们只能记上一个位置的操作次数。
两个位置之间的操作次数的差形如一个 \(\log\left( \frac{\log}{\log} \right)\),精度误差难以处理。
注意到这个值很小,暴力找即可。
代码

D

给定一个字符串,要求把它分配为若干长度不超过 k 的子串,最小化每个子串结束字符构成的集合的大小。
$1\le k,n\le 2^{18},\lvert\Sigma\rvert\le 18$

转化的好题。

思路解析

注意到转化中有很多优美的性质。
把都合法,在状压意义下变为哪些不合法。

正解

本题一开始有很多转化方式。
注意到字符集很小,那么本题的基调是状压上的。

考虑一种转化:
最后一个位置必选,然后把我们的集合放到串上,此时不存在两个相邻位置距离 \(\geq k\)。
也就是合法当且仅当不存在任何一个长为 k 的子串中不包含选定的字符。
那么若刻画这些子串的字符集合为 \(T_{1},T_{2},\cdots,T_{n-k+1}\),则合法当且仅当 \(S\) 与这些集合都有交。
由于字符集很小,我们可以去判断每一个 \(S\) 是否合法,做到最小化。

使得 \(S\) 与每一个 \(T_{i}\) 都有交比较困难,但容易知道哪些 \(S\) 和某个 \(T_{i}\) 无交(正难则反)。
于是只需对 \(U-T_{i}\) 打上标记,那么它的所有子集都不合法。
高维前缀和维护即可。

实现细节

值得注意的是根据题意,我们的转化是不充要的。
必须钦定把最后一个位置的字符选上。

代码

E

给定长为 $2n$ 的序列,可以任意交换 $a_i,a_{i+n}$。
定义一个序列的权值为把所有 $\forall i\in[1,n],~a_{2i}+a_{2i-1}$ 拍下来后的极差。
最小化序列的权值。
$n\le 10^5$
思路解析

分析,简单变换。
考察性质,使用双指针。
使用 dp 和动态 dp 来实现。

正解

偶数情况直接贪心即可。
奇数情况下的情况非常复杂,进行抽象。
考虑了交换和贡献,可以通过重标号,把原问题变为一个奇环,每个边的两边各有一个权值,可以翻转边的一个模型。

极差的性质很差无法直接 dp,二分加 2-sat 也完全做不了。
但是注意到这样操作生成的数值只有 \(4n\) 种,并且极差具有一定意义下的单调性。
具体来说,在值域序列上考虑的话,固定一个端点,则合法性有单调性。
所以祭出 双指针
(枚举加二分因为枚举的一维复杂度,大概率没有前途了)

那么只需支持加入删除位置来判定。
Easy Version 可以 2-sat,但是看起来就没前途。
注意到,这个环的只在相邻处有影响,容易想到 dp,发现我们加入删除,只需改变共 \(\mathcal O(n)\) 个相邻的转移关系。
于是 动态 dp,使用矩阵刻画转移,是一个位运算的 and or 矩阵,想一下是有结合律的,线段树维护即可。

代码

标签:10,le,一个,题解,合法,CF1995,序列,dp
From: https://www.cnblogs.com/Sugar-Cube/p/18535095

相关文章

  • ICPC23沈阳区域赛 D. Dark LaTeX vs. Light LaTeX 题解
    D.DarkLaTeXvs.LightLaTeXThe2023ICPCAsiaShenyangRegionalContest(The2ndUniversalCup.Stage13:Shenyang)给两个字符串\(s,t\),长度分别为\(n,m\),现在分别取\(s,t\)的子串\(s',t'\),合成一个新的长度为偶数的字符串\(str=s'+t'\),记\(str\)的长度为......
  • 题解:P11249 [GESP202409 七级] 小杨寻宝
    题目显然等价于问所有宝箱是否在一条链上。稍微转化一下题意,即我们现在要找到一条链,使得这条链上有宝物的节点数量尽可能多。想到这里我们发现这个和树的直径比较相似,那么我们直接大胆将深度定义为从根到这个节点上有宝箱节点的数量,然后做一遍树的直径。最后判断直径长度是否等......
  • 题解:3254. 长度为 K 的子数组的能量值
    Problem:3254.长度为K的子数组的能量值I题解:3254.长度为K的子数组的能量值给定一个数组nums和一个整数k,我们需要找出所有长度为k的子数组的“能量值”。根据题意:如果子数组是连续递增的,能量值等于子数组中的最大元素。否则,能量值为-1。以下是两种不同......
  • CF 1365 题解
    CF1365题解AMatrixGame注意到每次操作都相当于会损失一行和一列,那么最多进行可用行列较少的那一个的轮数.判断奇偶性即可,BTroubleSort手玩发现,不管一个属性的元素集合内部多么无序,都可以借助一个其它属性的元素达到有序.归纳证明特别简单.因此,一个序列可以......
  • P5479 [BJOI2015] 隐身术 题解
    题目传送门前置知识后缀数组简介|字符串哈希|二分解法考虑分别计算出编辑距离恰好等于\(k_{0}\in[0,k]\)的答案。观察在编辑距离的存在下,长度差至多为\(k\)。考虑设\(f_{i,j}\)表示最大的\(x\)使得\(s_{1\simx}\)和\(t_{1\simx+j}\)可以在\(i\)次编......
  • P7984 [USACO21DEC] Tickets P 题解
    题目传送门前置知识线段树优化建图|最短路解法考虑对票建虚点,从\(c_{i}\)向\(i+n\)连一条权值为\(p_{i}\)的边,然后从\(i+n\)向\([a_{i},b_{i}]\)连一条权值为\(0\)的边。建出反图后\(1\toi\)和\(n\toi\)的路径集合会有重复统计的部分,不妨以\(dis_{1,i......
  • 快速上手Docker部署Flask项目 附常见问题解决
    一、准备Flask项目1.项目结构有一个app.py文件作为主应用程序入口,内容示例:fromflaskimportFlaskapp=Flask(__name__)@app.route('/')defhello_world():return'Hello,World!'if__name__=='__main__':app.run(host='0.0.0.0&#......
  • P9192 [USACO23OPEN] Pareidolia P 题解
    P9192[USACO23OPEN]PareidoliaP题解首先自然考虑不带修的情况。考虑问题的本质就是求序列中尽量短的bessie序列个数。对于尽量短的理解是对于bessiebessie序列,不考虑其由\(1,8\sim12\)构成的序列,只考虑\(1\sim6,7\sim12\)组成的序列。于是考虑dp:设\(dp_{i......
  • CF1956F Nene and the Passing Game 题解
    处理很妙的题,部分细节请教了未来姚班zyl和LYH_cpp,在此鸣谢。首先考虑把题目给的式子进行转化,设\(i<j\),那么\(i\)和\(j\)能传球当且仅当\(l_i+l_j\lej-i\ler_i+r_j\)。移项并拆开得到,\(i+l_i\lej-l_i\)且\(i+r_i\gej-r_j\),如果画到数轴上的话......
  • 题解:P11253 [GDKOI2023 普及组] 小学生数学题
    所求的式子带除法,模意义下除法计算复杂度带\(\log\)太慢了,先改写成乘法:\(\sum_{i=1}^ni!\timesi^{-k}\)。想求这个式子,最简单的思路就是对于每个整数\(i\in[1,n]\),分别预处理出\(i!\)和\(i^{-k}\)的值,最后乘起来再\(O(n)\)暴力加起来就好了!对于\(i!\),注意到:\[i!=\b......