ARC-082F Sandglass

题意

有一个含有两个玻璃球的沙漏，分别称这两个玻璃球为\(\)和\(\)，沙漏中有一些沙子，当\(\)放在上面时，\(\)就在下面，而\(\)在上面时\(\)就在下面。
沙子总是以\(1\)克每秒的速度从上面的玻璃球漏到下面的玻璃球，直到当上面的玻璃球没有沙子。
初始时刻是0时刻，此时，\(\)在上面，\(\)在下面，且\(\)中有\(\)克沙子，\(\)中有\( − \)克沙子（沙漏中总共有克沙子）。
沙漏会在\(_1,_2,…,_\)这些时刻反转，我们假设反转是瞬间完成的。
有个询问，每个询问形如\((_,_)\)，表示询问当\( = _\)的情况下\(_\)时刻\(\)中的沙子数。
【数据范围】保证\(1 ≤ ,_,_ ≤ 109，1 ≤ , ≤ 10^5，0 ≤ _ ≤ \)

做法

显然某一时刻，初始时的\(a\)作为定义域，沙子数量作为值域，是一个分段函数：平，斜率为\(1/-1\)，平

维护每个关键点\(t_i\)的函数图象即可

题外话

国集题解讲得好抽象啊...

code

没去写了，贴一份这里的代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fo(i,l,r) for(int i=l;i<=r;i++)

#define of(i,l,r) for(int i=l;i>=r;i--)

#define fe(i,u) for(int i=head[u];i;i=e[i].next)

using namespace std;

typedef long long ll;

inline int rd()

{

    static int x,f;

    x=0,f=1;

    char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

const int N=100010;

int X,K,Q,T[N],ty;

struct cha{//a1-a2是定义域，[x1,x2]是值域

    int a1,x1,a2,x2,x;

    bool flag;

    inline int get(int a)

    {

        if(flag)return x;

        if(a<=a1)return x1;

        if(a>=a2)return x2;

        return a-a1+x1;

    }

}c[N];

inline void gao(int i,int tim)

{

    if(c[i].flag){

        c[i].x+=ty*tim;

        c[i].x=max(0,c[i].x);

        c[i].x=min(c[i].x,X);

        return;

    }

    if(ty==-1){//往下掉

        if(c[i].x2<=tim){

            c[i].flag=1;c[i].x=0;

            return;

        }

        if(tim>=c[i].x1){ c[i].a1+=tim-c[i].x1; c[i].x1=0; c[i].x2-=tim;}

        else{c[i].x1-=tim;c[i].x2-=tim;}

    }

    else{//往上掉

        if(c[i].x1+tim>=X){

            c[i].flag=1;c[i].x=X;

            return;

        }

        if(c[i].x2+tim>=X){ c[i].a2-=c[i].x2+tim-X; c[i].x2=X; c[i].x1+=tim;}

        else{c[i].x1+=tim; c[i].x2+=tim;}

    }

}

int main()

{

    freopen("inc.txt","r",stdin);

    X=rd();K=rd();

    c[0].a1=c[0].x1=0; c[0].a2=c[0].x2=X, c[0].x=0;

    c[0].flag=0;ty=-1;

    fo(i,1,K)

        T[i]=rd(),

        c[i]=c[i-1],

        gao(i,T[i]-T[i-1]),

        ty=-ty;

    int j=0;

    Q=rd();

    ty=-1;

    fo(i,1,Q){

        int t=rd(),a=rd();

        while((j<K&&T[j+1]<=t))j++,ty=-ty;

        int ans=c[j].get(a);

        ans+=ty*(t-T[j]);

        ans=min(ans,X);

        ans=max(ans,0);

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

    }

    return 0;

}

巴特西

ARC-082F Sandglass

题意

做法

题外话

code

最新文章

热门文章