头像

Live

The Number 6 Middle School


访客:7111

离线:28天前


活动打卡代码 AcWing 830. 单调栈

Live
3个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=1e6+10;

int s[N],a[N],k;
int t;


int main(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        while(k&&s[k]>=x)k--;
        if(k)cout<<s[k]<<" ";
        else cout<<"-1 ";
        s[++k]=x;
    }
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

Live
5个月前
#include<iostream>

using namespace std;

int v[1000010],w[1000010],a[1000010];

int n,V;

int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
        a[j]=max(a[j],a[j-v[i]]+w[i]);
    }cout<<a[V];
    return 0;
}


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

Live
5个月前
#include<iostream>

using namespace std;
int q[1000010];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    int x;
    while(m--){
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(q[l]!=x)printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]<=x)l=mid;
                else r=mid-1;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}


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

Live
5个月前
#include<iostream>

using namespace std;
int q[1000010];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    int x;
    while(m--){
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(q[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(q[l]!=x)printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(q[mid]<=x)l=mid;
                else r=mid-1;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}



Live
5个月前
#include<iostream>
using namespace std;
bool prime(int a)
{
    if(a<2)return false;
    for(int i=2;i<=a/i;i++)
        if(a%i==0)
        return false;
    return true;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        if(prime(x))printf("Yes\n");
        else printf("No\n");}
    return 0;
}


活动打卡代码 AcWing 872. 最大公约数

Live
5个月前
#include<iostream>

using namespace std;

int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    int x,y;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&x,&y);
        printf("%d\n",gcd(x,y));}
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

Live
5个月前
#include<iostream>
#include<cstdio>

using namespace std;
int q[100010],tmp[100010];
long long merge_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=l+r>>1;
    long long res=merge_sort(l,mid)+merge_sort(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{
            res+=mid-i+1;
            tmp[k++]=q[j++];
        }
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&q[i]);
    cout<<merge_sort(1,n);
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

Live
5个月前
#include<iostream>
#include<cstdio>

using namespace std;
int q[100010],tmp[100010];
long long merge_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=l+r>>1;
    long long res=merge_sort(l,mid)+merge_sort(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{
            res+=mid-i+1;
            tmp[k++]=q[j++];
        }
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&q[i]);
    cout<<merge_sort(1,n);
    return 0;
}


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

Live
5个月前
#include<iostream>
#include<cstdio>

using namespace std;
int q[1000010];
int tmp[100010];
void merge_sort(int l,int r)
{
    if(l>=r)return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(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(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(0,n-1);
    for(int i=0;i<n;i++)
    printf("%d ",q[i]);
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

Live
5个月前
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int a[1000010];
int sum;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    while(1)
    {
        int j=1;
        while(a[j]==0)
        j++;
        if(j==n)
        break;
        else{
            a[j]+=a[j+1];
            sum+=a[j];
            for(int i=j+1;i<n;i++)
            a[i]=a[i+1];
            n--;
        }
        for(int i=j;i<n;i++)
        if(a[i]>a[i+1])
        swap(a[i],a[i+1]);
    }
    printf("%d",sum);
    return 0;
}