#dfs序 #线段树 题意  1为根的树，n个节点，每个点有点权 处理m个操作，操作有三种  给某个点的点权+a 给某个点的的子树中所有结点点权+a 询问结点x到根的路径上所有点的权值和    思路  前两个操作都好处理，借助dfn序把树变为线性结构即可 对于询问，dfn无法直接解决到根的路径和，可以考虑对dfs序操作 dfs序中每个元素出现两次，第一次出现记为+第二次出现记为- 路径和就是dfs序中当前这个点第一次出现的前缀和，线段树维护即可 线段树还得维护区间中+的个数，以保证lazy的传递  代码 #include<bits/stdc++.h> using namespace...

题意  n个结点的二叉树，1为根，每个结点有一个权值 要选择尽可能多的点，选点要满足如下要求  选了根那子树中的所有选择的点要比根更大 左子树选了一个点，右子树选的点要比他小    思路  对于选择规则，其实就是满足左结点>右结点>根 不妨维护根右左的dfn序，这样子找的就是dfn序中最长上升子序列 LIS的朴素维护 ，用二分优化使得复杂度变为  二分优化方法  维护一个数组d[i]记录长为i的LIS的最小结尾 每新添一个元素，lower_bound找第一个大于等于它的  如果存在就替换掉它，扩充后面的空间 如果不存在说明，当前元素会构成新的LIS给dpush_back当前元素  ...

#数位dp A 题意  两个字符串a，b，最终要将b添加到a上面 给定操作序列：如果是V就把b的当前位加入到a的开头，如果是D就加入到末尾  思路  模拟即可  代码 #include<bits/stdc++.h> #define endl '\n' using namespace std; void solve(){ int n,m; string a,b; cin >> n; cin >> a; cin >> m; cin >> b; string op; cin >> op; for(int i=0;i<op....

#线段树 #树状数组 #dfn 题意  n个结点，n-1条边，根为1 给定每个点的权值v_i 有m个操作，两种  1 a x 将结点a的权值+x，结点a的儿子权值-x，结点a的孙子权值+x，以此类推 2 a 求a节点的权值    思路  对于每一个点的修改，在这个点的子树中，所有和它奇偶性相同的点操作是+，所有和它奇偶性不同的点操作是相反的 可以维护两个线段树，一个维护深度为奇数的点，一个维护深度为偶数的点 对于每次修改在两颗树上同步维护就行 对于每次查询根据查询点的奇偶性单独输出即可 线段树只维护变化量，最后输出加上初始值就行，避免建树初始化 另一个思路是维护差分树状数组，代码量较小 附一个...

#线段树 #树状数组 #dfn序 题意  n个结点，n-1条边 给定根k和每个点的权值v_i 有m个操作，两种  1 a x 将结点a的权值+x 2 a 求a节点所在的子树的所有结点的权值和    思路  用dfn把树转化成链 线段树or树状数组维护单点修改区间查询  代码 #include<bits/stdc++.h> #define endl '\n' using namespace std; int v[1010101]; vector<int> G[1010101]; int tim; int L[4040404],R[4040404],dfn[4040404]...

#构造 #gcd 题意  给定n和k，选择4n个不同元素构造n个四元组，，其中m为四个元素中最大的，每个四元组中任意两个元素的gcd为k，输出这n个四元组，以及最小的m  思路  构造一个互质四元组，然后给所有元素乘上k就满足要求 构造最小的互质四元组，任意相邻的三个奇数和其中一个偶数 因此构造一个四元组实际花费6个数的位置， 按要求输出即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,k; cin >> n >> k; cout << (6*n-1)*k ...

#数学 #整数分块 #思维 题意  定义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后一段定长的区间内  的值是固定的，但i是公差为1的等差数列 对于每一个块，分界总是  对每个块计算即可  代码 #include<bits/stdc++.h> using namespace std; long long g(long long n){ long long ans=0;...

题意 对于一个斐波那契序列，给定前两项，求解第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(){ long long a,b,n; cin >> a >> b >> n; cout << gcd(a,b) << endl; return 0; }

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

题意  q次询问，每次给一个x，问1到x的因数个数的和  思路  考虑每一个因子的贡献，对于因子p，有x/p对：p(1,2,3,……,n/p)。其中前p-1个是已经被枚举过的，p*p这对被计算了两次，所以每个因子的贡献是(x/p-p)*2+1枚举加和即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ int q; cin >> q; for(int i=1;i<=q;i++){ int x; cin >> x ; long long ans=0; for(int j=1;j*j...

贴一个大佬的题解 题意    求解x的个数，如果不存在输出0  思路  唯一分解定理+质因数分解 质因数分解：对于任何一个数n，对它质因数分解只需要枚举到  不断试除，如果最后剩余的不是1，那剩余的就是唯一的大于根号n的因子 对于一个质因子p，和公约数相关的会限制次数的下界，和公倍数相关的会限制次数的上界  如果a0和a1相同下界就是这个值，如果a0和a1不同次数就只能是a1 如果b0和b1相同上界是这个值，如果b0和b1不同次数就只能是b1   题目保证：cnta1<=cnta0，cntb0<=cntb1 最后判断即可  代码 #include<bits/stdc++.h&...

题意  m个操作，起始只有结点0，有如下三种操作  1 i——在结点i下开一个新点，序号为最大编号 2 i a——给结点i的子树全部加上a 3 i——查询结点i的值    思路  先把操作记录下来，建出树 对整颗子树的操作其实就是对dfn的一段区间操作，所以，所有的操作都可以在按dfn顺序的线段树上完成 遍历树得到dfn序以及每个结点的开始区间和结束区间 维护线段树即可 线段树本身记录的就是laz，每次开新点给对应的点清零就行  代码 #include<bits/stdc++.h> #define endl '\n' using namespace std; struct ty{ ...

二进制按位拆贡献看太久，最后一题爆搜没敢写  A 题意  给定k，输出两个非负整数使得异或和为k  思路  签到，0和k  代码 int main(){ int k; cin >> k; cout << 0 << ' ' << k << endl; return 0; }  B 题意  给定长为n的序列a，求相邻两个元素的异或和，获得长为n-1的序列b，求序列b的gcd  思路  直接模拟  代码 int a[30]; int b[30]; int main(){ int n; cin >> n; for(int i=0;...

好复杂的一个题  题意  n个结点，形成一棵根为1的树 k个帮派，每个帮派会控制一些结点 帮派可能结盟，单个帮派也可自己结盟，结盟后任意两个被控制的结点之间的路径都被联盟控制 Q次询问，每次询问给出首都V和结盟的帮派，只需要考虑结盟的帮派 每次询问回答首都V到最近的被控制的城市的距离  思路  对于结盟：任何两个点u,v结盟后所控制的点是lca(u,v)到u和v的路径上的所有点，多个点结盟就是lca(all_node)到每一个点的路径上的所有点 对于每次询问：共有分为三种情况，记LCA为询问中所有的控制点的lca  V不在LCA子树中，则V一定不被控制，此时dis就是V和LCA在树上的距离： ...