写在前面
这场考试我参与了出题
大概是这样的,有三题是某横竖哥出的,我参与了验题,其中有两道正解一道暴力
然后我抄了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)$