首页 > 其他分享 >[CodeForces] CF1978 题解

[CodeForces] CF1978 题解

时间:2024-11-11 09:41:59浏览次数:6  
标签:一堆 题解 CodeForces CF1978 CF Luogu Link 编号 等差数列

A. Alice and Books

Link-CF
Link-Luogu

【题目大意】

\(n\) 本书,编号为 \(1\) 到 \(n\),价值为 \(a_1\) 到 \(a_n\)。将这些书分成两堆,你获得每堆编号最大的书的价值。求可以获得的最大的价值。

【解题思路】

无论怎样,编号为 \(n\) 的书不管在那一堆都是编号最大的,所以一定会有它的价值。

那么我们另外一堆中可以获得剩下 \(n-1\) 本书中价值最大的。具体地,\(1\) 到 \(n - 1\) 中最大价值的编号为 \(i\),那么 \(1\) 到 \(i\) 放一堆,\(i + 1\) 到 \(n\) 放一堆,答案为 \(a_i + a_n\),它一定是最优的。


B. New Bakery

Link-CF
Link-Luogu

【题目大意】

一个长度为 \(n\) 的序列,前 \(k\) 项为公差为 \(-1\) 的,首项为 \(b\) 的等差数列。后面的数全是 \(a\)。给定了 \(n\)、\(a\)、\(b\),求序列所有数的和的最大值。

【解题思路】

在最优解中,显然,前 \(k\) 项的等差数列中,每一项都应该比 \(a\) 大,否则将其换成 \(a\) 会更优。所以我们只需要令 \(k = b - a\),这样,前 \(k\) 项都大于 \(a\),并且等差数列第 \(k + 1\) 小于 \(a\),这样是最优的。

最后等差数列求和公式出来即可。注意 \(k\) 的边界条件。


C. Manhattan Permutations

Link-CF
Link-Luogu

标签:一堆,题解,CodeForces,CF1978,CF,Luogu,Link,编号,等差数列
From: https://www.cnblogs.com/Eliauk-FP/p/18539156

相关文章

  • luogu-P3262题解
    简要题意有一棵不超过十层的满二叉树,需要对每个节点进行染色。每个叶子节点会对其颜色相同的祖先节点产生贡献且黑白贡献不同。求最大贡献。题解首先我会暴力!我如果直接暴力枚举每个节点的颜色,复杂度就是\(O(2^{2^n})\)。然后还要算贡献,所以还有一个\(O(2^{n-1}(n-1))\)。然......
  • CF 1365 题解
    CF1365题解APrimeSubtraction任何数的因数中都会有质数,除非他是\(1\).因此原题不合法当且仅当\(b-a=1\).BKill'EmAll首先,答案有明确的下界:最右面的怪兽一定要处理.不断模拟去杀掉当前最靠右的怪兽,得到的答案就是答案的下界.是否能取到下界呢?答案是肯定......
  • CF622E Ants in leaves 题解
    传送门给定一棵\(n\)个节点的树,根节点是\(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过\(1\)秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。根结点的各个子树独立,因......
  • Refact.ai Match 1 (Codeforces Round 985)
    A.Set二分出最大数满足至少有\(k\)个倍数的数。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;usingpii=pair<int,int>;consti32inf=INT_MAX/2;constintmo......
  • ABC372D ABC379F 题解 单调栈二分
    ABC372DABC379F题解单调栈二分一直觉得AT上面学到的东西比CF要多一些,无意捧一踩一,但可能是我太菜的原因,毕竟ABC的题目普遍要比Div.2简单一些。好多次碰到这个单调栈里面二分的trick了,所以写一篇来总结一下。ABC372D形象地给定一系列Buildings的高度\(h\),保证每个......
  • P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度 题解
    P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来:\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{......
  • 历年CSP-J初赛真题解析 | 2019年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客矩阵变幻有一个奇幻的矩阵,在不停的变幻,其变幻方式为:数字0变成矩阵[......
  • [NOIP2012 提高组] 国王游戏 题解
    [NOIP2012提高组]国王游戏典贪心。设当前点为\(i\),\(\prod_{k=0}^{i-1}a_k\)为\(x\),则对于\(i,j\)两点的答案:(为了方便,记\(i+1=j\))\[\mathit{res}_1=\max\bigg(\dfracx{b_i},\dfrac{xa_i}{b_j}\bigg)~;\]若交换,则:\[\mathit{res}_2=\max\bigg(\dfracx{b_j},\dfrac{......
  • B. Replacement (python解)-codeforces
    B.Replacement(python解)-codeforces原题链接:B.Replacement问题分析:我们有两个二进制字符串:s(长度为n)和r(长度为n-1)。根据游戏规则,我们需要在s上执行n-1次操作。在每次操作中,我们选择一个索引k,使得s[k]和s[k+1]不相同并将这两个字符替换为r[i](第i次操作中r的......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......