YANG's Blog

题目大意给定长度为 $n\ (1 \le n \le 10^5)$ 的数组，$a_i\ (0 \le a_i \le 2^{30})$，$q\ (1 \le q \le 10^5)$ 次查询，每次给定 $l, r$，在区间内任选两个数，求它们或运算后的最小值。 题目链接 思路一个重要性质 假设都是

思路不能超过30次，所以应该往位运算上靠 (反正我当时是没想到) 假设有两个数 $a = (\ldots000)_2$，即二进制以3个零结尾，那么 $\gcd(a, 2^3) = 2^3$。而假如 $a = (\ldots100)_2$，那么 $\gcd(a, 2^3) \neq 2^3$。 所以我

题目大意给定一个 $n$ 节点的树，并且认定 $1$ 号节点为根。初始时，所有节点都是未感染状态，而我们的任务是感染这棵树。 每一秒中，我们依次执行以下两个操作： 如果一个节点 $v$ 的儿子节点中，至少有一个未感染，那么我们就可以至多再感染一个 $v$ 的儿子节点。 感染一个任意未被感染的节点。

前言想写这个东西是因为看了3b1b的线性代数的本质，且学校之前教的线代就是歌姬吧，只会算数，不理解其含义，于是就想写点总结，方便自己复习，如果对这个内容感兴趣，还请看看完整的视频教程，这个博客可能会帮助你记忆。 向量含义$\vec{A} = (x,y)$ 表示 $x \cdot i + y \cdo

题目大意给定一个包含 $n$ 个点、$m$ 条边的图，第 $i$ 条边的长度是 $2^i$。 求一条长度最短的环的长度和边的编号，如果没有输出 $-1$。 题目链接 思路可以发现，前 $i-1$ 条边的长度加起来也比第 $i$ 条边短。所以我们尽量用前面的边来构成环。 那么如何判断是否存在环呢？我们

题目大意给定一个 $n \times n$ 的数字矩阵，代表每个点的高度，每个数各不相同，求一条遍历所有点的路径，要求只能上下左右移动，且高度下降的次数不小于高度上升次数。 题目链接 思路事实上，随便走一条路，如果高度下降的次数大于高度上升的次数，那么我们就反过来走就行了：) 代码123456789

题目大意有一个 $n$ 个点的完全图，每个点上有 $a_i$ 个饼干。我们可以任意选择一个点，让它给每个相邻的节点分一个饼干，如果不够，那就无法执行此操作。 问我们是否可以一直进行此操作？如果不能，那就输出最终每个点剩余的饼干的数量（即所有点的饼干都不够 $n-1$ 个）。 思路其实模拟几次就可以看

题目链接 思路题目要求在树上求最短路，我们很容易想到 LCA 来解决。 但问题是我们需要同时计算能获得的最大值，所以我们需要额外的倍增数组来维护一些值。 那么具体是什么呢？ 假设我们从 $x$ 点出发，到达 $LCA(x, y)$ 的时候，进行了买入操作，在 $LCA(x, y)$ 到 $y$ 的路

题目大意给定一个 $n$ 个数的集合，Alice 和 Bob 轮流操作，Alice 先操作，每次选最大的数，将其减少任意值，再放回集合（需一直满足集合中元素互不相同，且 $a_i \ge 0$）。 原题链接 思路这是一道相当妙的博弈论，这个游戏是个 ICG，也就是说存在必胜策略。我们把数都从小到大排

题目大意给定两个数 $l, r$（$0 < l \le r \le 2^{17}$），将 $[l, l+1, \ldots, r-1, r]$ 的一个任意排列全部异或 $x$，得到一个新的数组 $a$。 给定 $l, r$ 和 $a$ 数组，求 $x$。 题目链接 思路简单版本的做法如下： 按