ZJT's Blog

大変に気分がいい~

集训队作业之ARC073-F

2017-11-28 15:92017-11-28 15:9
集训队作业AtCoderDP树状数组

传送门

考虑最终的决策,可以分成很多段,每段里面选的棋子一样。最终的总代价可以表示成每段内相邻两个的代价,以及跨段的代价。

我们可以DP,设$f_i$表示当前有一个棋子位于$x_i$,另一个位于$x_{i+1}$,且已经走完$x_1$~$x_i$的最小代价。转移可以写成:$$f_i=\min_{j<i}f_j+|x_{i+1}-x_j|+s_i-s_{j+1}$$

其中$s_i$表示相邻两个$x_i$之间距离的前缀和。为了去掉式子中的绝对值,我们根据$x_i\geq x_j$和$x_i\leq x_j$,分别维护两个树状数组进行转移,就能在每步$O(\log n)$的时间内进行DP啦。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

int n,m;
LL a[MAXN],sd[MAXN],A,B;
LL f[MAXN];

struct Fenwick{
    LL c[MAXN];

    Fenwick(){ memset(c,0x77,sizeof c); }

    void modify(int x,LL v){
        while(x<=m){
            if(v<c[x]) c[x]=v;
            x+=x&(-x);
        }
    }

    LL getMin(int x){
        LL res=1LL<<50;
        while(x){
            if(c[x]<res) res=c[x];
            x-=x&(-x);
        }
        return res;
    }
}s1,s2;

int main(){
    scanf("%d%d%lld%lld",&m,&n,&A,&B);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);
    for(int i=2;i<=n;i++) sd[i]=abs(a[i]-a[i-1]);
    for(int i=1;i<=n;i++) sd[i]+=sd[i-1];
    f[0]=min(abs(A-a[1]),abs(B-a[1]));
    s1.modify(A,abs(B-a[1])-A-sd[1]);
    s2.modify(m-A+1,abs(B-a[1])+A-sd[1]);
    s1.modify(B,abs(A-a[1])-B-sd[1]);
    s2.modify(m-B+1,abs(A-a[1])+B-sd[1]);
    for(int i=1;i<n;i++){
        f[i]=min(a[i+1]+sd[i]+s1.getMin(a[i+1]),-a[i+1]+sd[i]+s2.getMin(m-a[i+1]+1));
        s1.modify(a[i],f[i]-a[i]-sd[i+1]);
        s2.modify(m-a[i]+1,f[i]+a[i]-sd[i+1]);
    }
    LL ans=1LL<<62;
    for(int i=0;i<n;i++) ans=min(ans,f[i]+sd[n]-sd[i+1]);
    printf("%lld\n",ans);
    return 0;
}

查看详细内容

集训队作业之ARC068-E

2017-10-7 10:382017-10-7 10:38
集训队作业AtCoder离线树状数组

传送门

直接把每个$d$值可能经过的所有点存起来,再根据每个点的下一个点的位置,可以把每个商品转换成平面上一个矩形内所有点+1,直接离线+树状数组就行了。因为总共有$O(n\log n)$个点,再加上数据结构总体复杂度就是$O(n\log^2n)$了。

无压力1A。(也就只有这些水题能1A了)

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2000010
using namespace std;

int read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    int res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n,m,numq;
int p[MAXN][2];
int ans[MAXN];

namespace Fenwick{
    int c[MAXN];

    void add(int x,int v){
        x++;
        while(x<=n+1){
            c[x]+=v;
            x+=x&(-x);
        }
    }

    int sum(int x){
        x++;
        int res=0;
        while(x){
            res+=c[x];
            x-=x&(-x);
        }
        return res;
    }
}

struct Event{
    int x1,x2,y,id;
}q[MAXN];

bool cmp(Event x,Event y){
    if(x.y==y.y) return x.id<y.id;
    return x.y<y.y;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    m=read(); n=read();
    for(int i=1;i<=m;i++){
        p[i][0]=read(); p[i][1]=read();
        q[++numq]=(Event){p[i][0],p[i][1],p[i][1]+1,0};
    }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            q[++numq]=(Event){j,j,j+i,i};
    sort(q+1,q+numq+1,cmp);
    for(int i=1;i<=numq;i++)
        if(q[i].id) ans[q[i].id]+=Fenwick::sum(q[i].x1);
        else Fenwick::add(q[i].x1,1),Fenwick::add(q[i].x2+1,-1);
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

查看详细内容