BZOJ5329 [SDOI2018] 战略游戏

Description 一个 $n$ 个点 $m$ 条边的无向连通图,$q$ 次询问。每次询问给出一个集合 $S$ ,问有多少结点 $x$ 满足: $x\not\in S$; 删除结点 $x$ 及与其相连的所有边之后, $S$ 中的点不连通。 $n,q\leqslant10^5;m,\sum|S|\leqslant2\times10^5$ 。 多组数据,数组组数 $T\leqslant10$ ;时限 $10s$ 。 ...

CF947E Perpetual Subtraction

Description 有一个非负整数 $x$ 。你要执行 $m$ 次操作,每次操作是 x = randint(0, x) ( = 表示赋值, randint(0, x) 均匀随机地在 $[0, x]$ 中取一个整数)。 现在已知初始的 $x$ 会随机在 $[0, n]$ 取值,且取 $i$ 的概率是 $p_i$ ,求最后取到 $[0, n]$ 每个数的概率。 $$n\leqslant10^5, m\leqslant10^{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$ 。 ...

BZOJ2815 [ZJOI2012] 灾难

Description $n$ 个点 $m$ 条边的DAG,对于每个点,求它的重要度。重要度定义如下: 对于 $v$ 这个点,将其(和其相连的所有边)删去。之后考察所有点,如果某个点初始时出度不为 $0$ 而当前出度为 $0$ ,则将这个点也删去。重复这个过程直到没有点被删去。 $v$ 的重要度即为除它以外删掉的点的个数。 $n\leqslant10^5$ 。 ...

BZOJ5006 [THUWC2017] 随机二分图

Description 有一个左右各 $n$ 个点的二分图。有 $m$ 组有概率出现的边,分为三种: 一组一条边,出现或不出现的概率各有 50%。 一组两条边,同时出现或同时不出现的概率各有 50%。 一组两条边,必定会恰好出现一条,概率各有 50%。 组与组之间的概率是独立的。 问完美匹配的期望个数 $E$ ,输出 $2^nE \pmod {10^9+7}$ (显然是整数)。 ...

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

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

BZOJ5251 [多省联考2018] 劈配

Description $n$ 个选手和 $m$ 个导师,第 $i$ 个选手把第 $j$ 个导师填到了自己的第 $a_{i,j}$ 志愿里。选手按照编号从小到大依次选择导师,每名选手会选择他所可能选到的最高志愿的老师之一(志愿编号越小就越高,如果 $a_{i,j}=0$ 表示第 $i$ 名选手未把第 $j$ 名导师填进志愿)。每名选手有一个目标值 $s_i$ 表示他想要选到第 $1~s_i$ 的志愿之一。 第 $i$ 名导师最多被选 $b_i$ 次。 问:每名选手会选到哪一个志愿、以及他要达成目标,最少要上升多少名次(在其它选手相对排名不变的情况下)。 $n, m\leqslant200$ ,每名选手每个志愿最多有 $10$ 名导师。 ...

九省联考2018 游记

可算是撑过去了…… ...

2018 年 4 月 8 日

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

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