BZOJ5475 [WC2019] 数树

Description 对于两棵树 $T_1, T_2$,定义它们的交 $T_1\cap T_2$ 是它们的边集的交形成的森林,$k(T_1\cap T_2)$ 表示这个森林的连通块个数,求下列三种问题之一: 给定 $T_1, T_2$,求 $y^{k(T_1\cap T_2)}$; 给定 $T_1$,求 $\sum_{T_2}y^{k(T_1\cap T_2)}$; 给定 $n$,求 $\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}$ 其中 $n\leqslant 10^5$,上面的 $\sum$ 都是对所有可能的 $n^{n-2}$ 种树求和。 答案对 $998244353$ 取模。 ...

BZOJ1369 [Baltic2003] Gem

Description 给出一棵 $n$ 个结点的树,要求给每个点一个正整数权值,使得相邻的结点的权值不相等,且最小化权值和。 $n\leqslant10^4$。 ...

2018 年 12 月 26 日

LOJ565 [LR10] mathematican 的二进制

Description 一个初始为 0 的二进制数,有 $m$ 次操作。 第 $i$ 次操作是将这个二进制数加上 $2^{a_i}$ 。这个操作以 $p_i$ 的概率执行。 如果某次操作执行了并且修改了二进制数的 $k$ 位,那么它会带来 $k$ 的代价。 问代价和的期望,答案对 $998244353$ 取模。 $n=\max a_i\leqslant10^5, m\leqslant2\times10^5$ ...

LOJ6391 [THUPC2018] Tommy神的树

Description 一棵 $n$ 个结点的树。初始时 $a$ 和 $b$ 是黑的,其他点是白的。 每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。 问把结点染红的顺序有多少种。 $1\leqslant a,b\leqslant n\leqslant234567$ 答案对 $998244353$ 取模,时限 10s 。 ...

BZOJ5340 [CTSC2018] 假面

Description 有一列数 $a_i$ ,有 $Q$ 个操作: 对于某个 $i$ ,以 $p$ 的概率使 $a_i$ 减一(若 $a_i=0$ 则忽略); 指定某些 $a_i$ ,从这些 $a_i$ 中的所有大于零的位置随机选一个,对于每个 $a_i$ 你需要求出选到它的概率。 你还要求出每个 $a_i$ 执行完所有操作后的期望。 令 $C$ 为 2 操作的数量: $n\leqslant200,Q\leqslant2\times10^5,C\leqslant10^3;$ 初始时 $a_i\leqslant100$ 。 时限 6s 。 ...

2018 年 5 月 18 日

BZOJ4911 [SDOI2017] 切树游戏

Description 一棵 $n$ 个结点的树,每个点有点权 $a_i$ 。有 $q$ 个操作: Change x y, 表示把编号为 $x$ 的点的点权改为 $y$; Query k, 表示询问点权异或和为 $k$ 的连通块个数 $\bmod 10007$ 。 $n\leqslant30000,a_i\in[0, m),m\leqslant128,q\leqslant30000$ 。 $m$ 是 $2$ 的幂。 ...

BZOJ1492 [NOI2007] 货币兑换

Description 你有 $S$ 元钱。在第 $i$ 天你可以把 $x$ 元钱变成 $\frac{Rate_ix}{Rate_iA_i+B_i}$ 单位 A 金券和 $\frac{x}{Rate_iA_i+B_i}$ 单位 B 金券;或把 $a$ 单位 A 金券 $b$ 单位 B 金券变成 $A_ia+B_ib$ 元钱。 问 $n$ 天后你最多能持有多少元钱。 $n\leqslant10^6$ 。 ...

BZOJ5252 [多省联考2018] 林克卡特树

Description 有一棵 $n$ 个结点的树,每条边有边权。给定 $0\leqslant k\lt n$ ,要求 $k+1$ 条路径(可以仅包含单个点),使得它们不在结点处相交(包括两条路径端点相同的情况),最大化路径上的边权和。 $0\leqslant k \lt n \leqslant 3\times10^5$ ...

BZOJ5250 [多省联考2018] 秘密袭击

Description 一棵 $n$ 个点的树,第 $i$ 个点有点权 $d_i$ 。给定一个数 $k$ ,求所有 [ 大小不小于 $k$ 的连通块中的第 $k$ 大的点权 ] 的和。 $k \leqslant n \leqslant 1666$ ,点权最大值 $W \leqslant 1666$ 。 ...

BZOJ5248 [多省联考2018] 一双木棋

Description 有一个 $n \times m$ 的方格, Alice 和 Bob 玩游戏。每次每人可以选择一个格子占领,前提是这个格子未被占领且它左上方的所有格子都已被占领。 第 $i$ 行第 $j$ 列的格子若被 Alice 占领则 Alice 获得 $A_{i, j}$ 分,若被 Bob 占领则 Bob 获得 $B_{i, j}$ 分。 Alice 先手,所有格子都被占领时结束。双方都想最大化自己的得分与对方得分的差。求双方采取最优策略时 Alice 得分与 Bob 得分的差。 $n, m\leqslant10$ 。 ...

2018 年 4 月 8 日