首页 > 其他分享 >CF889E题解

CF889E题解

时间:2024-08-21 21:37:35浏览次数:15  
标签:log CF889E 题解 bmod ans 答案 res 区间

\(\text{Problem - 889E - Codeforces}\) \(\text{*3000}\)

题意

给一个序列,对于一个非负整数 \(x\),有一个式子:

\[x\bmod a_1+x\bmod a_1\bmod a_2+...+x\bmod a_1\bmod a_2...\bmod a_n \]

求出上式的最大值。

思路

先去寻找题目的性质。

首先 \(x\) 的值单调不增,然后如果当前 \(x\) 的值小于 \(a_i\) 则对 \(x\) 无影响。

对于上述两条,我们首先能够总结出一点:一定存在一个答案区间 \([l,r]\),其中 \(ans_l=ans_r=a_l-1\)。说人话就是首先答案是一段一段的递减区间,然后一定有一段区间的值顶着对应区间的上界。因为如果没有,则可以至少令当前 \(x+1\),然后答案更大。然后就是 \(x+1\) 的操作的正确性是因为余数性质:\(x+y\equiv x\%p+y\%p\pmod p\),所以只要操作后 \(x\) 小于 \(p\) 后面区间就不会变成零,并且我如果将最初的 \(x+1\),那么所有位置的 \(x\) 就都会加一,答案也都会加一。

然后对于这道题有一个显然的暴力 \(dp\)。我们令 \(f_{i,j}\) 表示计算到位置 \(i\) 当前 \(x\) 值为 \(j\) 的最大值,转移显然,复杂度是 \(O(n\times a_1)\)。

考虑能否优化状态。因为答案区间是一段一段的递减,其实我们枚举 \(j\) 的时候就会发现最下面的答案是 \(i\times j\),然后上面变成一段更小的单调不增的区间。然后根据之前发现每个位置对应的 \(x\) 同加同减,也就是说他们的相对值不变,所以如果我们不去维护最后的答案而是只维护上层的答案,那么更新(转移)上面的答案就是 \(O(1)\) 的。比如我转移状态需要修改 \(x\) 时,我只需要把区间整体答案修改即可。

所以我们得到了最终的 \(dp\),设 \(f_{i,j}\) 表示计算到位置 \(i\) 当前 \(x\) 值为 \(j\) 时每个 \(x\) 大于 \(j\) 的部分的和,最后答案就是 \(\max_{0\le i<a_n} \{f_{n,i}+n\times i\}\)。转移时对于 \(f_{i,j}\) 分成两种情况考虑:

  1. 直接转移到 \(f_{i+1,j\%a_{i+1}}\):这时 \(j\) 变小,答案加上 \(j-j\%a_{i+1}\) 的高度;
  2. 每次新维护一个 \(f_{i+1,a_{i+1}-1}\):答案加上的高度类比第一种即可。

存在第二种转移是因为性质一告诉我们一定会有一个 \(x=a_i-1\),所以每次需要维护。

关于复杂度的话,考虑对于每个 \(i\),至多存在 \(0,1,2...,a_i-1\) 一共 \(a_i\) 种状态,所以初始状态可看成 \(n\) 种;每次转移会将 \(j\) 转移到 \(j\% a_i\) 上,已知取模复杂度是一只 \(\log\) 所以状态是 \(n\log x\) 的。然后实际 \(dp\) 的时候,第一维滚掉,第二维发现 \(j\) 太大用 \(\text{map}\) 存,然后 \(\text{map}\) 也有一只 \(\log\),所以时间复杂度是 \(O(n\log x\log n)\)。

代码

signed main(){
    n = rd(), res[p = rd() - 1] = 0;
    for(int i = 2; i <= n; ++i){
        p = rd();
        for(map < ll , ll > :: iterator it = res.lower_bound(p); it != res.end(); res.erase(it++)){
            ll j = (*it).first, f = (*it).second;
            res[j % p] = max(res[j % p], f + (i - 1) * (j - j % p));
            res[p - 1] = max(res[p - 1], f + (i - 1) * ((j + 1) / p * p - p));
        }
    }
    for(map < ll , ll > :: iterator it = res.begin(); it != res.end(); it++)ans = max(ans, n * (*it).first + (*it).second);
    printf("%lld", ans);
    return 0;
}

标签:log,CF889E,题解,bmod,ans,答案,res,区间
From: https://www.cnblogs.com/Nekopedia/p/18372614

相关文章

  • [SCOI2014] 方伯伯的玉米田 题解
    对于每次修改的区间以及其左边序列和右边序列,共三种情况:1.区间内比两侧低的还是低2.区间内比两侧低的变得比两侧高了3.区间内比两侧高的还是高那么现在又面临一个问题:在区间内变化后,对答案,即最长不下降子序列有什么影响。对区间左边:可能会使其最长不下降子序列增长对区间......
  • SP368 CSTREET - Cobbled streets 题解
    题意选n−1条道路连接n个城市,且使得其修建的价格最小。分析最小生成树的模板题,可以用kruskal来做。首先,先将所有的边权从小到大排序。然后,取当前没有选过的,且边权最小的边,判断它连接的两个点是否同属一个集合,如果不是就把他们加到同一个集合中,再记录答案。代码很简单,......
  • [CERC2019] ABB 题解
    题目可以转化为求最长回文子串,答案就是长度减去最长回文子串的长度。看到是求最长回文子串,一眼就容易想到马拉车。此题只需在求出回文半径的基础上储存回文串的右端点,将求出的右端点排序,只要右端点不在最后的字符就结束(不能补),如果在最后的字符就取原字符串长度与当前回文子串的差......
  • [JOISC 2023 Day3] Tourism 题解
    大家好,我喜欢珂朵莉树,所以我用珂朵莉树\(AC\)了本题。实际上,我们比较容易发现,这题实际上就是求\([l,r]\)中的所有点作为关键点时,虚树所压缩的所有点(实际上就是显现出来的点+在虚边上的点)。那么我们容易发现,一个点\(x\)作为虚树所压缩的所有点的充要条件为:\(x\)是至少......
  • 【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
    【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)......
  • SP368 CSTREET - Cobbled streets 题解
    题意选n−1条道路连接n个城市,且使得其修建的价格最小。分析最小生成树的模板题,可以用kruskal来做。首先,先将所有的边权从小到大排序。然后,取当前没有选过的,且边权最小的边,判断它连接的两个点是否同属一个集合,如果不是就把他们加到同一个集合中,再记录答案。代码很简单,......
  • 莫队的 1.5 近似构造 题解
    前言题目链接:洛谷。感觉T4比T3水,虽然我都没做出来。题意简述给定\(1\simn\)的排列\(a\)和\(m\)个区间\([l_i,r_i]\)。定义值域区间\([L,R]\)的价值为\(\operatorname{val}([L,R])\operatorname{:=}\max\limits_{i=1}^m\sum\limits_{k=l_i}^{r_i}[L......
  • P10892 SDOI2024 题解
    【题意简述】你有一个数字\(n\),每次操作将\(n/2\),如果\(n\)是一个奇数,你会纠结是向上取整还是向下取整。问你最少纠结多少次。多组数据。【思路】为了方便起见,我们在二进制下重新审视这个题目:在二进制下,一个数除以\(2\)等同于右移一位。默认向下取整,因为右移会舍弃......
  • P7706 文文的摄影布置 题解
    P7706文文的摄影布置题解原题读完题,发现是线段树。单点修改+区间查询。不过查询的值有些奇怪,就是了,我们考虑用线段树维护这个ψ值(下称待求值)。对于一个区间的待求值,大概有四种情况:如上图四种情况分别为:待求值最大值在左区间待求值最大值在右区间\(a_i与b_j\)在左......
  • 一元柯西问题解法整理与试证明(傅里叶变换的应用)
    关于柯西问题:  柯西问题是指偏微分方程仅有初始条件而无边界条件的定解问题,常用特征线法、分离变量法、格林函数法以及傅里叶变换求解,柯西问题即对于  其中   为主函数, 为初始条件,求解U(x,t)关于傅里叶变换:公式:对于一维方程f(x)有    或  卷积:若,则......