思路 首先有一个显然结论：如果我们将所有叶子节点全部遍历过了，那么整棵树都将被遍历。 于是我们只需要考虑叶子节点之间的关系。再其次，我们发现同一棵子树内的叶子节点一定是被连续遍历的。 考虑将 kkk 赋值为 k+1k + 1k+1，那么最终我们是需要直接返回根节点的。 显然，当我们访问完一棵子树后，我们需要返回根节点。令这个点为 pup_upu​，则直接返回的代价是 dpu−dfau=dpu−du

思路 首先，你显然可以用 3n3n3n 次操作求出 a1a_1a1​ 和 xxx。同时整个序列可以按照值分为小于 a1a_1a1​ 和大于 a1a_1a1​ 两部分。 考虑分别处理这两个部分。你希望还可以通过分治的方法，将一个部分再分为一个部分。 但是，由于数据的不随机性，我们不能单纯的选取一个部分的第一个当作分界点，因为容易构造一个有单调性的序列，每次分治都只会被分出来一个数。 既然数据不随机，

思路 首先考虑只有一个询问，区间为 [1,n][1,n][1,n] 的做法。 定义 dpidp_idpi​ 表示前 iii 个数中，以 aia_iai​ 结尾的方案数。容易得到状态转移方程： dpi=1+∑j<i∧aj∣aidpjdp_i = 1 + \sum_{j < i \wedge a_j \mid a_i}{dp_j} dpi​=1+j<i∧aj​∣ai​∑​dpj​ 最

思路 首先证明一下当序列扩大时答案一定不劣。考虑 f(l,r)f(l,r)f(l,r) 到 f(l,r+1)f(l,r + 1)f(l,r+1) 的变化。 f(l,r)−f(l,r+1)=sl,r−xsl,r−sl,r+1+xsl,r+1=xsl,r+1−xsl,r−ar+1≤0\begin{aligned} f(l,r) - f(l,r + 1) &= s_{l,r} - xs_{l,r

思路 首先转化原式为： (ai+aj)×(ai+aj+1)≡z(mod3)(a_i + a_j) \times (a_i + a_j + 1) \equiv z \pmod 3 (ai​+aj​)×(ai​+aj​+1)≡z(mod3) 考虑对 ai mod 3,aj mod 3a_i \bmod 3,a_j \bmod 3ai​mod3,aj​mod3 进行分讨： ai/aja_i/a_j

思路 经典贪心，二进制拆分后，从高位往低位枚举。 如果答案的第 iii 位为 111，说明 ∀p∈[1,n]\forall p \in [1,n]∀p∈[1,n]，cpc_pcp​ 的第 iii 位都是 111。进而由异或的性质得到，∀p∈[1,n]\forall p \in [1,n]∀p∈[1,n]，apa_pap​ 的第 iii 位与 bpb_pbp​ 的第 iii 位不同。 但是单单判断第

思路 首先可以将题目的操作转化为： 将一个数 aia_iai​ 异或一个常数 kkk。 将连续两个数 ai,ai+1a_i,a_{i + 1}ai​,ai+1​ 同时异或一个常数 kkk。 那么，你发现最坏情况下，操作次数是 nnn。那么考虑如何将多余步骤给减去。 发现，如果一个区间 [l,r][l,r][l,r]，⊕i=lrai=0\oplus_{i = l}^{r}a_i = 0⊕

思路 容易看出来是个 DP 题，但是你发现 DP 的起点是不好确定的，于是假定第一条边的起点是黑色。然后你发现设为白色的贡献与黑色是相同的，于是直接令第一条边的起点是黑色，最后答案乘以 222 即可。 然后就可以愉快的 DP 了。 首先枚举每条边白色点的数量 kkk，定义 dpi,0/1dp_{i,0/1}dpi,0/1​ 表示确定了前 iii 条边，且第 iii 条边的终点为 黑色/白色。转移就

思路 首先需要知道一个事情，对于一个数 x=∏picix = \prod{p_i^{c_i}}x=∏pici​​，它的约数个数是： ∏(ci+1)\prod{(c_i + 1)} ∏(ci​+1) 那么先将 (kn)\binom{k}{n}(nk​) 展开： ∏i=n−k+1nik!\frac{\prod_{i = n - k + 1}^{n}i}{k!} k!∏i=n−k+1n​i​ 发现一个数

思路 将小于等于 xxx 的元素赋为 111，其余的赋为 000。那么一个区间内小于等于 xxx 的数量就是区间中 111 的数量。 那么，将区间升序排列就是将 111 先堆在前面，将 000 堆到后面；降序排列同理。 考虑动态维护 xxx 的位置，记其位置为 ttt。如果 l≤t≤rl \leq t \leq rl≤t≤r，则 ttt 可能会改变；否则不会改变。 在升序排列中，ttt 将会改变到