UOJ Logo ydc的博客

博客

HAOI2015

2015-04-25 21:16:48 By ydc

写在前面

这场考试我参与了出题

大概是这样的,有三题是某横竖哥出的,我参与了验题,其中有两道正解一道暴力

然后我抄了ZJOI一道题,并向vfk借了一道题

所以我会做4道题

我不知道每道题目的题目名……所以,咳咳咳

一个树形dp题

题意

有一棵$n$个点的边代权树,每个点都是白点,然后你要选择$k$个点将其染黑

一棵树的价值是白点两两间的距离和加黑点两两间的距离和

最大化价值

$n \le 2000$

题解

首先我们要知道的是,这么一份伪代码的复杂度是$O(n^2)$的

void Tree_Dp(int p)
{
    size[p]=1;
    each(x,son[p])
    {
        Tree_Dp(x);
        for(int i=0;i<=size[p];++i)
            for(int j=0;j<=size[x];++j)
                update dp[p][i+j];
        size[p]+=size[x];
    }
}

复杂度的证明?考虑那个二重循环,可以看做分别枚举两棵子树的每个点。你会发现,点对$(u,v)$,只会在Tree_Dp($lca(u,v)$)处被考虑到,所以复杂度是$O(n^2)$

换句话说,$i$所考虑到的点的DFS序一定小于$j$所考虑到的点

于是我们就可以$dp_{i,j}$表示子树$i$选了$j$个黑点,然后转移暴力枚举子树里选了几个黑点,复杂度还是$O(n^2)$的,关键是怎么转移

其实说白了还是设状态的问题,如果设他是子树$i$选了$j$个黑点,子树内的同色点对距离和的话,是不好转移的对吧……所以我们要把他们往子树外连的也考虑进来

这么讲吧,假设我们把任意一对同色点之间的路径给标一下,那么$dp_{i,j}$记录的就是,子树$i$选了$j$个黑点,子树内的所有被标过的路径权值和,这样就能转移了

简单地说,就是改变一下状态定义,就能让他不仅考虑子树$i$内部的和,把子树外的延伸到子树内的那些边也考虑了

这是我验题的代码

void update(LL &a,LL b)
{
    if(a<b)
        a=b;
}
void DFS(int p,int fa)
{
    static LL tmp[maxn];
    fill(dp[p]+2,dp[p]+n+1,-INF);
    size[p]=1;
    for(int i=start[p];i;i=next[i])
        if(to[i]!=fa)
        {
            int q=to[i];
            DFS(to[i],p);
            fill(tmp,tmp+size[p]+size[q]+1,-INF);
            for(int j=0;j<=size[p];++j)
                for(int k=0;k<=size[q];++k)
                    update(tmp[j+k],dp[p][j]+dp[q][k]+len[i]*(k*(m-k)+(size[q]-k)*(n-m-(size[q]-k))));
            size[p]+=size[q];
            for(int j=0;j<=size[p];++j)
                dp[p][j]=tmp[j];
        }
}

一个数据结构题

题意

一棵$n$个点带权的树,$m$个操作,分别是:单点加、子树加、查询点到根的链的权值和

题解

这题是超级良心送分题啦~考验基础数据结构水平

(算了还是卖卖萌把这题讲讲)

算贡献

假设点$u$的子树加了$x$,点$v$在点$u$的子树内,那么对$v$到根的链的权值和会带来$(dep_v-dep_u+1)x$的贡献

假设点$u$加了$x$,点$v$在点$u$的子树内,那么对$v$到根的链的权值和会带来$x$的贡献

$dep$数组是常量,我们设一个点$i$到根的链的权值和为$k_idep_i+b_i$

那么子树加操作就是把整棵子树里每个点的$k$值和$b$值加上同一个数,单点加操作就是把整棵子树的$b$值加上同一个数

子树可以转为DFS序的一段区间,所以用两个树状数组分别维护每个点的$k,b$数组就行了

str

题意

你有一个长度为$n$的数字串。

定义$f(S)$为将$S$拆分成若干个$1 \sim m$的数的和的方案数,比如$m=2$时,$f(4)=5$,分别为:

$4=1+1+2,4=1+2+1,4=2+1+1,4=2+2,4=1+1+1+1$

你要将这个数字串分割成若干个数字(允许前导0),将他们加起来,求$f$,并求和,和为$g$。

比如$g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

已知字符串和$m$后求答案对$998244353(7×17×223+1$,一个质数$)$取模后的值。

字符串长度不超过$500$,$m \le 5$

题解

ydc从ZJOI上抄的原题,来源是ZJOI2011年的细胞

首先考虑$f$怎么求,很容易发现$f(n)=\sum\limits_{i=\max(0,n-m)}^{n-1} f(i)$。由于$m$只有$5$,我们可以用一个$m \times m$的矩阵表示转移矩阵,记作$A$。

那么答案就是一堆$A$的若干次方的和(两个$m \times m$的矩阵是可以相加的)。

假设我们把数字串分成$k$个数,分别是$a_1,a_2,a_3,\cdots,a_k$,那么答案是$A^{a_1+a_2+a_3+\cdots+a_k}$,他恰好等于$A^{a_1} \times A^{a_2} \times A^{a_3} \cdots \times A^{a_k}$。

一堆$m \times m$的矩阵,不仅能乘,还能加,还有分配律,我们就能$dp$了

$dp$当然就是$dp_i$表示$1 \sim i$这部分的答案矩阵,转移显然,贴下标程的代码吧

    for(int i=1;i<=n;++i)
    {
        now=pw[0][a[i]-'0'];
        F[i].n=F[i].m=m;
        for(int j=i-1;j>=0;--j)
        {
            F[i]+=now*F[j];
            if(j)
                now=now*pw[i-j][a[j]-'0'];
        }
    }

复杂度是$O(n^2m^3)$

set

题意

一个有$n$个元素的集合,你有一个空集,每次你会选择集合的一个子集,与当前集合进行取并集操作,问期望多少次后第一次变成全集,选中每个子集的概率是输入给你的

$n \le 20$

题解

vfk教ydc做人

先来普及一点科技

定义一种乘法为$c[n]=\sum\limits_x\sum\limits_y a[x]b[y] [x \mid y=n]$

定义一种子集和变换,即$f(n)=\sum\limits_{x \subseteq n}g(x)$

我们用子集和变换来考虑上面的乘法

左边自然是$\sum\limits_{x \subseteq n}c_x$,右边应该是$\sum\limits_{x \subseteq n}\sum\limits_{y \subseteq n} a[x]b[y]=\sum\limits_{x \subseteq n}a[x]\sum\limits_{y \subseteq n}b[y]$

有没有发现什么?进行了子集和变换之后,之前的奇怪乘法,变成了人们熟知的点积

那么我们只要把$a,b$给子集和变换一下,点积得到$c$,再把$c$变回来

说到这里,介绍一点科技:如何巧妙地子集和变换与变回来

    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]+=a[j^(1<<i)];
    for(int i=0;i<n;++i)
        for(int j=0;j<N;++j)
            if(j>>i&1)
                a[j]-=a[j^(1<<i)];

分别是变换与变回

好吧回归正题

读入的数组是$p$,将它看作多项式,先用定义的乘法来考虑,那么$p^k$的第$i$项就代表$k$轮之后得到$i$的概率

答案是$\sum\limits_{k}k \times (p^k-p^{k-1})[2^n-1]$。我们设$f(x)=\sum\limits_{k}k \times (p^k-p^{k-1})[x]$

由于定义的那个乘法太麻烦,就子集和变换一下,就变成了我们所熟知的点积了(不是多项式乘法)

$(p^k)[x]$就是$p[x]^k$

$f$的子集和变换后的结果,是$\sum\limits_{k}k \times (p^k-p^{k-1})=-(1+p+p^2+p^3+\cdots)$

由于$p$所有元素加起来才是$1$,那么子集和变换后的$p$里每个值,肯定也是在$[0,1]$之间的

于是$-(1+p+p^2+p^3+\cdots)$可以$O(1)$算出,得到了$f$的子集和变换结果,变回去即可

时间复杂度:$O(n2^n)$

评论

wangck1998
前排
1150076053
前排
Asm_Def
跪跪跪……不过暴力分拿得好爽……= =
taorunz
子集或卷积有些裸TAT
TKD
前排
cstdio
Orz……这个子集和变换不是只枚举了每个位置上的1吗……为什么能求出子集和?
Hydra
Orz
Prime
maya 居然是这样的出题。
Bill_Yang
讲得很好,顶起!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。