OpenJ_POJ1055 Tree

题目链接

题面

以随机父节点的方式生成一棵节点个数不大于 $n$ 的随机树, 求平均结点深度的期望
$n\leq 10^{18}$

题解

又是 Picks 出的题
这题依然是好题
设前面已经生成 $i-1$ 个点,当前生成第 $i$ 个点,这个点的期望深度为 $d_i$ ,前 $i$ 个节点的期望平均深度为 $f_i$ ,则
$$
\begin{eqnarray}
d_i&=&f_{i-1}+1 \tag{1}\\
f_i&=&\frac{f_{i-1}(i-1)+d_i}{i} \tag{2}\\
\end{eqnarray}
$$
继续阅读

TsinsenA1221 大楼

题目链接

题意

给出一张带权图, 从 $1$ 结点出发, 问最少走过多少条边, 使得权值总和大于等于 $m$ 。
$1\leq n\leq 100, 1\leq m\leq 10^{18} $

题解

发现给出了一个邻接矩阵,而且从 $i\to k$ 和从 $k\to j$ 的权值和可以更新 $i\to j$ 的最大权值和
可以看做用邻接矩阵中 $g[i][k]+g[k][j]$ 来更新 $g[i][j]$
于是类似于矩乘的做矩阵快速幂棵快速得到走过 $l$ 条边的最大权值
继续阅读

BZOJ4911 切树游戏

建议在 LOJ 上提交

题解

一开始想用点分治然后DP,结果发现会统计不合法答案,后来去看题解了,发现这题简直神题
算法:动态dp+FWT
虽然题目中表示树是无根的,但是我们还是可以随便选一个点作为根
设 $f(i,k)$ 为以 $i$ 为根节点的子树,异或值为 $k$ 的联通子树个数
发现某个节点的 $f$ 值可以从所有子树的 $f$ 做异或卷积转移得来
具体地说,设 $F_i(z)$ 代表 $i$ 的 $f$ 数组的生成函数,则
$$ F_i(z) = z^{v_i} \prod (F_{son_i}(z)+z^0)$$
其中卷积为异或卷积
继续阅读

一道有趣的题目

其实是今天考试题,话说昨天做了 FWT 题今天就考一道 FWT 题真巧

题意

给出 $n$ 堆石子,每堆石子个数为 $a_i$ ,然后删掉几堆石子(不能全删),问至少删多少堆使后手必胜

题解

设 $XOR$ 为所有 $a_i$ 的异或和,则题目可以转化为选最少的数是它们异或起来为 $XOR$
继续阅读

BZOJ1040 骑士

题解

一类基环树题目的套路
首先发现可以将题目中的痛恨关系转化成一些基环树(显然是无向边)
首先考虑如果是树应该怎么做,就是一个及其简单的树形 $dp$
设状态 $f[i][0/1]$ 表示节点 $i$ 选或不选的最大战斗力总和
于是有转移
$$ f[i][1]=\sum f[son[i]][0] $$
$$ f[i][0]=\sum max{f[son[i]][0], f[son[i]][1]} $$
继续阅读

BZOJ3687 简单题

题意

给出四个问题:
1.子集的异或和的算术和
2.子集的异或和的异或和
3.子集的算术和的算术和
4.子集的算术和的异或和
请解决四个问题

题解

虽然只要解决第四个,但还是随便打了打前面的问题
前三个问题之和暴力拍了一下没错,不保证实际正确性
继续阅读

BZOJ1875 HH 去散步

题意

给出一张简单图,求走 $t$ 步从 $A$ 走到 $B$ 的方案数,不允许先从 $x$ 走到 $y$ 然后下一步从 $y$ 走回 $x$

题解

如果去掉”不会立刻沿着刚刚走来的路走回”这个条件,我们直接用邻接矩阵做矩阵快速幂就行了
但是加上这个条件后,发现直接用点之间的关系转移会有不合法方案被算进去
继续阅读

BZOJ4870 组合数问题

题解

首先推导一下这个式子的组合意义
然后发现其实就是要求在 $nk$ 件物品中取出的物品件数 $\% k$ 为 $r$ 的方案数
设在 $n$ 件物品中取物品件数 $\% k$ 为 $i$ 的方案数为 $f[n][i]$ ,那么 $f[n+1][i] = f[n][i]+f[n][(i – 1 + k) mod k] $
发现转移方程与第一位无关,于是可以快乐矩乘
复杂度 $O(k^3\log{nk})$
继续阅读

luogu3953 逛公园

题解

与路径统计很像的一道题。

设$f[i][k]$为起点到$i$点,距离与到其的最短路偏差(肯定大于$d[i]$,$d[i]$为$1$到$i$的最短路)为$k$时的路径数。

然后可以拓扑排序后按照$k$从小到大的对每个点进行$dp$:

设有边$(u,v,w)$,转移方程可以写成$f[v][d[u]+w+k-d[v]]+=f[u][k]$

顺序很重要,需要先枚举$k$然后再枚举点和边。
继续阅读

BZOJ4720 换教室

题解

发现是一个比较简单的期望dp题,一开始想用一个状态$f[i][j]$表示前$i$个数取$j$个的期望,然后用一个数组记录是否申请以帮助转移,后来发现实际上如果某一个状态选择申请,那后面的状态也可能由当前状态的不申请情况转移过来,那也可以比较简单的设计新状态,$f[i][j][0/1]$,第三位表示当前状态选/不选的期望。
继续阅读