ZJT's Blog

Keep your determination.

集训队作业之ARC077-E

2017-12-17 21:172017-12-17 21:17
集训队作业AtCoder差分

传送门

推一下发现每一段的代价是个关于$x$的分段一次函数,然后随便差分维护一下一次项系数和常数项,然后扫一遍就能知道$x$在每个位置时的总步数。

#include <cstdio>
#include <cstring>
#define MAXN 100010
#define LL long long

int n,m;
LL v[MAXN];
LL d[MAXN][2];

void add(int l,int r,LL x1,LL x2){
    d[l][0]+=x1;
    d[l][1]+=x2;
    d[r+1][0]-=x1;
    d[r+1][1]-=x2;
}

int main(){
#ifdef DEBUG
    freopen("E.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",v+i);
    LL s0=0;
    for(int i=1;i<n;i++){
        LL a=v[i],b=v[i+1];
        if(a<b){
            add(a+1,b,-1,a+1);
            s0+=b-a;
        }else{
            if(a<m) add(a+1,m,-1,a+1);
            add(1,b,-1,a-m+1);
            s0+=b+m-a;
        }
    }
    LL t0=0,t1=0;
    LL ans=1LL<<60;
    for(int i=1;i<=m;i++){
        t0+=d[i][0]; t1+=d[i][1];
        LL s=s0+t0*i+t1;
        if(s<ans) ans=s;
    }
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之ARC081-F

2017-11-22 18:82017-11-22 18:8
集训队作业AtCoder差分

传送门

先行和列都差分一下,问题变成了求最大的全$0$子矩阵。

我们可以枚举矩形底边所在的行,然后考虑每一列往上走有多少个$0$(记为$b_i$),把所有列按$b_i$排个序,然后从大到小枚举一下矩形高度$h$,把所有$b_i\geq h$的列合并起来,每次合并的时候统计一下答案就行了。

排序用的是基数排序,所以总复杂度是$O(n^2)$。

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

int n,m;
int a[MAXN][MAXN],b[MAXN],s[MAXN];
int p[MAXN][2];

void sort(){
    static int cnt[MAXN];
    memset(cnt,0,sizeof cnt);
    for(int i=1;i<=m;i++) cnt[b[i]]++;
    for(int i=1;i<=n+1;i++) cnt[i]+=cnt[i-1];
    for(int i=m;i>=1;i--) s[cnt[b[i]]--]=i;
}

int gao(int l){
    for(int i=1;i<=m;i++)
        if(a[l][i]) b[i]=l+1;
    sort();
    memset(p,0,sizeof p);
    int res=0;
    for(int i=1;i<=m;i++){
        int x=s[i];
        p[x][0]=p[x][1]=x;
        if(p[x-1][0]){
            p[p[x-1][0]][1]=p[x][1];
            p[x][0]=p[p[x][1]][0]=p[x-1][0];
        }
        if(p[x+1][1]){
            p[p[x+1][1]][0]=p[x][0];
            p[x][1]=p[p[x][0]][1]=p[x+1][1];
        }
        res=max(res,(l-b[x]+2)*(p[x][1]-p[x][0]+2));
    }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
            if(str[j]=='#')
                a[i][j]=1;
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            a[i][j]=a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1];
    int ans=max(n,m);
    n--; m--;
    for(int i=1;i<=m;i++) b[i]=1;
    for(int i=1;i<=n;i++) 
        ans=max(ans,gao(i));
    printf("%d\n",ans);
    return 0;
}

查看详细内容

集训队作业之ARC067-F

2017-11-2 11:332017-11-2 11:36
集训队作业AtCoder单调栈差分

传送门

一直想$O(NM)$没什么思路,结果一看数据范围$N$是$5000$。。。

然后就是各种乱搞技巧了,我对每个颜色维护了一个单调栈,为了求每个颜色的后缀min的和,直接差分之后转成前缀和,然后每次暴力扫的过程中就能顺便求出来了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5010
#define MAXM 210
#define LL long long
using namespace std;

int n,m;
LL d[MAXN];
LL a[MAXN][MAXM];
LL c[MAXN];

struct LCT{
    int f[MAXN];

    void init(){ for(int i=1;i<=n;i++) f[i]=i; }

    int access(int x){
        if(f[x]==x) return x;
        return f[x]=access(f[x]);
    }

    void link(int x,int y){
        access(x);
        access(y);
        if(f[x]^f[y]) f[f[y]]=f[x];
    }
}lct[MAXM];

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) lct[i].init();
    for(int i=2;i<=n;i++){
        scanf("%lld",d+i);
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lld",&a[i][j]);
    LL ans=0;
    for(int i=1;i<=m;i++){
        ans+=a[1][i];
        c[1]+=a[1][i];
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=i-1;
            while(x && a[lct[j].access(x)][j]<a[i][j]){
                int y=lct[j].access(x);
                c[y]-=a[y][j]-a[lct[j].access(y-1)][j];
                lct[j].link(y,i);
                x=y-1;
            }
            a[x+1][j]=a[i][j];
            c[x+1]+=a[x+1][j]-a[lct[j].access(x)][j];
        }
        LL temp=0;
        for(int j=1;j<=i;j++){
            temp+=c[j];
            ans=max(ans,temp-d[i]+d[j]);
        }
    }
    printf("%lld\n",ans);
}

查看详细内容

集训队作业之AGC006-C

2017-9-24 9:262017-11-2 11:35
集训队作业AtCoder打表差分

传送门

推了一下发现其实就是每次把一个数换成相邻两个数的和减掉这个数。把每个位置表示成其他位置的线性变换后,打了个表看看有什么规律,发现两行之间好像差别不大?于是想到了差分。差分后,在第$x$位做一个这样的操作,等价于把$x$和$x+1$位的值互换。这样我们直接把$M$次操作看成是$M$个对换,做完这些操作就可以看成是$1$到$n$的一个置换。我们我们直接把置换拆成一些轮换,然后直接在每个轮换上面每个点走$K$步就行啦。

(顺便不知道浮点意义何在。。。可能是用来坑人的)

代码:

#include <cstdio>
#include <cstring>
#define MAXN 100010
#define LL long long

int n,m;
LL v[MAXN],ans[MAXN],K;
int a[MAXN];
int p[MAXN];
bool visit[MAXN];

void gao(int x){
    static int b[MAXN];
    int numb=0;
    b[numb++]=x;
    visit[x]=1;
    for(int i=a[x];i^x;i=a[i]){
        b[numb++]=i;
        visit[i]=1;
    }
    for(int i=0;i<numb;i++){
        int x=b[i];
        p[x]=b[(K+i)%numb];
    }
}

int main(){
#ifdef DEBUG
    freopen("C.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",v+i),a[i]=i;
    for(int i=n;i>=2;i--) v[i]-=v[i-1];
    scanf("%d%lld",&m,&K);
    while(m--){
        int t;
        scanf("%d",&t);
        a[t]^=a[t+1]^=a[t]^=a[t+1];
    }
    for(int i=1;i<=n;i++)
        if(!visit[i])
            gao(i);
    for(int i=1;i<=n;i++)
        ans[i]=v[p[i]];
    for(int i=2;i<=n;i++)
        ans[i]+=ans[i-1];
    for(int i=1;i<=n;i++) printf("%.1lf\n",(double)ans[i]);
}

查看详细内容