牛客937992666号

题解

/ 注册

全部文章 / 题解（共61篇）

题解 | 区间根号与区间求和 #

给定长度为的数组，执行两种操作：区间根号：将这个区间中的全部元素修改为其开根号后的值，即区间和查询：输出下标在这个区间中的所有元素之和，即维护区间开根号十分困难，但是仔细想会知道开根号的次数不会超过5次(连续开根号次就变成了，...

2026-01-13

0 17

题解 | 余数求和 #

，是从到，但是是，如果，那就是数论分块模板；如果，将直接修改为没有问题；如果，那么对于的这部分来说，的值为0，不用考虑，那么其实的范围为 #include<bits/stdc++.h> using namespace std; #define end...

2026-01-13

0 14

题解 | 下取整乘积求和 #

求，有基本可以确定是数论分块了，但还得乘以以为例：注意到每个块的答案贡献是，设这个块的长度为，那么就是那么就直接用数论分块去累加每个块的答案贡献即可 ...

2026-01-13

0 14

题解 | 区间因数个数之和 #

设表示区间所有数的因子个数之和，那么求区间的因子个数之和为如何求这是暴力循环的代码：因为区间中有个数是的倍数，即有个数的因子包含区间中有个数是的倍数，即有个数的因子包含区间中有个数是的倍数，即有个数的因子包含 ..... int sum&n...

2026-01-13

0 15

题解 | 【模板】整除分块 #

目标是求的和：做法是将相同的连续一个区间看做一个块，例如区间中所有的的的值都相同，那么我直接所以依次枚举区间的左边界，然后找到最大的右边界，然后累加，最后将设置为，继续找下一个块下面是基本代码： int ans = 0; for(int&nb...

2026-01-13

0 17

题解 | 机房传信 #

给你一棵树(因为n个节点，n-1条边)，每个节点的权值就是它的度数，然后若干次查询：求任意两个节点的最短路径上的权值之和使用倍增的算法求解，我们知道使用相同的思想，在DFS中同时存储，从根节点到每个节点的权值之和，记为那么是不是但还是有问题，这里有一点需要警惕： ...

2026-01-13

0 15

题解 | #洛谷 P3398 仓鼠找 sugar #

题目的意思是给定了一棵树，有若干个询问：，问的最短路径和的最短路径是否有交点神奇的结论：如果两条最短路径相交，那么其中一条的最近公共祖先一定在另一条最短路径上证明就是如图所示，如果存在交点，那么可以继续向上走，或者向下走；如果向下走，那么LCA就是向下走的哪个转折点，如果...

2026-01-13

0 21

题解 | #【模板】最近公共祖先（LCA） #

最近公共祖先:在有根树的结构中，对于任意两个节点和,它们的最近公共祖先是指满足下面两个条件的节点: 同时是和的公共祖先(即在到根节点的路径上，也在到根节点的路径上)、是所有公共祖先中深度最大的节点("最近"的本质是距离u 和 v距离最近) 关键性...

2026-01-12

0 20

题解 | #数列 k 重排 #

倍增题目太卡时间了，没意思定义st[i][j]表示从i位置进行了次操作后的下标，为什么是下标呢？我一开始定义的是i位置进行了次次操作后的值，但是发现如果是值的话，转移方程写不了如果是下标，那么转移时，直接就是,初始化st[i][0] = x[i] 所以可以很快...

2026-01-12

0 23

题解 | #环形数组跃迁 #

倍增题目和上一道题差不多，但还是有很些区别(这道题完全靠自己做出来了！) 题目的意思就是不断的跃迁，然后累加上每一次跃迁到达的位置的值，当然跃迁的次数m最大为1e18; 定义st[i][j]表示从i出发，跃迁了次后的结果那么转移的方程：就不是简单的什么st[i][j] =...

2026-01-12

0 33