BZOJ5249 [多省联考2018] IIIDX

Description 给定一个长为 $n$ 的序列 $d$ (可能有重复)和一个常数 $k$ (不一定是整数)。 求 $d$ 的一个排列,要求满足 $d_i \geqslant d_{\lfloor\frac ik\rfloor}$ 。 求所有满足条件的排列中字典序最大的一个。 ...

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 日

BZOJ3925 [ZJOI2015] 地震后的幻想乡

Description 一个 $n$ 个结点、 $m$ 条边的无向图,所有边权在 $[0, 1]$ 之间均匀分布(互相独立);求这个图的最小生成树上的最大边权的期望值。 $n \leqslant 8, m \leqslant \frac{n(n-1)}2$ 。 ...

BZOJ1494 [NOI2007] 生成树计数

Description 有一个 $n$ 个点的图。$n$ 个点排成一排,两个点之间有边当且仅当它们距离不超过 $k$ (即它们之间隔了不超过 $k-1$ 个点)。 求这个图的生成树个数。 $n\leqslant10^{15}, k\leqslant5$ 。 ...

BZOJ4944 [NOI2017] 泳池

Description 有一个底边长 $n$ 个单位,高为 $+\infty$ 的矩形网格,其中每个格子都有可能是危险的或者安全的。 每个格子安全的概率为 $p$ ,危险的概率为 $1 - p$ 。任意两个格子是否安全都是独立的。 要选取一个子矩形,要求它与底边相邻且其中所有格子都是安全的。最大化选取子矩形的面积。求答案恰好为 $k$ 的概率。 $n \leqslant 10^9, k \leqslant 1000$ 。 ...

BZOJ4942 [NOI2017] 整数

Description 你要维护一个二进制数 $x$ ,有 $n$ 个操作: 1 a b ,表示 $x \mathrel{+}= a \times 2^b$ ; 2 k ,表示询问 $x$ 第 $k$ 个二进制位的值。 初始时 $x = 0$ 。 $n \leqslant 10^6, |a| \leqslant 10^9, b, k \leqslant 3 \times 10^7$ ...

2018 年 3 月 19 日

BZOJ3669 [NOI2014] 魔法森林

Description 一个 $n$ 个点 $m$ 条边的无向图,每条边有 $A$ 和 $B$ 两个边权。求一个从 $1$ 到 $n$ 的路径 $P$ ,最小化 $\max_{e \in P} A_e + \max_{e \in P} B_e$。 $n \leqslant 50000, m \leqslant 100000, A_i, B_i \leqslant 50000$. ...

2018 年 3 月 19 日

BZOJ5119 [清华集训2017] 生成树计数

Description 一个$s$个点的图,目前被$s-n$条边连成了$n$个连通块,第$i$个连通块大小为$a_i$。要求你再连$n-1$条边把它变成一棵树。对于每一棵树,若第$i$个连通块连出了$d_i$条边,其价值为 $val(T)=\left(\prod_{i=1}^nd_i^m\right)\left(\sum_{i=1}^nd_i^m\right)$ 求所有生成树的价值和$\bmod998244353$。$n \leqslant 30000, m \leqslant 30$。 ...

新的开始

搭建了 Hexo 博客… 新的开始吧…

2018 年 3 月 14 日

BZOJ3434 [WC2014] 时空穿梭

Description 有一个$n$维的超立方体$[1, m_1]\times[1, m_2]\times\dots\times[1,m_n]$。 现在要再其内部选择$c$个整点,使得其每一维都是递增的(也即,$\forall i=1\dots c-1, j=1\dots n, x_{i+1, j}>x_{i,j}$),且这$c$个点共线。求方案数。 多组数据,至多$1000$组;$n\leqslant 11, c\leqslant 20, m_i\leqslant 10^5$。 ...

2018 年 3 月 14 日