#递归 题意  n层汉诺塔，从a柱移到c柱，每次移动只能向相邻的移动，求解所需要的步数  思路  设计递归函数：对于当前这一片，把它从a移动到c需要先把它上面的移动到c，然后再把它移动到b，再把c上的所有移动到a，再把自己移动到c，然后移过来 其中只有移动自己的部分需要记录步数 观察发现  代码 #include<bits/stdc++.h> using namespace std; int cnt; void han(int n,int f,int t){ if(n==0) return ; han(n-1,0,2); cnt++; han(n-1,2,0); cnt++; ha...

#前缀和 #二维前缀和  PS:太久没写二维前缀和，有点忘了，写一个  题意  5000*5000的网格，有n个目标，每个目标具有价值 可以消除r*r个点，并获得所有消除的点的价值，求能获得的最大价值  思路  直接维护二维前缀和然后求答案就行 二维前缀和的维护是a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]  代码 #include<bits/stdc++.h> using namespace std; int a[5050][5050]; int sum[5050][5050]; int main(){ int n,r; cin ...

#枚举 #位运算 #贪心 题意  n行m列矩阵(1<=n,m<=15)，k次操作，每次消除一行or一列，将答案加上消除的值 求解最大答案  思路  对于只消除行和列，一定是消除行和和列和最高的k个 行和列同时选的时候，贪心的依次选最高行和列不能保证答案最优  选两次 9 10 1 1 1 1 1 20 9   所以既然混着选没法确定，那就枚举行的所有选法，然后再行确定的时候堆列进行贪心，用一个n位2进制表示行的选法，然后每次剔除所选行的元素计算每列的和  代码 #include<bits/stdc++.h> #define int long long using nam...

#离线 #广度优先搜索 #构造 #优先队列bfs A 题意  求a/r上取整  思路  小技巧，求上取整   代码 void solve(){ int a,l,r; cin >> a >> l >> r; cout << (a+r-1)/r << endl; }  B 题意  双排列序列，相同的两个数的最远距离  思路  开一个桶记录记录位置，同时更新答案 直接模拟  代码 void solve(){ int n; cin >> n; vector<int> a(n+10); int ans=0; for(in...

#单调栈 #构造 #贪心  单调栈过于久远，忘了  A 题意  用1*2和2*1的砖块填充3*n的矩形，判断能不能填充满  思路  签到，偶数可以，奇数不行  代码 void solve(){ int n; cin >> n; if(n%2) cout << "NO" << endl; else cout << "YES" << endl; }  B 题意  给定x，最多进行k次操作，判断能不能使得操作后变为回文串 记y为x翻转并去除前导0，每次操作x=x+y  思路  直接模拟  代码 bool check(string s){ f...

#妙妙题 #二分 #dfn #lca 题意  给定一个无根树，每个结点有自己的颜色，处理两种操作  求颜色x的生成树的大小 将结点x的颜色改为y    思路  对于某一种颜色  如果只有一个点，生成树大小是0 如果有两个点，生成树大小是这两个点的距离 如果在此基础上再加入新的点，会有两种情况  一种是新点x加入的位置两旁有其它点u,v，这时候新点加入的贡献是  而另一种是新点x加入的位置位于最左侧或者最右侧，此时任取两个点计算代价都是一样的，代价仍然是    最终发现这个公式在两个点的时候也成立，那么对每一个结点维护一个set，然后二分找最近的两个点，如果二分没有结果就用任意两个点，每次添加和...

#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; }