bzoj5333: [Sdoi2018]荣誉称号

请不要去改题目给的输入，不然你会wa穿。。。

这么故弄玄虚的题目，肯定要先转换问题

看到这个不断的除2想起别人家的线段树的写法。。。x的两个孩子是x<<1和x<<1|1

然后问题就转换成给你一棵树，你可以增加树的权值，要让树上每一条长度为k+1的链上的点权和%m都等于0

先%m把取值范围降到[0,m-1]

观察一下性质，假如通过加权确定了根节点的点权=d，就确定了所有和它距离为k+1的点的点权必须也要变成d

据此我们把点分成k+1组，那是不是每一组的点权都要变成相同的呢？

然而并不，正确的答案应该是这棵树上面的前2^(k+1)-1个点，它们的点权是不受约束的，然后它们覆盖了下面的所有点

我们可以处理出一个c数组，表示第i组全部改成j的花费

然后就是裸的树包了

然而暴力处理c只能得到70分的好成绩，能不能再优化一下呢

我想法是上一个线段树，然而其实可以先把ci,0处理出来，然后DP出其他的值

ci,j=ci,j-1+∑bk(k属第i组) - m*∑u(u属第i组且初始值为u)bu

两个∑都是可以预处理的，所以是O(2^k*m)的复杂度

背包O(2^k*m^2)没什么毛病

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int n,k,m,Bin[];LL a[],b[];

unsigned int SA, SB, SC;int p, A, B;

unsigned int rng61(){

    SA ^= SA << ;

    SA ^= SA >> ;

    SA ^= SA << ;

    unsigned int t = SA;

    SA = SB;

    SB = SC;

    SC ^= t ^ SA;

    return SC;

}

void gen(){

    scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);

    for(int i = ; i <= p; i++)scanf("%lld%lld", &a[i], &b[i]);

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

        a[i] = LL(rng61() % A + );

        b[i] = LL(rng61() % B + );

    }

}

//-----------------------------scanf-----------------------------------------

LL c[][],sum[];//和i点合并，一起变成j的费用cij

void dfs(int x)

{

    if(x>n)return ;

    int f=x;

    while(f/Bin[k]>)f/=Bin[k];

    if(a[x]!=)

    {

        if(f==)

        {

            int t;t++;

        }

        c[f][]+=(LL(m)-a[x])*b[x];

        c[f][a[x]]-=b[x]*m;

    }

    sum[f]+=b[x];

    dfs(x<<);

    dfs(x<<|);

}

void getc()

{

    for(int i=;i<Bin[k];i++)

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

            c[i][j]+=c[i][j-]+sum[i];

}

//------------------------------------init----------------------------------------------------

LL f[][];

void treeDP(int x)

{

    if(x*>=Bin[k])

    {

        memcpy(f[x],c[x],sizeof(f[x]));

        return ;

    }

    int lc=x<<,rc=x<<|;

    treeDP(x<<);

    treeDP(x<<|);

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

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

        {

            int u=(i-j+m)%m;

            f[x][i]=min(f[x][i],f[lc][u]+f[rc][u]+c[x][j]);

        }

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    Bin[]=;for(int i=;i<=;i++)Bin[i]=Bin[i-]*;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        gen();k++;

        for(int i=;i<=n;i++)a[i]%=m;

        memset(c,,sizeof(c));

        memset(sum,,sizeof(sum));

        dfs();

        getc();

        memset(f,,sizeof(f));

        treeDP();

        printf("%lld\n",f[][]);

    }

    return ;

}

巴特西

bzoj5333: [Sdoi2018]荣誉称号

最新文章

热门文章