Z_L_G

题解

总结(20) 训练赛(16)

/ 注册

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

脑洞大开-Colorful_Tree

#妙妙题 #二分 #dfn #lca 题意给定一个无根树，每个结点有自己的颜色，处理两种操作求颜色x的生成树的大小将结点x的颜色改为y 思路对于某一种颜色如果只有一个点，生成树大小是0 如果有两个点，生成树大小是这两个点的距离如果在此基础上再加入新的点，会有两种情况一种...

妙妙题二分 dfn lca

2025-08-23

0 8

算法入门-[HAOI2015]树上操作

#dfs序 #线段树题意 1为根的树，n个节点，每个点有点权处理m个操作，操作有三种给某个点的点权+a 给某个点的的子树中所有结点点权+a 询问结点x到根的路径上所有点的权值和思路前两个操作都好处理，借助dfn序把树变为线性结构即可对于询问，dfn无法直接解决到根的路径和，可...

线段树 dfs序

2025-08-23

0 8

算法入门-选点

题意 n个结点的二叉树，1为根，每个结点有一个权值要选择尽可能多的点，选点要满足如下要求选了根那子树中的所有选择的点要比根更大左子树选了一个点，右子树选的点要比他小思路对于选择规则，其实就是满足左结点>右结点>根不妨维护根右左的dfn序，这样子找的就是dfn序中最...

dp dfn 最长上升子序列最长上升子序列优化

2025-08-23

0 8

算法入门-CF383C

#线段树 #树状数组 #dfn 题意 n个结点，n-1条边，根为1 给定每个点的权值v_i 有m个操作，两种 1 a x 将结点a的权值+x，结点a的儿子权值-x，结点a的孙子权值+x，以此类推 2 a 求a节点的权值思路对于每一个点的修改，在这个点的子树中，所有和它奇偶性相同的点操...

线段树 dfn 树状数组

2025-08-20

0 10

算法入门-求和

#线段树 #树状数组 #dfn序题意 n个结点，n-1条边给定根k和每个点的权值v_i 有m个操作，两种 1 a x 将结点a的权值+x 2 a 求a节点所在的子树的所有结点的权值和思路用dfn把树转化成链线段树or树状数组维护单点修改区间查询代码 #include<...

线段树树状数组 dfn

2025-08-20

0 10

算法入门-CF476D

#构造 #gcd 题意给定n和k，选择4n个不同元素构造n个四元组，，其中m为四个元素中最大的，每个四元组中任意两个元素的gcd为k，输出这n个四元组，以及最小的m 思路构造一个互质四元组，然后给所有元素乘上k就满足要求构造最小的互质四元组，任意相邻的三个奇数和其中一个偶数因此构造一个...

构造 gcd

2025-08-19

0 9

算法入门-小G的约数

#数学 #整数分块 #思维题意定义F(n)为n的约数和，G(n)为F(1)+F(2)+...+F(n-1)+F(n) 给定n，求(G(n)) 思路依然考虑贡献，对于一个因子i，包含i的数的个数是n/i个，产生的贡献是i*[n/i]，对于G(n)转换成求对于分块，发现在i超过根号n...

数学整数分块思维

2025-08-19

0 8

算法入门-华华对月月的忠诚

题意对于一个斐波那契序列，给定前两项，求解第n项和第n+1项的gcd 思路更相减损术 gcd(Fn+1,Fn)=gcd(Fn+Fn-1,Fn)=gcd(a,b) 代码 #include<bits/stdc++.h> using namespace std; int main(){...

数学 gcd 思维

2025-08-19

0 7

算法入门-只能吃土豆的牛牛

题意若干个数，第i个数是3^(i-1)，你可以拿取若干个，求解第k大的拿法的权重思路水题，二进制每一位改成3权重即可代码 #include<bits/stdc++.h> using namespace std; long long get_weight(int x){ ...

数学水题

2025-08-19

0 8

算法入门-因数个数和

题意 q次询问，每次给一个x，问1到x的因数个数的和思路考虑每一个因子的贡献，对于因子p，有x/p对：p(1,2,3,……,n/p)。其中前p-1个是已经被枚举过的，p*p这对被计算了两次，所以每个因子的贡献是(x/p-p)*2+1枚举加和即可代码 #include<bits/s...

数学思维

2025-08-19

0 7