- 博客(24)
- 收藏
- 关注
RSS订阅原创 题解：P11251 [GESP202409 八级] 美丽路径
求一条路径，使得路径上距离为奇数的点颜色不同，距离为偶数的点颜色相同，输出这条路径最多能包含多少结点。，将两条以它的颜色不同于它的子节点为起点的路径相连。从大到小进行排序，或放进一个大根堆中，取最大的两个相加再加。为起点或终点的美丽路径最多包含多少个结点。为起点或终点的美丽路径，其实就是用结点。的所有子结点，设当前搜索到的子节点为。为起点的美丽路径最多包含多少个结点，为根节点的子树中，经过结点。的所有颜色不同于它的子节点。为根节点的子树中，不以。为根节点的子树中，以。为起点的美丽路径上，
2024-11-13 21:26:02
1026
原创 题解：P11248 [GESP202409 七级] 矩阵移动
开始，每次只能向右或向下移动，走到。的矩阵，你可以选择至多。很容易想到动态规划。
2024-11-07 12:58:15
2113
1
原创 题解：P11029 『DABOI Round 1』A Simple Problem
那时间复杂度为遍历的时长乘上快速幂的时长，即。仔细观察，不难发现。，用等差数列公式求和，为。不知道快速幂的请移步。
2024-09-11 12:42:11
994
原创 二进制的原码、反码和补码。
众所周知，电脑使用二进制来储存数据。为了能存储负数，电脑会将最高的二进制位设为符号位，当符号位为0时，该数为非负整数，当符号位为1时，该数为负数。所以像int和long long这种整型变量就能存储负数，而无符号类型变量等，由于没有符号位，不能存储负数，但能存储的值比有符号类型变量的更大。虽然能存储负数了，但使用这种存储方式将负数与其他数进行运算时，会很麻烦。为了让负数方便地与其他数进行运算，补码就诞生了。
2024-09-05 20:30:51
1108
原创 树状数组详解
树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题（当我没说），现多用于高效计算数列的前缀和， 区间和。以上内容来自网络。
2024-09-02 20:11:59
1057
原创 前缀和解析+B3612【深进1.例1】求区间和 题解
前缀和为一个数组前几个数的和。比如，定义一个a数组，和一个前缀和数组s。那么si∑j1iaj，即a数组前i个数的和。同时，我们还可以得出si的递推公式sisi−1ais00。举个例子，设a数组的元素为114514，那s数组的元素为126111216。
2024-08-28 19:58:06
944
原创 洛谷 P10835 『FLA - I』冲云霄 题解
中的元素都相同，所以根据前面的公式，两两异或后的结果为。中的元素都为正整数，所以根据上面得出的公式(的元素是多少，只要是正整数，结果一定会是。为奇数时，才存在满足条件的序列，因为当。与上面同理，将序列中的元素两两异或为。根据这两条公式，可得出以下结论。为偶数时，才存在满足条件的序列。为偶数时，根据上面得出的公式，的所有项异或得到的结果等于。根据上面得出的结论，分类讨论。的结果肯定也为一个正整数。，判断是否存在一个长度为。中所有元素的值都相同。以外的元素两两异或为。
2024-08-28 18:38:20
890
原创 P10995 【MX-J3-T2】Substring 题解
的所有子串通过开头数字进行分类，在每一类中将子串以长度从小到大排序。由于每一类中的子串的字典序都是以长度排序，所以右端点为。具有单调性，所以只需二分查找字典序第。小的子串属于哪一类，即第一个小于等于。中的下标，则可以很容易地得到。小的子串的左右端点是多少。根据上面的结论，我们可以将。次询问，每次询问为序列。中出现一次，不会出现。的子串的字典序排名，对于每一次询问，由于。
2024-08-28 12:48:15
927
原创 P10724 [GESP202406 七级] 区间乘积 题解
因为不管是按照依照原来的规则，还是新定义出来的规则，都不影响结果。学过奥数的朋友应该都知道，完全平方数的因数个数为奇数，反之亦然，因为它的平方根只能算一次。后的结果必需为奇数，也就是说所有质因子的指数必需为偶数，所以我们只关心。并相乘，求出因数个数。如果因数为奇数个，则该数是完全平方数，否则不是。而求出一个数因数个数，只需将它分解质因数后将所有质因数的指数先各自加。因为它的因数都可以表述为它的若干个质因数的乘积（判断是否为完全平方数时只需用上前面说的方法，将减后的指数加。，查看有多少个的乘积为完全平方数。
2024-08-25 08:00:00
2736
1
原创 P10723 [GESP202406 七级] 黑白翻转 题解
因为删点后只能剩下一棵树，所以所有黑点和根节点的路径中包含的所有的点必需为黑色。也就是说如果一个白点在一条黑点与根节点间的路径中，则必需将这个白点变为黑色。由于黑点不可变为白点，所以删点后的树中必然包含所有原来为黑色的结点，所以我们可以任取一个黑色的结点作为删点后的树和原来的树的根节点。求至少需要将多少白色的结点变成黑色，使得删除完所有白点后，剩余的黑点可构成一棵树。，则说明存在一条黑点与根节点的路径，包含该节点。这样我们遍历时，如果一个结点的直接连接的深度比该点大的点中的。，即子树中没有黑色的结点。
2024-08-24 15:20:29
1006
1
原创 P10723 [GESP202406 七级] 黑白翻转 题解
这样我们遍历时，如果一个结点的直接连接的深度比该点大的点中的 dfs 值为 true，则说明存在一条黑点与根节点的路径，包含该节点。由于黑点不可变为白点，所以删点后的树中必然包含所有原来为黑色的结点，所以我们可以任取一个黑色的结点作为删点后的树和原来的树的根节点。这里需要注意的是，即使我们确定了返回值，也不能直接返回返回值结束函数。为黑色或出现上一段出现的情况，则函数 dfs(x) 返回的值为 true，否则为 false。所包含的子树中至少有一个黑色的结点，否则返回 false，即子树中没有黑色的结点。
2024-08-24 13:07:24
762
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人