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

⭐创作不易,点个赞吧~

⭐点赞收藏不迷路~

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部