CF1859D Andrey and Escape from Capygrad 题解。 题目大意 给定 $n$ 对区间，每对区间由大区间 $[l_i,r_i]$ 和小区间 $[a_i,b_i]$ 构成，保证小区间是大区间的子区间。在任意时间，你可以任意多次使用（可以不使用）以下技能来改变你的当前位置： 选择一个数 $i(1\le i\le n)$ ，满足你当前位置在第 $i$ 对...

这是一道关于无向图中能量传递的问题。给定一个无向图，每个点有一个点权表示其高度，从一个点走到另一个点需要消耗对应高度差的能量，如果能量为负值则表示恢复对应绝对值的能量。现在给出多个询问，每个询问包含起点、终点和初始能量，问能否从起点走到终点并保持能量非负。 通过观察可以发现，走过的点的高度不能高于起点高度与初始能量的和。所以问题转化为能否只经过高度不高于 $h_a+e$ 的点到达 $b$。...

本题是一道关于序列操作的算法题，需要对给定的初始序列进行排序去重，并通过对数列中不同位置元素加上不同的常数来更新序列。具体实现可以使用 set 和 multiset 分别维护当前数列和相邻两数差距，进而求得最大的相邻两数差距作为总的操作次数。每次操作后输出数列中最大值加上操作次数的结果。 题目大意 有一台机器，他会对一个序列执行以下操作： 对序列排序并去重 如果序列中只剩下一...

这道题目是一道关于使用分治算法求逆序对个数的问题。具体思路为：通过二分得到区间中两个部分的最大数位置，然后判断这两个数哪个更大，从而解决问题。 题意 有一个长度为 $n$ 的未知序列，询问 $l,r$ 可以通过花费 $r-l$ 个金币获取 $l$ 到 $r$ 之间逆序对的个数。你需要花费不多于 $5n^2$ 个金币来找到序列中最大数的个数。 思路 用分治来解决。如果询问的区间长度小于...

这道题目要求使用两种魔法（水魔法和火魔法）消灭一组怪物，每个怪物有不同的强度，而魔法的获得速度也不同。通过贪心策略，将尽可能多的水魔法用于消灭怪物，并使用 01 背包预处理得到最大水魔力消耗，然后判断剩余怪物是否能够被火魔法消灭，最终输出最少需要的时间。 题目大意 你有两个魔法，水魔法和火魔法。每秒你分别能获得 $s,f$ 点对应的魔力。现在有 $n$ 个怪物，每个怪物的强度为 $s_i...

这是一道关于电影观看和快乐值的题目。 题目给出了 n 场电影，每场电影能够带来一定的快乐值。但是如果距离上一次观看电影 cnt 天后再观看一场电影，这场电影带来的快乐值会减少 d*cnt（可能减少至负数）。现在要选择不超过 m 场电影观看，使得最终所获得的快乐值最大。 题目大意 有 $n$ 场电影，第 $i$ 场电影能够带来 $a_i$ 的快乐值，但是当距离上一次观看电影 $cnt$ ...

exgcd，即扩展欧几里得算法（Extended Euclidean Algorithm），是欧几里得算法的一个扩展版本。它用于求解两个整数a和b的最大公约数（Greatest Common Divisor，简称GCD），并且可以同时计算出满足贝祖等式 ax + by = gcd(a, b) 的整数解x和y。 题目大意 给定正整数 $N,A,B,C,X$ ，求满足以下要求的三元组 $(i...

这是一道关于动态规划的题目，题目要求在给定的平面上按顺序走过所有点，并且可以选择跳过一些点，求移动总距离和代价之和的最小值。 题目大意 平面上有 $n$ 个点，需要按顺序走过点 $1-n$ ，可以跳过除了点 $1$ 和点 $n$ 以外的一些点，跳过 $c$ 个点的代价是： $2^{c-1}$ if $c>0$ $0$ if $c=0$ 求移动总距离和代价之和的最小值。 ...

时间不会倒流，时间轴上靠后发生的不会影响前面的事，具有无后效性，因此很多时候结合时间来设状态，并用刷表法进行转移，是一种很好的做法。 例题 CF1840F Railguns 题解博客 这题将某人在第 $k$ 秒能否 停留在点 $(i,j)$ 上设为状态 dp[i][j][k] 进行转移，一个人在某个时间要么停留，要么往右/往下走，于是可以列出更新公式（转移方程）。 P2583 地铁...

一些情况下，图不是事先给定，从输入中直接给出的，而是根据实际情况在程序中动态生成的，称为“隐式图”。 路径寻找问题主要是求从某个初状态到某个终状态的最优路径（关键是存在状态间的相互转移，所以可以把状态看作是图上的节点），一般可以转化为隐式图，然后利用图的遍历或者求图的最短路来求解。 例题 隐式图中最短路 CF1846G（把当前的患病状态作为图上的节点，结合每种药的药效用位运算来连边）...