ContestHunter暑假欢乐赛 SRM 15

　　菜菜给题解，良心出题人！但我还是照常写SRM一句话题解吧...

　　T1经典题正解好像是贪心...我比较蠢写了个DP，不过还跑的挺快的

　　f[i]=min( f[j-a[j]-1] )+1 { j+a[j]>=i , j<=i }

　　这个显然就是查询一个后缀的最小值，倒着做BIT查前缀就行了

　　T2建一个超级源点做MST就行了

　　T3是一个模拟题，首先预处理出所有数在当前位置是小于坐标还是大于坐标，也就是随着向左挪一格是对答案贡献是增还是减，同时可以算出对答案贡献从增变减或从减变增的分界点，做差分。再扫一遍的时候，照常差分的同时将第一个数跑到最后一个数做一个特殊的处理，不然不好写。特殊处理就是把now减去2，因为第一个数在1位置一定对答案是增，而到n的时候变减了，至于之后状态的改变就靠差分了，所以这个数对答案的贡献从增变成了减，一下-2，但是在算当前答案的时候实际上只少了1，于是计算当前答案我们再把1给他加回去...

　　看起来就很乱，因为是个比较复杂的模拟题，再加上我写的丑+表达能力不好QAQ

　　T3看代码吧...或者去向CYC学习一波，他的T3比我快到不知道哪里去了

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

int n,x,a[],chafen[],fangan;

ll xz,zeng,ans;

void read(int &k)

{

    int f=;k=;char c=getchar();

    while(c<''||c>'')c=='-'&&(f=-),c=getchar();

    while(c<=''&&c>='')k=k*+c-'',c=getchar();

    k*=f;

}

int abs(int x){return x>=?x:-x;}

int main()

{

    read(n);

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

    read(a[i]);

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

    {

        if(a[i]>=i)

        {

            chafen[a[i]-i]++;

            xz+=a[i]-i;

            zeng--;

        }

        else

        {

            chafen[a[i]+n-i]++;

            xz+=i-a[i];

            zeng++;

        }

    }

    ans=xz;

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

    {

        zeng+=chafen[i-]*-;

        xz+=abs(a[n-i+]-)-abs(a[n-i+]-n)++zeng;

        ans=min(ans,xz);

    }

    printf("%lld",ans);

    return ;

}

巴特西

ContestHunter暑假欢乐赛 SRM 15

最新文章

热门文章