YACS

生病了，但是依然强悍。 好久没打 YACS 比赛了。 T1 树的路径 题目大意 https://www.iai.sh.cn/problem/867 给定一棵 \(n\) 个结点的树，点的编号为 \(1\) 到 \(n\)，\(1\) 号点为根。树上第 \(i\) 个点与其父亲的距离为 \(d_i\) ......

目前只有 T2，其他题目我在看。 题目链接1 题目链接2 题目链接3 T2 很简单的一道题，将图分为若干个连通块，然后分别求最小生成树。 从货车运输中得到的结论，最小生成树等价于最小边权上限生成树，也就是它也能够保证选出边中最大的边权最小。 而题目中明确说了这个最小生成树的权值是其中边权的最大值。 ......

题目链接1 题目链接2 题目链接3 榜单终于公布了，这应该是第二长的榜单公布吧。（最长的一次是去年八月，拖到九月开始后才公布） T1 是傻逼数据结构不说了吧，对于每个点枚举以他为角的 $k\times k$ 的四个正方形算一下点的数量，用 $cdq$ 或者扫描线都行。 看这个题目编号是 $81$，看 ......

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 ......

## T1：[幸运儿](https://iai.sh.cn/problem/842 "幸运儿") 幸运儿是 $(x-1+m-1)\%n+1$ 代码实现 ``` #include #define rep(i, n) for (int i = 0; i > n >> x >> m; --x; int a ......

简单题，先二分出直线上 $x$ 最小的点使得这个点在矩形内。 然后不断跳，直到遇到整点。（实际上要用扩欧，但初测能过于是就偷个懒没写） 接着不断跳直到不符合条件。 先 $\sqrt{V}$ 个跳一下，跳完后再一个一个跳就不用写二分了多好。 代码： #include<iostream> #define ......

题目链接 背包 首先想到背包，$f_{i,j}$ 为前 $i$ 个数和为 $j$ 的方案数，但时间复杂度为 $O(n\cdot 20000000)$，会炸。 如果背包跑的时候只跑到当前的 $sum$，就能得到常数的优化，但仍然不足以通过。 插板法 先来考虑一个更简单的问题，每个 $a_i$ 只有下界 ......

看到这题，自然的想到 DP 啦！ 如果设 $f_{i,j}$ 为到第 $i$ 个位置前面的都合法且最后一段和为 $j$ 是否可行，那么转移十分显然，但是状态会炸。 此时我们考虑在状态上进行优化来减少时间，把 $f_i$ 设为到第 $i$ 个位置分段数量最多的情况下且最后一段和最少的和，以及能分成几段 ......

题目链接 小清新的区间 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：第二个部分的最后的端点 尽量让 ......

最近很有空，我填坑来了（ 思路 这道题目有一个很困难的限制：重复玩的角色会让它带来的快乐值清零。我们考虑如何消去这个限制。 考虑如下方法：假如我们考虑 $1\cdots$ $r$ 玩的最大值。区间内的最后一个 $x$ 类型角色玩它得到的快乐值是 $c_x$，倒数第二个 $x$ 类型角色玩它得到的快乐 ......