首页 > 其他分享 >CF 1365 题解

CF 1365 题解

时间:2024-11-11 08:49:40浏览次数:1  
标签:cnt 题解 sum CF pos 1365 答案 节点 式子

CF 1365 题解

A Prime Subtraction

任何数的因数中都会有质数, 除非他是 \(1\).

因此原题不合法当且仅当 \(b-a=1\).

B Kill 'Em All

首先, 答案有明确的下界: 最右面的怪兽一定要处理. 不断模拟去杀掉当前最靠右的怪兽, 得到的答案就是答案的下界.

是否能取到下界呢? 答案是肯定的. 注意到刚刚的过程可以顺带把所有怪兽都杀掉, 是一种合法的方案.

C Standard Free2play

考虑每到达一个台阶, 首先它可以没有代价的到达下面一个台阶的上方 \(1\) 格, 然后, 考察下面一个台阶的下方 \(1\) 格是否打开, 没有打开就要花费 \(1\) 的代价到达下方.

这个贪心的正确性在于一定想要用较少的钱到达较低处的位置, 在更高的位置显然不优.

D AB-string

一个很好的性质是字符集只包括两种字符.

这样, 不符合要求的串只有 AAAA...AABABB...BBB 以及类似形式.

扫一遍就可以统计了.

E Keyboard Purchase

首先, 字符集大小 \(n\leq20\), 考虑状压.

答案只与相邻两个字符是什么有关, 与原串无关, 考虑转化: 记 \(cnt_{i,j}\) 表示 字符 \(i,j\) 相邻了多少次, 这是好统计的.

特别的, 对任意 \(i\), 令 \(cnt_{i,i}=0\).

现在要给每个字符分配一个位置排列 \(pos_i\), 则答案是

\[\sum_{i=1}^n\sum_{j=i}^n|pos_i-pos_j|cnt_{i,j} \]

我们想要答案最小.

我们设计一个 dp, 首先, 每次转移按照 \(pos\) 顺序加入一个元素, 加入的这一刻我们能够知道 \(i\) 的 \(pos_i\) 是什么 (就等于目前集合大小), 但是其他的都不知道, 这意味着原来的式子不能直接维护, 需要拆掉, 你把元素都按照 \(pos\) 排序后 (也就是转移顺序) 可以得到:

\[\begin{align*} ans&=\sum_{i=1}^n\sum_{j=i}^n(pos_i-pos_j)cnt_{i,j} \\ &=\sum_{i=1}^npos_i(\sum_{j>i}cnt_{i,j}-\sum_{j<i}cnt_{i,j}) \end{align*} \]

这个式子就比较清晰了, 用 dp 去求解这个式子的最小值就好.

设 \(f_S\) 表示只考虑 \(x\in S\) 的 \(pos_x\) 的贡献, 并且已经决定好它们的 \(pos\), 并且按照 \(pos\) 的顺序加入集合, 则有转移式:

\[f_{S|x}\leftarrow f_S+|S|(\sum_{y\not\in S}cnt_{y,x}-\sum_{y\in S}cnt_{y,x}) \]

由于按照 \(pos\) 序转移, 因此不在 \(S\) 中的元素 \(y\) 会在 \(x\) 之后, 反之则在前面, 因此这个转移式和上面的式子一致.

F The Maximum Subtree

考察每个节点所连子节点情况.

注意到一个节点所有相邻节点都不能有公共区间, 否则有环.

考察一个节点 \([l,r]\), 他可以连出另一个节点 \([l_0,l]\) , 再向左延申, 右侧也同理, 这部分是一条链, 而另外的, 这个节点也可以连出其他节点 \([l+1,l+2],[l+3,l+4],\ldots [r-2,r-1]\). 因此, 这个树是一个链套菊花的结构.

设计一个类似于找最长链的 dp 就可以了, 答案统计和转移式都是类似的.

Adilbek and the Watering System

这个东西很像一个反悔贪心, 但是你会发现不好维护上界小于等于 \(c\) 的约束.

考虑脱离用堆维护反悔贪心框架的束缚, 考虑把运水的费用当用水时再计算.

考虑每次运水, 就尝试接受所有的水, 如果溢出了的话就尝试把当前最贵的水舍弃掉.

每次用水, 就把最便宜的水用掉并计入答案.

考虑需要维护最大值和最小值, map 是满足要求的, 模拟即可.

标签:cnt,题解,sum,CF,pos,1365,答案,节点,式子
From: https://www.cnblogs.com/snowycat1234/p/18538992

相关文章

  • 「杂题乱刷2」CF1354E
    题目链接CF1354EGraphColoring(*2100)解题思路发现这个东西就是类似于二分图染色的东西。因为\(2\)只能和\(1,3\)链接。其余种类的点都不能连接。不妨把\(1,3\)都看成同一个点放到最后处理。那么我们就相当于是要找到一种方案使得选择每个联通快的黑点或白点,使得最......
  • 操作系统FCFS护航效果
    如果第一个作业的爆发时间是最高的,FCFS可能会受到队列影响。就像在现实生活中一样,如果队列在路上经过,那么其他人可能会被堵塞,直到完全通过。这也可以在操作系统中进行模拟。如果CPU在就绪队列的前端获得较高突发时间的进程,则较低突发时间的进程可能被阻塞,这意味着如果执行中......
  • 「杂题乱刷2」CF1370F2
    题目链接CF1370F2TheHiddenPair(HardVersion)(*2700)题目描述真的很难吗?我们首先考虑找出第一个特殊点。我们可以先求出这两个点路径中的任意一个点。发现询问\(1\simn\)就使我们需要的询问、接下来以这个路径中的一个点为根来确定每个节点的深度。接下来考虑二......
  • CF622E Ants in leaves 题解
    传送门给定一棵\(n\)个节点的树,根节点是\(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过\(1\)秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。根结点的各个子树独立,因......
  • 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{......
  • [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......
  • [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......