头像

福贵

安徽大学




离线:2小时前


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


福贵
3小时前

既然是队列那么先要包含头文件

#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. 高精度除法

福贵
3小时前
#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. 高精度减法

福贵
6小时前
#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. 高精度乘法

福贵
13小时前
#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;
}



福贵
13小时前

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



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

福贵
1天前
#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. 判断子序列

福贵
1天前
#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. 区间和

福贵
1天前

思想太美丽了

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



活动打卡代码 AcWing 803. 区间合并

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

using namespace std;
const int N=1e5+10;
int n;
int a[N];
struct Edge
{
    int a,b;
    bool operator<(const Edge &W)const
    {
        return a<W.a;
    }
}edge[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>edge[i].a>>edge[i].b;
    sort(edge+1,edge+n+1);
    int num=n,tem=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        if(edge[i].a<=tem)
        num--;
        tem=max(tem,edge[i].b);
    }
    cout<<num<<endl;
}




福贵
1天前

用double型全都要用double型
用double型除以2不能用>>1,只能/2
用double型二分法时,不能例如l=mid+1了,因为要考虑小数点
double型输出例子:printf(“%.6lf”,l);