首先建议对结点编号的修改使用位运算，因为位运算相较于常规运算要快一些。其次数组大小要开到8倍的n，因为虽然有n条线段，但是有2n个端点。 本题采用权值线段树求解，使用multiset来对左右端点排序和存储，使用set来对左右端点排序和去重，由于左右端点较大，还需要离散化一下再使用线段树。 查询每一种颜色时，需要把相同颜色的线段删掉，防止干扰判断，查完了以后再加回来就ok了 #include<iostream> #include<set> #include<map> #include<vector> using namespace std; mul...

这个题说实话有点难度。 dfs跑两次，或者bfs跑两次，一次是解决不了的。 第一次，找出入度为1，或入度大于等于2的点，打上标记，然后将没有访问到的点和他的出边一并删除，并标记为0。 第二次，再次遍历，将到某一点的标记沿着路径传递（第一步不会传递标记，比如当结点4标记为2时，他的下一个节点，假设为6，标记还是1，所以需要传递）。 然后常规拓扑排序，当遇到环以后，所有与环相关的点都无法被访问到，就标记为-1即可 最后遍历标记就ok了 #include<bits/stdc++.h> using namespace std; int n,m; const int M=4e5+5; vec...

#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<int> q; for(int i=1;i<=n;i++){ if(!ind[i]) q.push(i); } while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i<v[x].size();i++){ int p=v[x]...

本题暴力循环是使不得的，本人亲测。 首先分析得到，n个数进行gcd操作的结果就是最终的相同的数（自行举几个例子就可以得出这个结论）。 我们注意到转换的步骤有几次，i就和他后面几个数进行gcd操作，而操作次数一定是单调的，所以可以采用二分来优化。 二分出操作次数后，就进行区间查询的操作，在[i,i+mid]区间中进行查询，高效的静态区间查询的数据结构可以采用st表来处理，每次查询的复杂度是o（1），非常优秀。 查询每个区间是否与最终相同的数相同，如果不同，说明区间太小，无法gcd到相同的数，就l=mid+1。 #include<bits/stdc++.h> using namespa...

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); return max(st[l][k],st[r-(1<<k)+1][k]); } int main(){ int n,q; cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i]; st[i][0]=a[i]; } fo...

做这个题的时候超时了一次，因为遍历序列的时候用了两层for来处理每个位置的最小值，最差复杂度高达9* 10^10，已经不是2s能完成的了，计算机大概1s只能处理10^8/10^9次方的数据。 后来改用两个一层for循环，先从前向后，再从后向前遍历（顺序怎么样都行），然后就ok了，这样子的复杂度只有(3* 10^5)* 2,可以通过。 #include<bits/stdc++.h> using namespace std; const int M=3e5+5; int a[M]; typedef long long ll; ll tep[M]; int main(){ ios::sy...

考察位运算 #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; cin>>n; memset(huo,0,sizeof(huo)); for(int i=1;i<=n;i++){ cin>>a[i]; huo[i]=huo[i-1]|a[i]; ans[i]=huo[i]^a[i]; } for(int i=1;i<=n;i+...

这个题的原问题是，从1n有没有一个正确的序列划分，可以缩小为子问题，从1i有没有正确的序列划分，由于子问题和原问题的求解方式一样，且原问题需要由子问题推来，这就说明了这个题需要用动态规划来求解（不过蒟蒻一开始也没想到动态规划，还是太菜了）。 考虑递推方程怎么写，由于只用判断整体区间划分能否正确，所以设一个一维bool数组即可， bool f[i] 代表着以第i个位置为结尾的子区间能否被正确划分 递推的过程需要分类讨论，因为i可以是结尾，也可以是起始 1、当i为结尾时，那么就判断前i-a[i]-1长度的区间能否被正确划分，如果可以，那么前i长度的区间也能被正确划分，bool数组置true； 2、...

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

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

这道题要将序列分为一个或多个连续序列，且要求每个序列的和相等，找到可能成功划分的最小厚度。 因为要求每个序列的和相等，所以总数除以序列的值一定可以整除，所以就依据这个不断的枚举序列长度，并通过dfs进行验证，直到找到最符合题意的长度。 #include<bits/stdc++.h> using namespace std; const int M=2005; int a[M]; int sum; bool dfs(int n,int base,int pos,int &len){ int s=0; int length=0; for(int i=pos;i<=n;i+...

模板算法题 #include<bits/stdc++.h> using namespace std; const int M=5e5+5; char s[M<<1]; int p[M<<1]; int main(){ cin>>(s+1); int n=strlen(s+1); for(int i=2*n+1;i>=1;i--){ //初始化 s[i]=(i&1)? '#':s[i>>1]; } s[0]='^'; s[2*n+2]='$'; int c=0; int r=0; for(int i=1;i<=2*n...