CF1852B Imbalanced Arrays 题解 题目大意 对于一个给定的长度为 $n$ 的数组 $A$，定义一个长度为 $n$ 的数组 $B$ 是不平衡的当且仅当以下全部条件满足： $-n \leq B_{i} \leq n$ 且 $B_{i} \ne 0$。即每个数在 $[-n,n]$ 内且不为 $0$。 $\forall i,j \in...

CF1824B1 LuoTianyi and the Floating Islands 题解 题目大意 给定一棵 $n$ 个结点的树，现在有 $k(k\le \min(n,3))$ 个结点上有人。 一个结点是好的当且仅当这个点到所有人的距离之和最小。 求在这 $n$ 个点中随机取 $k$ 个点时，好的结点的期望个数，对 $10^9+7$ 取模。 思路 easy 版本的，首先发现，...

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$ 求移动总距离和代价之和的最小值。 ...