乙组

T1：子集和（七） 考虑折半搜索 先暴力预处理出左右两部分的子集和序列 \(b\) 和 \(c\) 并对两序列做排序 然后固定 \(c_i\)，二分找到 \(b\) 序列中第一个大于 \(-c_i\) 的位置 \(j\)，那么对答案的贡献就是 \(|b|-j+1\) 代码实现 #include <b ......

## T1：[序列最大公约数](https://iai.sh.cn/problem/843 "序列最大公约数") $\mathcal{O}(\sqrt{s})$ 枚举 $\gcd$ 即可 代码实现 ``` #include using namespace std; int main() { int ......

题目链接 小清新的区间 DP 题。 看到数据范围以及回文一眼盯真得到是区间 DP。 设 $f[i][j]$ 为区间 $[i,j]$ 成为回文串最少要经过几次操作，转移一个个看。 首先可以删掉第 $j$ 个，$f[i][j]=\min(f[i][j],f[i][j-1]+1)$，同理也可以删掉第 $i ......

题目链接 乙组中比较好的一道思维题。 首先考虑暴力，如果没满就倒满了就往下继续倒，直到倒完或溢出为止，但如果开始就全满然后每次都从最上面倒那么 $O(n^2)$ 就超时了。 我们希望找到一个数据结构（当然不是也行）能够快速得到从某个位置向下（包括当前位置）第一个没满的香槟塔，显然并查集。 初始时每个 ......

这道题是乙组里比较新奇的一题，本来一眼看下来不会，后来蒙了个按照单位时间内收到罚款排序居然对了，十分意外。 简单的证明一下：假设有两个工作，时间分别为 $t_1$ $f_1$ $t_2$ $f_2$，假设把第一个放在前面更优，前面的罚款不变。 则有 $t_1\times f_1+(t_1+t_2)\ ......

## T1：[两数归零](https://iai.sh.cn/problem/817 "两数归零") $a_i + a_j = 0 \Leftrightarrow a_j = -a_i$，用 `std::map` 来统计即可 代码实现 ``` #include #define rep(i, n) f ......

## T1：[树的计数](https://iai.sh.cn/problem/834 "树的计数") 注意到，深度为 $2$ 的点一定是深度为 $1$ 的点的儿子节点，深度为 $3$ 的点一定是深度为 $2$ 的点的儿子节点.....那么深度为 $i$ 的点可以是深度为 $i - 1$ 的儿子节点， ......

令 $loc[i]$ 为 $i$ 的位置，我们看看经过操作后会变成什么。 初始时 $loc[i] = i$。如果有 $r$ 操作，那么 $loc[i] ++$，如果是 $f$ 操作，那么 $loc[i]$ 变为 $n-loc[i]+1$ 即可。 最终的每个 $loc[i]$ 都可以表示为 $sign ......

题目链接 一道诈骗题，英语课上一直在想然后想出来了（ 正难则反，我们很难按照题目所说的得到最少步数，可以考虑从排好序的状态开始。 这样，每次就从首或尾中选择一个移到任意一个位置了，简单了些。 （因为我们只能移动首尾，当前移动到哪里最优貌似可以贪心） 所以下面令初始状态为有序的那个，目标状态为初始时给 ......

T1：录制节目 可以将原题转化成 有 $n$ 条线段，可以保留若干条线段，并且可以分成两部分，使得每部分的线段互不相交 先将所有线段按右端点做升序排序，且按左端点做降序排序 然后维护两个变量 last1 和 last2 last1：第一个部分的最后的端点 last2：第二个部分的最后的端点 尽量让 ......