头像

福贵

安徽大学




离线:12小时前


最近来访(140)
用户头像
StkOvflow
用户头像
爱算法爱生活
用户头像
zkc12345678910
用户头像
yxc的小迷妹
用户头像
将以有为也
用户头像
宇宙有边
用户头像
垫底抽風
用户头像
HfjNUlYZ
用户头像
cw_yzt
用户头像
StarLi9ht
用户头像
北海没有WA
用户头像
sealt
用户头像
不高兴的兽奶
用户头像
逆陽の葵
用户头像
weirdoZ
用户头像
需要时间
用户头像
hepanrong.
用户头像
废蛋
用户头像
江南诗诗
用户头像
种花家的虎式坦克

活动打卡代码 AcWing 838. 堆排序

福贵
13小时前

手写堆排序用数组实现堆结构
(也可直接用STL优先队列)
无标题.png
无标题2.png

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int n,m;
int h[N],cnt;

void down(int u)
{
    int t=u;
    if(u*2<=cnt&&h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cnt&&h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    cnt=n;//cnt记录总个数

    for(int i=n/2;i;i--) down(i);

    while(m--)
    {
        printf("%d ",h[1]);
        h[1]=h[cnt--];
        down(1);
    }

    puts("");//换行
    return 0;
}




福贵
14小时前

完全二叉树定义 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。




福贵
1天前

(就是STL里的堆排序)
既然是队列那么先要包含头文件

#include <queue>

他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的

和队列基本操作相同:


top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容


定义:

priority_queue<Type, Container, Functional>

Type 就是数据类型,Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆
一般是:

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)

————————————————
版权声明:本文为CSDN博主「吕白_」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_36888577/article/details/79937886



活动打卡代码 AcWing 794. 高精度除法

福贵
1天前
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

vector<int>div(vector<int>&A,int b,int &r)
{
    vector<int>C;
    r=0;
    for(int i=A.size()-1;i>=0;i--)
    {
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end());
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main()
{
    string a;
    vector<int>A;

    int B;
    cin>>a>>B;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');

    int r;
    auto C=div(A,B,r);

    for(int i=C.size()-1;i>=0;i--) cout<<C[i];

    cout<<endl<<r<<endl;
    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

福贵
1天前
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

bool cmp(vector<int>&A,vector<int>&B)
{
    if(A.size()!=B.size()) return A.size()>B.size();

    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
            return A[i]>B[i];

    return true;
}

vector<int> sub(vector<int>&A,vector<int>&B)
{
    vector<int>C;
    for(int i=0,t=0;i<A.size();i++)
    {
        t=A[i]-t;
        if(i<B.size()) t-=B[i];
        C.push_back((t+10)%10);
        if(t<0) t=1;//处理借位
        else t=0;
    }

    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

int main()
{
    string a,b;
    vector<int>A,B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');

    vector<int>C;
    if(cmp(A,B)) C=sub(A,B);
    else C=sub(B,A),cout<<'-';

    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;

    return 0;
}


活动打卡代码 AcWing 793. 高精度乘法

福贵
1天前
#include<iostream>
#include<vector>

using namespace std;

vector<int> mul(vector<int>&A,int b)
{
    vector<int>C;

    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        if(i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }

    while(C.size()>1&&C.back()==0) C.pop_back();//防止b=0
    return C;
}

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int>A;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//记得倒序分解string

    auto C=mul(A,b);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}



福贵
1天前

pop():删除栈顶(数组的尾部)的一个元素,并且返回它的值。
pop_back():删除栈顶(数组的尾部)的一个元素。
back():返回容器的最后一个元素的值。



活动打卡代码 AcWing 791. 高精度加法

福贵
2天前
#include<iostream>
#include<vector>

using namespace std;

vector<int> add(vector<int>&A,vector<int>&B)
{
    if(A.size()<B.size()) return add(B,A);

    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t) C.push_back(t);
    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');

    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    cout<<endl;
    return 0;
}



活动打卡代码 AcWing 2816. 判断子序列

福贵
2天前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=1e5+10;
int n,m;
int a[N],b[N];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];

    int ans=0;
    for(int i=0,j=0;j<m;j++)
    {
        if(a[i]==b[j])
        i++;
        if(i==n)
        {
            ans=1;
            break;
        }
    }
    if(ans==1) cout<<"Yes";
    else cout<<"No";

}


活动打卡代码 AcWing 802. 区间和

福贵
2天前

思想太美丽了

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int,int>PII;

const int N=300010;

int n,m;
int a[N],s[N];

vector<int>alls;
vector<PII>add,query;

int find(int x)
{
    int l=0,r=alls.size()-1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }

    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }

    //去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    //处理插入
    for(auto item:add)
    {
        int x=find(item.first);
        a[x]+=item.second;
    }

    //预处理前缀和
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];

    //处理询问
    for(auto item:query)
    {
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}