2019.10.25 csp-s模拟测试87 反思总结

一次非常神奇的考试，考完试以后看着T2的0pts突然笑死我自己

太智障了这什么神奇的题意理解错误23333

T1一眼分类讨论，两眼二分，觉得分类讨论有点玄学但是出题人八成不会卡【何】，然后本着对二分的恐惧打了玄学

关于T2，我没了豹笑我没想到一只鸟可能被打两枪你敢信

T3？今天有T3？

T1：

正解是显而易见的二分。然而我比较懒，又经常在二分上炸掉【写得比较丑】，而且第一眼其实并不是二分。

如果k最后小于1，那么相对于原来1个单位时间的移动来说，肯定这种上下移动的步数越多越好。先dfs一次，跑出从起点到终点上下移动步数最多的最短路，然后计算出对应的k。如果这个k解出来大于1，就再跑一次使左右移动步数最多的最短路，再次解出k。这样可以保证选取这个k的同时，跑的一定是最短路。

其实总是隐约不太放心，感觉可能有锅XD然而最后A了

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int n,m,sx,sy,tx,ty;

int a[][],vis[][];

int h[]={,-,,};

int l[]={-,,,};

double s;

struct node{

    int x,y,tmp,dis;

    bool operator < (const node a) const {

        return tmp < a.tmp;

    }

};

priority_queue<pair<int,node> >q;

node dfs1(){

    node u;

    u.x=sx,u.y=sy,u.tmp=;

    q.push(make_pair(,u));

    while(!q.empty()){

        while(q.size()&&vis[q.top().second.x][q.top().second.y])q.pop();

        if(!q.size())break;

        int d=-q.top().first;

        node x=q.top().second;

        q.pop();

        vis[x.x][x.y]=;

        if(x.x==tx&&x.y==ty){

            x.dis=d;

            return x;

        }

        for(int i=;i<;i++){

            node y=x;

            y.x+=h[i],y.y+=l[i];

            if(y.x>&&y.x<=n&&y.y>&&y.y<=m&&!a[y.x][y.y]){

                if(i==||i==)y.tmp++;

                q.push(make_pair(-(d+),y));

            }

        }

    }

}

node dfs2(){

    node u;

    u.x=sx,u.y=sy,u.tmp=;

    while(!q.empty())q.pop();

    memset(vis,,sizeof(vis));

    q.push(make_pair(,u));

    while(!q.empty()){

        while(q.size()&&vis[q.top().second.x][q.top().second.y])q.pop();

        if(!q.size())break;

        int d=-q.top().first;

        node x=q.top().second;

        q.pop();

        vis[x.x][x.y]=;

        if(x.x==tx&&x.y==ty){

            x.dis=d;

            return x;

        }

        for(int i=;i<;i++){

            node y=x;

            y.x+=h[i],y.y+=l[i];

            if(y.x>&&y.x<=n&&y.y>&&y.y<=m&&!a[y.x][y.y]){

                if(i==||i==)y.tmp++;

                q.push(make_pair(-(d+),y));

            }

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            scanf("%d",&a[i][j]);

        }

    }

    scanf("%lf",&s);

    node b=dfs1();

    double k=(1.0*s-1.0*b.dis+1.0*b.tmp)/(1.0*b.tmp);//tmp上下，dis-tmp左右

    if(k<)printf("%.3lf",k);

    else{

        b=dfs2();

        k=(1.0*s-1.0*b.tmp)/(1.0*(b.dis-b.tmp));//tmp左右，dis-tmp上下

        printf("%.3lf",k);

    }

    return ;

}

T2：

什么？一只鸟有可能被打两次……？是你R光速换弹还是我鲲化而为鹏……？

咳咳，不是不是，其实真的挺智障的，居然没想到一只鸟所占的区间可能会长于换弹时间…老实说，考试的时候还是不太认真XD

发现一只鸟可能被打两次以后，就要考虑重复的问题。把区间排序以后扔进队列可以解决当前时间的区间覆盖数目。

然后要从0~i-k选出一个去掉重复个数的f[j]进行转移。选取最大的f值以及对重复个数的修改都可以利用线段树完成。线段树以时间为下标，储存f[i]-（同时覆盖i与当前时间的区间个数）。维护方式是，根据前面的队列，当有新的区间的l覆盖了当前时间而入队时，使得l到r这一段区间-1，含义是这一段对于当前时间多了一个重复区间。而一段队列里的区间的r小于当前时间出队时，再把对应的l到r这一段+1，这一个区间不再重复了。

从0扫到max，max是最大的r。ans即为最大的（根据当前时间i查询的线段树中0->i-k中最大值+当前时间点的区间覆盖数量【队列size】）。

要注意各处l或r小于0的区间的处理。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

int n,k,top=,ans,sum,maxx;

struct node{

    int l,r;

    bool operator < (const node x)const{

        return l==x.l?r<x.r:l<x.l;

    }

}a[];

priority_queue<pair<int,node> >q;

struct tree{

    int l,r,maxx,tag;

}b[*];

void pushdown(int p){

    if(b[p].tag){

        b[p*].tag+=b[p].tag;

        b[p*].maxx+=b[p].tag;

        b[p*+].tag+=b[p].tag;

        b[p*+].maxx+=b[p].tag;

        b[p].tag=;

    }

}

void pushup(int p){

    b[p].maxx=max(b[p*].maxx,b[p*+].maxx);

}

void build(int p,int l,int r){

    b[p].l=l,b[p].r=r;

    b[p].maxx=b[p].tag=;

    if(l==r)return;

    int mid=(l+r)/;

    build(p*,l,mid);

    build(p*+,mid+,r);

}

void change(int p,int l,int r,int y){

    if(l<=b[p].l&&b[p].r<=r){

        b[p].maxx+=y;

        b[p].tag+=y;

        return;

    }

    pushdown(p);

    int mid=(b[p].l+b[p].r)/;

    if(l<=mid)change(p*,l,r,y);

    if(r>mid)change(p*+,l,r,y);

    pushup(p);

}

void update(int p,int l,int r,int y){

    if(l<=b[p].l&&b[p].r<=r){

        b[p].maxx=y;

        b[p].tag=;

        return;

    }

    pushdown(p);

    int mid=(b[p].l+b[p].r)/;

    if(l<=mid)update(p*,l,r,y);

    if(r>mid)update(p*+,l,r,y);

    pushup(p);

}

int ask(int p,int l,int r){

    if(l<=b[p].l&&b[p].r<=r){

        return b[p].maxx;

    }

    pushdown(p);

    int mid=(b[p].l+b[p].r)/;

    int val=;

    if(l<=mid)val=max(val,ask(p*,l,r));

    if(r>mid)val=max(val,ask(p*+,l,r));

    pushup(p);

    return val;

}

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){

        scanf("%d%d",&a[i].l,&a[i].r);

        maxx=max(maxx,a[i].r);

    }

    sort(a+,a+n+);

    build(,,maxx);

    for(int i=;i<=maxx;i++){

        while(a[top].l<=i&&top<=n){

            if(a[top].r<){

                top++;

                continue;

            }

            q.push(make_pair(-a[top].r,a[top]));

            change(,max(,a[top].l),a[top].r,-);

            top++;

        }

        while(q.top().second.r<i&&q.size()){

            change(,max(,q.top().second.l),q.top().second.r,+);

            q.pop();

        }

        if(i>=k)sum=ask(,,i-k);

        update(,i,i,sum);

        ans=max(ans,sum+(int)q.size());

    }

    printf("%d\n",ans);

    return ;

}

蠢出一定程度了…线段树写错+队列没考虑l的入队顺序不一定是r的出队顺序于是没写优先队列…改了挺长时间的

T3：

咕咕咕咕咕咕咕咕【飞了】

今天发现各处弥漫着稍许颓废的气息

可能是秋天到了吧【何】

巴特西

2019.10.25 csp-s模拟测试87 反思总结

最新文章

热门文章