牛客937992666号

分类

题解(76)

/ 注册

全部文章（共77篇）

题解 | 机房传信 #

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

2026-01-13

0 33

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

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

2026-01-13

0 45

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

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

2026-01-12

0 45

题解 | #数列 k 重排 #

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

2026-01-12

0 38

题解 | #环形数组跃迁 #

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

2026-01-12

0 74

题解 | #环形字符串跃迁 #

这是一道倍增题目，因为k最大可以取到1e18,所以需要优化转化为二进制来计算定义st[i][j]表示从i这个位置经行次跃迁后到达的位置，那么st[i][j] = st[st[i][j - 1]][j - 1], 表示的是从st[i][j - 1](即先从i这个位置进行次跃迁)然后再进行次跃迁...

2026-01-12

1 45

题解 | #小红出千#

题目的意思是将这n张牌修改成一个顺子，求最小的操作次数修改后的顺子一定是[left, left + 1, left + 2, ... , right]，其中right - left + 1 = n, 也就是长度为n 那么最优的方法就是依次枚举每一个a[i]为左边界left，然后看有多少...

2025-12-22

0 44

题解 | #小红出牌（hard）#

纯思维题目还是很好想的：假设我现在知道了前 i - 1 张的答案，然后我需要求前 i 张牌的答案(为什么是这样想？，因为题目就是这么说的：依次回答的每一个答案那么当我新加入a[i]时，如果前 i - 1张牌里面有 a[i] - 1 或者有 a[i] + 1牌时，那么我是不...

2025-12-22

0 38

题解 | #素数对#

2是唯一一个偶数质数，其他的质数都是奇数所以在中：显然如果都是奇数质数，则为偶数，为奇数，则肯定不满足所以中肯定其中一个为2 所以不妨令，然后枚举小于n的质数即可总代码: #include<bits/stdc++.h> using na...

2025-12-22

0 33

题解 | #小苯的数字权值#

唯一分解定理:任何一个大于1的整数n都可以分解成若干个质数的连乘积那么则的因子总个数为那么对于给定的n，求方案一：全部分解为质数，那么值为方案二：不分解，那么值为方案三：分解部分：例如将n分解为:,那么值为显然方案二总是比方案三更好，所以只需考...

2025-12-22

0 34