/ Vijos / 题库 / 蚯蚓 /

# 5 条题解

• @ 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);
}
}
``````
• @ 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;
}
``````
• @ 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次

• @ 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;
}

• @ 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

(无)

1578

317

20%

7