「CF1209E2」Rotate Columns (hard version)
给出一个 n \times m 的矩阵 a。
你可以进行若干次操作。每次操作,你可以选择任意一列,并循环移位该列中的元素。
设 r_i 表示第 i 行的最大值,求 \sum_{i = 1}^n r_i 的最大值。
数据范围:1 \leq n \leq 12,1 \leq m \leq 2000,1 \leq a_{i, j} \leq 10^5。
时空限制:3s / 512MiB。
给出一个 n \times m 的矩阵 a。
你可以进行若干次操作。每次操作,你可以选择任意一列,并循环移位该列中的元素。
设 r_i 表示第 i 行的最大值,求 \sum_{i = 1}^n r_i 的最大值。
数据范围:1 \leq n \leq 12,1 \leq m \leq 2000,1 \leq a_{i, j} \leq 10^5。
时空限制:3s / 512MiB。
给出一个包含 n 个点 m 条边的简单无向连通带权图。节点编号为 1 \sim n,其中恰好有 k 个充电中心,编号为 1 \sim k。
有一个电池容量为 c 的机器人在图中移动,任意时刻电量 x 必须为区间 [0, c] 中的整数。经过一条长度为 w 的边需要消耗 w 的电量,每当到达一个充电中心时,其电池将会充满。
有 Q 次询问,每次询问给出 a, b,你需要求出机器人从 a 到 b 至少需要的电池容量 c 是多少。
数据范围:2 \leq k \leq n \leq 10^5,1 \leq m, Q \leq 3 \times 10^5,1 \leq w \leq 10^9,1 \leq a, b \leq k,a \neq b。
时空限制:3s / 512MiB。
希望能带来好运!

希望能带来好运!

希望能带来好运!

希望能带来好运!
给出一棵大小为 n 的树,第 i 个节点的权值为 w_i。
你需要选出一个最大的节点集合,使得节点集合中不同的两个点 i, j,若 i 为 j 的祖先节点,必须满足 w_i \leq w_j。
数据范围:1 \leq n \leq 2 \times 10^5,1 \leq w_i \leq 10^9。
时空限制:1000ms / 250MiB。
希望能带来好运!
希望能带来好运!