P2827——蚯蚓

八十分: 直接拿个堆维护一下,以 当前len+当前到最后的时间*q 排序即可,然后每次取出来的时候减去后面即可,因为这样可以保证你每次取出来的都是加过q的,而一直到末尾的原因是他们每一段时候加的都是一样的。而不能记一个时间,然后每次取出来的时候加,因为你有可能取出来的那个不是最大的。但如果我们每次加的话就会挂,所以先加到末尾,最后再减就不会有问题。 但是优先队列多个log啊,然后就疯狂乱t;

不加硬核优化只有75(逃

// luogu-judger-enable-o2
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define int long long
#define max maxx
#define min minn
using namespace std;
const int N=1e6+10;
template <class T> void in(T &x) {
    x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    if (f) x = -x;
}
inline int maxx(int x,int y) {
    return x>y?x:y;
}
inline int minn(int x,int y) {
    return x<y?x:y;
}
inline int gcd(int x,int y) {
    return !y?x:gcd(y,x%y);
}
int m,n,q,u,v,t,lennow,ans[10*N],cnt;
struct node {
    int len;
    int t;
    bool operator < (const node& b)const {
        return  len<b.len;
    }

} ew[8*N],t1,t2,x;
priority_queue<node> pq;
signed main() {
    in(n),in(m),in(q),in(u),in(v),in(t);
//  printf("%lf\n",p);
    for(ri i=1; i<=n; ++i)
        in(ew[i].len),ew[i].t=m-0,ew[i].len+=ew[i].t*q,pq.push(ew[i]);
    /*for(ri i=1;i<=n;++i)
        cout<<pq.top().len<<endl,pq.pop();*/
    for(ri i=1; i<=m; ++i) {
        x=pq.top();
        //puts(" ");
    //  printf("%d %d %d\n",i,x.len,x.t);
        lennow=x.len;
        lennow-=(m-i+1)*q;
        //printf("%d \n",lennow);
        if(i%t==0)
            cout<<lennow<<" ";
        pq.pop();
        t1.len=lennow*u/v,t1.t=m-i;
        t2.len=lennow-t1.len,t2.t=m-i;
        t1.len+=t1.t*q;
        t2.len+=t2.t*q;
        //printf("%d %d\n",t1.len,t1.t);
    //  printf("%d %d\n",t2.len,t2.t);
        pq.push(t1);
        pq.push(t2);
    }
    puts(" ");
    while(!pq.empty()) {
        cnt++;
        if(cnt%t==0)
            printf("%lld ",pq.top().len);
        pq.pop();
    }
    puts(" ");
    return 0;
}

100分: 留坑,代码来源: jzzcjb

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ri register int
#define max maxx
#define min minn
using namespace std;
const int N=1e7+10;
template <class T> void in(T &x) {
    x = 0;
    bool f = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while ('0' <= c && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    if (f) x = -x;
}
inline int maxx(int x,int y) {
    return x>y?x:y;
}
inline int minn(int x,int y) {
    return x<y?x:y;
}
inline int gcd(int x,int y) {
    return !y?x:gcd(y,x%y);
}
bool cmp(int a,int b) {
    return a>b;
}
int n,m,sum,S,u,v,T,q[N],q1[N],q2[N],h,h1,h2,t,t1,t2;
int find() {
    return (q[h]>max(q1[h1],q2[h2])&&(h<=t))?q[h++]:((q1[h1]>q2[h2])?q1[h1++]:q2[h2++]);
}
int main() {
    in(n),in(m),in(S),in(u),in(v),in(T); 
    double p=(double)u/v;
    t1=t2=0;
    t=n;
    h=h1=h2=1;
    for(ri i=1; i<=n; ++i) scanf("%d",&q[i]);
    sort(q+1,q+n+1,cmp);
    for(ri i=1; i<=m; ++i) {
        int x=find()+sum;
        sum+=S;
        int a1=p*(double)x,a2=x-a1;
        q1[++t1]=(a1-=sum),q2[++t2]=(a2-=sum);
        if(i%T==0)printf("%d ",x);
    }
    puts("");
    q1[t1+1]=q2[t2+1]=-0x3f3f3f3f;
    for(ri i=1,x=find(); i<=n+m; ++i,x=find())
        if(i%T==0)printf("%d ",x+sum);
    return 0;
}

发表于 2018-08-27 20:31:27 in 题目