BZOJ3712 [PA2014] Filoki

Description 有若干药瓶,第 $i$ 号药瓶里装着 $g_i$ 克 $i$ 号物质。 有 $m$ 次操作,第 $i$ 次会把 $a_i$ 号瓶子全部倒入 $b_i$ 号瓶子,之后 $a_i$ 号瓶子不会再用到。 一共 $k$ 对物质之间会反应生成沉淀(沉淀不再参与反应),1 克 $c_i$ 物质和 1 克 $d_i$ 物质反应生成 2 克沉淀。 当有若干反应都可以进行的时候优先进行编号小的反应。求整个过程中一共生成了多少沉淀。 $m<n\leqslant2\times10^5,k\leqslant5\times10^5$。 ...

2018 年 12 月 26 日

BZOJ1369 [Baltic2003] Gem

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

2018 年 12 月 26 日

ZOJ4058-4070 Solutions for QingDao ACM 2018

目前 H 不会写,K 不想写… ...

2018 年 11 月 7 日

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$ ...

生成函数简介

生成函数 生成函数(generating function)又称母函数,是处理组合数学问题的一大利器。 ...

LOJ6391 [THUPC2018] Tommy神的树

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

CTSC & APIO & THUPC2018 & SDOI2018R2 游记

由于此游记咕了一星期,不保证其内容完全正确 ...

2018 年 5 月 22 日

BZOJ5332 [SDOI2018] 旧试题

Description 令 d(i) 表示 $i$ 的约数个数。 求 $\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)$ 。 $A,B,C\leqslant10^5$ 。 ...

2018 年 5 月 18 日

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 日

BZOJ5328 [SDOI2018] 物理实验

Description 平面上有一个直线导轨,和 $n$ 个挡板(线段)。现在你可以在直线导轨上的某个位置放置一个长度为 $L$ 的激光发射器;它会以垂直于导轨的方向(向两边)发射激光。激光打到挡板上时会被吸收。 挡板间不相交,挡板和导轨不相交;挡板所在直线和导轨夹角不超过 $85^\circ$ 。 最大化吸收到激光的挡板总长。(只计算被激光照到的部分;计算这部分的挡板长度而不是激光宽度) $n\leqslant10^4, L\leqslant2\times10^9$ ,所有坐标绝对值 $\leqslant10^9$ 。 多组数据,数据组数 $T\leqslant100$ ,时限 10s 。 ...