/ Vijos / 题库 / 蚯蚓 /

题解

5 条题解

  • 1
    @ 2018-08-13 20:08:47
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const int maxn=100004,maxm=7000004;
    int n,m,q,u,v,t;
    int a[maxn],b[maxm],c[maxm];
    bool cmp(int x,int y){
        if(x>y) return true;
        return false;
    }
    int main(){
        //freopen("earthworm.in","r",stdin);
        //freopen("earthworm.out","w",stdout);
        scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
        double p=double(u*1.0/v);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1,cmp);
        int zc=0,l1=1,l2=1,r2=0,l3=1,r3=0;
        for(int i=1;i<=m;i++){
            int x=-999999999,y=-999999999,z=-999999999;
            if(l1<=n) x=a[l1];
            if(l2<=r2) y=b[l2];
            if(l3<=r3) z=c[l3];
            int w=max(x,max(y,z));
            if(w==x) l1++;
            else if(w==y) l2++;
            else l3++;
            x=w;
            x+=zc;
            int q1=floor(x*p*1.0);
            int q2=x-q1;
            q1-=zc;q2-=zc;
            q1-=q,q2-=q;
            b[++r2]=q1,c[++r3]=q2;
            if(i%t==0) printf("%d ",x);
            zc+=q;
        }
        printf("\n");
        for(int i=1;i<=n+m;i++){
            int x=-999999999,y=-999999999,z=-999999999;
            if(l1<=n) x=a[l1];
            if(l2<=r2) y=b[l2];
            if(l3<=r3) z=c[l3];
            int w=max(x,max(y,z));
            if(w==x) l1++;
            else if(w==y) l2++;
            else l3++;
            if(i%t==0) printf("%d ",w+zc);
        }
    }
    
  • 1
    @ 2017-04-16 17:57:17

    http://blog.csdn.net/jackypigpig/article/details/70196695

    洛谷上的评测需要卡卡常

    本质上是个单调队列,但是要是用自带的queue会超时,通过一些推理可以将其转化为普通的队列。
    具体可以看看我的博客 ^w^

    #include <cstdio>
    #include <algorithm>
    #define AA(x) (a[x]+(i-1)*q)
    #define BB(x) (b[x]+(i-1)*q)
    #define CC(x) (c[x]+(i-1)*q)
    #define Max(x,y,z) max(x,max(y,z))
    using namespace std;
    long long n,m,q,u,v,t,k,k1,k2;
    long long a[100005],b[7000005],c[7000005],A=1,B=1,C=1,rb,rc;
    bool cmp(int x,int y){return x>y;}
    
    long long Getk(int i){
        long long x1,x2,x3,xx;
        x1=x2=x3=-1;
        if (A<=n) x1=AA(A);
        if (B<=rb) x2=BB(B);
        if (C<=rc) x3=CC(C);
        xx=max(x1,max(x2,x3));
        if (xx==x1){A++; return x1;}
        if (xx==x2){B++; return x2;}
        else {C++; return x3;}
    }
    
    int main(){
        scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
        for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
        sort(a+1,a+n+1,cmp);
        for (int i=1; i<=m; i++){
            k=Getk(i);
            if (i%t==0) printf("%lld ",k);
            k1=k*u/v, k2=min(k1,k-k1), k1=k-k2;
            b[++rb]=k1-i*q;
            c[++rc]=k2-i*q;
        }
        printf("\n");
        for (int i=1; i<=n+m; i++){
            k=Getk(m+1);
            if (i%t==0) printf("%lld ",k);
        }
        return 0;
    }
    
  • 0
    @ 2017-06-08 13:05:32
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <limits>
    using namespace std;
    
    long long n,m,q,u,v,t;
    deque<long long> dq_1;
    deque<long long> dq_2;
    deque<long long> dq_3;
    
    void c_v_q_1()
    {
        dq_1.resize(0);
        dq_2.resize(0);
        dq_3.resize(0);
    }
    
    bool cmp_1(long long x,long long y)
    {
        return x>y;
    }
    
    void f_n_1(long long now_t,long long *now_l_p,long long *now_dq_p)
    {
        *now_l_p=(numeric_limits<long long>::min)(),*now_dq_p=0;
        if (dq_1.size()>0)
            if (*now_l_p<dq_1.front())
                *now_l_p=dq_1.front(),*now_dq_p=1;
        if (dq_2.size()>0)
            if (*now_l_p<dq_2.front())
                *now_l_p=dq_2.front(),*now_dq_p=2;
        if (dq_3.size()>0)
            if (*now_l_p<dq_3.front())
                *now_l_p=dq_3.front(),*now_dq_p=3;
        *now_l_p+=(now_t-1)*q;
    }
    
    void p_dq_b_1(long long now_dq)
    {
        if (now_dq==1)
            dq_1.pop_front();
        else if (now_dq==2)
            dq_2.pop_front();
        else if (now_dq==3)
            dq_3.pop_front();
    }
    
    int main()
    {
        while (~scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t))
        {
            c_v_q_1();
            dq_1.resize(n,0);
            for (long long i=0;i<n;i++)
                scanf("%lld",&dq_1[i]);
            sort(dq_1.begin(),dq_1.end(),cmp_1);
            for (long long i=1;i<=m;i++)
            {
                long long now_l,now_dq;
                f_n_1(i,&now_l,&now_dq);
                dq_2.push_back((now_l*u/v)-(i*q));
                dq_3.push_back(now_l-dq_2.back()-(2*i*q));
                p_dq_b_1(now_dq);
                if (i%t==0)
                    printf("%lld ",now_l);
            }
            printf("\n");
            for (long long i=1;i<=n+m;i++)
            {
                long long now_l,now_dq;
                f_n_1(m+1,&now_l,&now_dq);
                p_dq_b_1(now_dq);
                if (i%t==0)
                    printf("%lld ",now_l);
            }
            printf("\n");
        }
    }
    
    • @ 2017-06-08 13:06:16

      %lld打成%I64d害我错了5次

  • 0
    @ 2017-03-21 11:35:35

    单调队列233
    考场码错了QAQ
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<ctime>
    using namespace std;
    int my_comp(int a,int b)
    {
    if(a>b) return 1;
    return 0;
    }
    int d1[9*1000000],d2[9*1000000],d3[9*1000000];
    int main()
    {
    int n,m,q,u,v,t,i,j,t1,l1,l2,l3;

    //freopen("earthworm.in","r",stdin);
    //freopen("earthworm.ans","w",stdout);

    memset(d1,-128,sizeof(d1));
    memset(d2,-128,sizeof(d2));
    memset(d3,-128,sizeof(d3));

    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);

    l1=l2=l3=1;

    for(i=1;i<=n;i++)
    scanf("%d",&d1[i]);

    t1=t;

    sort(d1+1,d1+n+1,my_comp);

    for(i=1;i<=m;i++)
    {
    long long x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
    if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;}
    else
    {
    if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
    else {x1=d3[l3];l3++;}
    }

    long long a=(x1+=(i-1)*q)*u/v;

    d2[i]=a-i*q;
    d3[i]=x1-a-i*q;

    if(i%t==0) printf("%d ",x1);
    }

    printf("\n");

    for(i=1;i<=n+m;i++)
    {
    int x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
    if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;}
    else
    {
    if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
    else {x1=d3[l3];l3++;}
    }

    if(i%t==0) printf("%d ",x1+m*q);
    }

    //fclose(stdin);
    //fclose(stdout);

    return 0;
    }

  • -1
    @ 2017-05-26 16:08:50

    #include <bits/stdc++.h>
    using namespace std;
    priority_queue<int>q1;
    queue<int>q2,q3;
    int n,m,q,u,v,t;
    int maxlen(int t){
    int x1=-1,x2=-1,x3=-1;
    if(!q1.empty())x1=q1.top()+t*q;
    if(!q2.empty())x2=q2.front()+t*q;
    if(!q3.empty())x3=q3.front()+t*q;
    if(x1>=x2&&x1>=x3){q1.pop();return x1;}
    else if(x2>=x1&&x2>=x3){q2.pop();return x2;}
    else{q3.pop();return x3;}
    }
    int main(int argc,char** argv){
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;i++){int len;cin>>len;q1.push(len);}
    for(int i=1;i<=m;i++){
    long t1,t2,len=maxlen(i-1);
    t1=len*u/v;t2=len-t1;
    q2.push(t1-i*q);q3.push(t2-i*q);
    if(i%t==0)cout<<len<<" ";

    }cout<<endl;
    for(int i=1;i<=m+n;i++){
    int len=maxlen(m);
    if(i%t==0)cout<<len<<" ";
    }return 0;
    }

  • 1

信息

ID
2007
难度
7
分类
(无)
标签
递交数
1555
已通过
308
通过率
20%
被复制
3
上传者