LXNHB

题解

c++基础(2) 三分法(1) 二分法(2) 操作系统(7) 算法(2)

/ 注册

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

题解|#F. Multi-Colored Segments# CF 来自专栏

首先建议对结点编号的修改使用位运算，因为位运算相较于常规运算要快一些。其次数组大小要开到8倍的n，因为虽然有n条线段，但是有2n个端点。本题采用权值线段树求解，使用multiset来对左右端点排序和存储，使用set来对左右端点排序和去重，由于左右端点较大，还需要离散化一下再使用线段树。查询每一种...

C++ 数据结构线段树 multiset set

2023-12-17

0 243

题解|#G. How Many Paths?# cf 来自专栏

这个题说实话有点难度。 dfs跑两次，或者bfs跑两次，一次是解决不了的。第一次，找出入度为1，或入度大于等于2的点，打上标记，然后将没有访问到的点和他的出边一并删除，并标记为0。第二次，再次遍历，将到某一点的标记沿着路径传递（第一步不会传递标记，比如当结点4标记为2时，他的下一个节点，假设为6...

C++ 图论拓扑排序

2023-12-16

0 275

题解|#走多远# lanqiao 拓扑排序模板来自专栏

#include<bits/stdc++.h> using namespace std; const int M=1e6+5; vector<int> v[M]; int ind[M]; int dp[M]; int n,m; void topo(){ queue<...

C++ 拓扑排序

2023-12-16

0 231

题解|#F. Array Stabilization (GCD version)# cf 来自专栏

本题暴力循环是使不得的，本人亲测。首先分析得到，n个数进行gcd操作的结果就是最终的相同的数（自行举几个例子就可以得出这个结论）。我们注意到转换的步骤有几次，i就和他后面几个数进行gcd操作，而操作次数一定是单调的，所以可以采用二分来优化。二分出操作次数后，就进行区间查询的操作，在[i,i+m...

C++ 动态规划 st表倍增

2023-12-15

0 300

题解|#区间最大值# 蓝桥来自专栏

st表模板题 #include<bits/stdc++.h> using namespace std; const int M=5e5+5; int a[M]; int st[M][21]; int getMax(int l,int r){ int k=log2(r-l+1); ...

C++ 动态规划 st表倍增

2023-12-15

0 258

题解|#E. Air Conditioners# cf 来自专栏

做这个题的时候超时了一次，因为遍历序列的时候用了两层for来处理每个位置的最小值，最差复杂度高达9* 10^10，已经不是2s能完成的了，计算机大概1s只能处理10^8/10^9次方的数据。后来改用两个一层for循环，先从前向后，再从后向前遍历（顺序怎么样都行），然后就ok了，这样子的复杂度只有(...

C++ 模拟

2023-12-15

0 264

题解|#D. Co-growing Sequence# cf 来自专栏

考察位运算 #include<bits/stdc++.h> using namespace std; const int M=2e5+5; typedef long long ll; ll a[M]; ll huo[M]; ll ans[M]; void solve(){ int n;...

C++ 位运算

2023-12-15

0 227

题解|#E. Sending a Sequence Over the Network# cf round 826 来自专栏

这个题的原问题是，从1n有没有一个正确的序列划分，可以缩小为子问题，从1i有没有正确的序列划分，由于子问题和原问题的求解方式一样，且原问题需要由子问题推来，这就说明了这个题需要用动态规划来求解（不过蒟蒻一开始也没想到动态规划，还是太菜了）。考虑递推方程怎么写，由于只用判断整体区间划分能否正确，所以...

C++ 动态规划

2023-12-15

0 247

题解|#D. Masha and a Beautiful Tree# codeforces round 826 来自专栏

就是归并排序的变形，主要还是反映了一个大问题可以分成每个独立的子问题进行求解的分治思想，整体并不难。 #include<bits/stdc++.h> using namespace std; const int M=262148; int p[M]; int b[M]; int cnt;...

C++ 分治

2023-12-15

0 362

题解|#D. Masha and a Beautiful Tree# codeforces round 826 来自专栏

就是归并排序的变形，主要还是反映了一个大问题可以分成每个独立的子问题进行求解的分治思想，整体并不难。 #include<bits/stdc++.h> using namespace std; const int M=262148; int p[M]; int b[M]; int cnt;...

C++ 分治

2023-12-14

0 272