头像

破茧٩๑o๑۶幻化成蝶




离线:2天前


最近来访(0)


790.数的三次方根

C++ 代码

/*
  浮点数二分法
*/

#include<iostream>
using namespace std;

double n;
int main(){
    cin>>n;
    double l=-100,r=100;//这里的区间注意设置成负一百到正一百,配合n的取值范围
    double mid;
    while(r-l>1e-8){
        mid = (l+r)/2;
        if(mid*mid*mid<n){
            l=mid;
        }else{
            r=mid;
        }
    }
    printf("%lf",mid);
    return 0;
}



AcWing 789数的范围,整数二分法,个人记录

/*二分法一定是有解的*/
/*
    重要的是二分法模板,自己需要确定区间
*/
#include <iostream>
using namespace std;

const int N=1e6+10;
int q[N];
int n;
void bsearch(int x,int l, int r){
  //  cout<<x;
    while(l<r){//循环判定条件是l<r
        int mid = (l+r)>>1;
        if(q[mid]>=x){//这里是mid
            r=mid;

        }else{
            l=mid+1;
        }
    }
    //cout<<"q[l]== "<<q[l]<<endl;
    if(q[l]!=x){
        cout<<"-1 -1"<<endl;

    }else{
        cout<<l<<" ";
        l=0,r=n-1;
        while(l<r){
            int mid = (l+r+1)>>1;
            if(q[mid]<=x){
                l=mid;

            }else
            {
                r=mid-1;
            }

        }

        cout<<l<<endl;
    }
}
int main(){
    cin>>n;
    int k; cin>>k;
    for (int i=0;i<n;i++){
        scanf("%d",&q[i]);
    }
    int x;
    for(int i=0;i<k;i++){

        cin>>x;
        bsearch(x,0,n-1);
    }

    return 0;
}


活动打卡代码 AcWing 797. 差分



----------

`//前缀和和差分注意从1开始
//s[n],a[n]设全局变量
/*#include<iostream>
using namespace std;

const int N=1e5+10;
int s[N],a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);//原数组
        a[i]=s[i]-s[i-1];//差分之后的数组
    }
    while(m--)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        a[l]=a[l]+c;
        a[r+1]-=c;
    }
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+a[i];
        cout<<s[i]<<" ";
    }
    return 0;
}*/`

----------

`


y总代码


#include<iostream>
using namespace std;

const int N=1e5+10;
int a[N],b[N];
void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        cout<<b[i]<<' ';
    }

}`


活动打卡代码 AcWing 796. 子矩阵的和



 //个人认为这题的重点应该是s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];这行代码与
//cout<<s[x2][y2]+s[x1-1][y1-1]-s[x2][y1-1]-s[x1-1][y2]<<endl;这行代码的输出,这里不要简单的想成-s[x1][y1],
//(x1,y1)的值是包含在输出重点的所以所有x1换成x1-1,所有的y1换成y1-1;


#include<iostream>
using namespace std;

const int N=1010;
int n,m,q;
int a[N][N],s[N][N];

int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(i==1)
            {
                s[i][j]=a[i][j]+s[i][j-1];
            }
            else if(j==1)
            {
                s[i][j]=a[i][j]+s[i-1][j];
            }
            else
            s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];//这里用不用+=都可以通过
        }
    }
    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]+s[x1-1][y1-1]-s[x2][y1-1]-s[x1-1][y2]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include<iostream>
using namespace std;
const int N=1e5+10;
int s[N];
int n,q,k;

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d",&s[i]);
    while(q--)
    {
        scanf("%d",&k);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r >> 1;

            if(s[mid]>=k) r=mid;//大于号,小于号不要搞错
            else l=mid+1;
        }
        if(s[l]!=k) cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<" ";
            int l=0,r=n-1;//这里的一行不能丢
            while(l<r)
            {
                int mid=l+r+1 >>1;
                if(s[mid]<=k) l=mid;
                else r=mid-1;
            }cout<<l<<endl;
        }

    }
    return 0;
}


活动打卡代码 AcWing 787. 归并排序


/*#include<iostream>
using namespace std;
const int N=1e6+10;

long long q[N],tmp[N];
void merge_sort(long long q[],int l ,int r)
{
    if(l>=r) return ;
    //确定分界点
    int mid=l+r>>1;
    //递归
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);

    int i=l,j=mid+1,k=0;
    //合二为一
    while(i<=mid&&j<=r)
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];

    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main()
{
    int n;scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", &q[i]);
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ", q[i]);
    return 0;
}*/


#include<iostream>
using namespace std;
const int N=1e5+10;
long long q[N],tmp[N];

void merge_sort(long long q[],int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main()
{
    int n; scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",q[i]);
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include[HTML_REMOVED]

using namespace std;

int n,k;
const int N=1e5+10;
int q[N];

int quick_sort(int l,int r,int k)
{
if(l>=r) return q[l];
int i=l-1,j=r+1,x=q[l+r>>1];
while(i[HTML_REMOVED]x);
if(i[HTML_REMOVED]>n>>k;
for(int i=0;i<n;i++) scanf(“%d”,&q[i]);
cout<<quick_sort(0,n-1,k);
return 0;
}