1供水管线（钻石；并查集+最小生成树）
时间限制：1秒
占用内存：128M
题目思路
该题目就是最小生成树的问题。我们使用选边的方法，每次选取最小边加入，用并查集检查是否已联通，如果已联通又加入该边就会产生环，是错误的，详见代码。
【码蹄集进阶塔全题解13】数据结构：并查集/线段树/树状数组 MT2137 – MT2143_哔哩哔哩_bilibili
代码
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int i,j,c;
bool operator<(const edge &t) const {return c<t.c;}
}p[200];
int n,k,par[200];
int find(int x)
{
if(x==par[x]) return x;
return par[x]=find(par[x]);
}
bool merge(int i,int j)
{
int x=find(i),y=find(j);
if(x!=y) par[x]=y;
else return false;
return true;
}
int main( )
{
cin>>n>>k;
for(int i=1;i<=n;i++) par[i]=i;
int x,y,c,ans=0;
for(int i=1;i<=k;i++) cin>>p[i].i>>p[i].j>>p[i].c;
sort(p+1,p+1+k);
for(int i=1;i<=k;i++)
{
bool ok=merge(p[i].i,p[i].j);//使用并查集判断连通性
if(ok==true) ans+=p[i].c;
}
cout<<ans;
return 0;
}2逆序（钻石；树状数组）
时间限制：1秒
占用内存：128M
题目思路
record：一个数是record就意味着他前边的数都比他小
树状数组可以求前边有多少个数比我小
【码蹄集进阶塔全题解13】数据结构：并查集/线段树/树状数组 MT2137 – MT2143_哔哩哔哩_bilibili
“树状数组”知识点补充
简介
树状数组，就是一个结构为树形结构的数组，不同于二叉树的结构，它在二叉树的结构上删除了一些中间节点：
二叉树：
树状数组：
应用场景
可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强；树状数组的作用就是为了简化线段树。
详细讲解
前置知识—lowbit(x)运算
如何计算一个非负整数n在二进制下的最低为1及其后面的0构成的数？ 例如：44 = (101100) 2,最低为1和后面的0构成的数是 (100) 2 = 4 所以 lowbit (44) = lowbit((101100)2) = (100)2 = 4,那么lowbit运算时怎么实现的呢？
44的二进制=(101100)，我们对44的二进制数取反+1(也就是44的二进制补码)，也即~44+1,得到-44
-44的二进制=(010100)，然后我们把44和-44的二进制进行按位与运算，也即按位&得到,二进制000100，也就是十进制的4
所以lowbit(x) = x&(-x)
1问题引入
2接下来分析树状数组原理
上面是树状数组的结构图，t[x]保存以x为根的子树中叶子节点值的和,原数组为a[]，那么原数组前4项的和t[4]=t[2]+t[3]+a[4]=t[1]+a[2]+t[3]+a[4]=a[1]+a[2]+a[3]+a[4]
观察节点的二进制数，可以发现，树状数组中节点x的父节点为x+lowbit(x),例如t[2]的父节点为t[4]=t[2+lowbit(2)]
3单点修改，区间查询
所以在进行单点修改的同时，更新父节点就变得非常简单，例如我们对a[1]+k，那么祖先节点t[1],t[2],t[4],t[8]都需要+k更新(因为t[]表示前缀和)，此时我们就可以用lowbit操作实现.
int add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=k;
}单点修改实现了，如何实现区间查询呢？ 例如：我们需要查询前7项的区间和sum[7]
通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的-lowbit操作来实现求和
int ask(x){
int sum = 0;
for(int i=x;i;i-=lowbit(i)){
sum+=t[i];
}
return sum;
}这只能求区间[1,x]的区间和，那么如何求[L,R]的区间和呢？ 这时候利用前缀和相减的性质就可以了[L,R]=[1,R]−[1,L−1]
int search(int L,int R)
{
int ans = 0;
for(int i=L-1;i;i-=lowbit(i))
ans-=c[i];
for(int i=R;i;i-=lowbit(i))
ans+=c[i];
return 0;
}（摘自：树状数组(详细分析+应用)，看不懂打死我!-CSDN博客）
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,c[N],chg[N];//chg[x]=y表示将x删掉后record会增加y个，那么chg数组中的最大值就是我们要的结果
int lowbit(int x) {return x & -x;}
void add(int x)
{
for(;x<N;x+=lowbit(x)) c[x]++;
}
int sum(int x)
{
int ret=0;
for(;x>0;x-=lowbit(x)) ret+=c[x];
return ret;
}
int main( )
{
cin>>n;
int x=0,maxm=0;
for(int i=1;i<=n;i++)
{
cin>>x;
maxm=max(maxm,x);
int cnt=sum(x);//计算前边有多少个数比X小
if(cnt==i-1) chg[maxm]--;//对第i个数来说，前边有i-1个数比我小，满足record；那么如果把我删掉，反而少了一个record，就要减一
else if(cnt==i-2) chg[maxm]++;//这说明前边有1个数比我大，如果把那个数删掉，就能多一个record
//只用考虑这两种情况，因为i-3的情况下，删除一个就也无法变成record，无能为力了，往后亦是如此
add(x);
}
int ans=1;
for(int i=1;i<=n;i++)
{
if(chg[i]>chg[ans]) ans=i;
}
cout<<ans;
return 0;
}3线段树（钻石；线段树）
时间限制：1秒
占用内存：128M
题目思路
线段树模板题
【码蹄集进阶塔全题解13】数据结构：并查集/线段树/树状数组 MT2137 – MT2143_哔哩哔哩_bilibili
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long
struct node
{
int l,r,val,lz;//lz是懒标记
}tree[4*N];
int a[N];
void build(int p,int l,int r)
{
tree[p].l=l,tree[p].r=r;
if(l==r)
{
tree[p].val=a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].val=tree[p*2].val+tree[p*2+1].val;
}
void lazy(int p,int v)
{
int s=tree[p].l,t=tree[p].r;
tree[p].val+=(t-s+1)*v,tree[p].lz+=v;
}
void pushdown(int p)
{
lazy(2*p,tree[p].lz);
lazy(2*p+1,tree[p].lz);
tree[p].lz=0;
}
//带懒标记区间修改,[l,r]
//为修改区间，p为当前节点编号，c为区间节点变化值，求和非求最值
void update(int l,int r,int c,int p)
{
int s=tree[p].l,t=tree[p].r;
if(l<=s&&t<=r) return lazy(p,c);
if(tree[p].lz&&s!=t) pushdown(p);
int mid=(s+t)/2;
if(l<=mid) update(l,r,c,p*2);
if(r>mid) update(l,r,c,p*2+1);
tree[p].val=tree[p*2].val+tree[p*2+1].val;
}
//带懒标记区间查询（区间求和）,[l,r]为修改区间，p为当前节点编号
int query(int l,int r,int p)
{
int s=tree[p].l,t=tree[p].r;
if(l<=s&&t<=r) return tree[p].val;
if(tree[p].lz) pushdown(p);
int mid=(s+t)/2,sum=0;
if(l<=mid) sum=query(l,r,p*2);
if(r>mid) sum+=query(l,r,p*2+1);
return sum;
}
signed main( )
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--)
{
int op,x,y,k;
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
update(x,y,k,1);
}
else
{
cin>>x>>y;
cout<<query(x,y,1)<<endl;
}
}
return 0;
}4快排变形（黄金；树状数组）
时间限制：1秒
占用内存：128M
题目思路
树状数组经典应用：求逆序对个数，使用归并排序
【码蹄集进阶塔全题解13】数据结构：并查集/线段树/树状数组 MT2137 – MT2143_哔哩哔哩_bilibili
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N],b[N],c[N];
long long ans;
int lowbit(int x) {return x & -x;}
void add(int i,int x)
{
for(;i<=n;i+=lowbit(i)) c[i]+=x;
}
int sum(int i)
{
int ans=0;
for(;i>0;i-=lowbit(i)) ans+=c[i];
return ans;
}
bool cmp(const int x,const int y)
{
if(b[x]==b[y]) return x>y;
return b[x]>b[y];
}
int main( )
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>b[i];
a[i]=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
add(a[i],1);
ans+=sum(a[i]-1);
}
cout<<ans;
return 0;
}5上楼梯（黄金；线性DP）
时间限制：1秒
占用内存：128M
题目思路
经典DP题，这道题目无需考虑层级之间的问题，直接使用动态转移方程：dp[n]=dp[n-1]+dp[n-2]即可，dp数组中存放到达第n层共有多少种方案。
【码蹄集进阶塔全题解14】动态规划：MT2144 – MT2150_哔哩哔哩_bilibili
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[100];//注意，int会报错
int main( )
{
cin>>m>>n;
int total=(n-1)*m;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=total;i++) dp[i]=dp[i-1]+dp[i-2];
cout<<dp[total];
return 0;
}6上楼梯2（黄金；线性DP）
时间限制：1秒
占用内存：128M
题目思路
状态转移方程：dp[n]=dp[n-1]+dp[n-2]+……+dp[n-k]
【码蹄集进阶塔全题解14】动态规划：MT2144 – MT2150_哔哩哔哩_bilibili
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k;
long long dp[N];
int main( )
{
cin>>n>>k;
dp[0]=dp[1]=1;
for(int i=2;i<=k;i++)
{
for(int j=1;j<=i;j++) dp[i]=(dp[i]+dp[i-j])%114584;
}
for(int i=k+1;i<=n;i++)
{
for(int j=1;j<=k;j++) dp[i]=(dp[i]+dp[i-j])%114584;
}
cout<<dp[n];
return 0;
}⭐创作不易，点个赞吧~
⭐点赞收藏不迷路~
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 码蹄集部分题目（2024OJ赛7.17-7.21；并查集+最小生成树+线段树+树状数组+DP）
发表评论 取消回复