2024冬令营

THUWC

Day1

T1

有 $n$ 个人, $m$ 个任务, 第 $i$ 个人完成第 $j$ 个任务的收益是 $a_{i, j}$, 雇佣第 $i$ 个人的代价是 $c_i$, 一个人可以完成多个任务, 雇佣代价不重复计算, 最大化收益减代价.

$n\le 15, m\le 3000$

最显然的暴力是 $f_{i, S}$ 表示前 $i$ 个人, $S$ 中任务要被完成的最大收益, 复杂度 $nm2^n$, 过不了.

预处理 $g_S$ 表示一个人完成 $S$ 的任务的最大收益, 则答案就是 $g_S$ 子集卷积, 暴力 $3^n$ 就过了.

T2

给定长 $n$ 的环 $a$, $m$ 次随机位置 $p\in [0, n]$ 和 $l\in [1, n]$, 把环上从 $p$ 开始的长 $l$ 的区间随机等概率重排, 求最后每个位置的期望.
$n=2^k, k\le 17, m\le 10^9$

容易发现相当于有固定的 $c_{i, j}$ 使得变换一次后的期望 $a’i=\sum_j a_j c{i, j}$, 而列 $c$ 的式子的时候容易发现其只和 $\min \vert i-j\vert, n-\vert i-j\vert$ 有关, 即设 $c_d$ 表示 $\vert i-j\vert=d$ 时 $j$ 对 $i$ 的贡献, 容易就是和 $c$ 数组做模 $n$ 的循环卷积, 又因为 $n$ 都是 $2$ 整次幂所以直接dft然后对点值快速幂再idft就 $n(\log n+\log m)$ 了.

T3

有一个 $n\times m$ 的矩阵 $a$, 每次可以询问一个矩形内是否有 $1$, 求最大的 $i+j$ 使得存在 $a_{i, j}=1$
要求询问次数为 $n$, 询问的矩形的长边的总和不超过 $\dfrac{3}{2}n\log n$

不会.

T4

有 $n\times m$ 的网格, 每次给一行的区间($(i, l), (i, l+1)\ldots (i, r)$)区间设为 $1$, 对于当前风速 $c$ 一个格子 $(i, j)$ 可用当且仅当 $(i, j-c+1)$ 到 $(i, j)$ 这个区间全部为 $1$, 定义连通为四连通, 求 $(a, b)$ 到 $(c, d)$ 连通的最大的 $c$.
$n\le 10^5, m\le 10^9, q\le 3\times 10^5$

容易发现如果有相邻两行 $的两个1$ 的区间, 能从一个区间走到另一个区间的最大的 $c$ 是两个区间交的长度, 而答案就是以交的长度为权值在相邻两行之间的区间连边后从起点到终点的边权的最小值的最大值, 和使得起点和终点两个点可用的最大值取 $min$, 而容易发现这么连边边的条数是 $O(q)$ 的(对于一共有 $k$ 个区间的两行), 以相交的形式连出的边不超过 $k$(少的那一行每个提供两个端点), 而包含的形式连出的边不超过 $k$(必然有一个区间只有这一条边). 于是直接lct维护最小瓶颈生成树, 加边加边即可.