国庆集训 Test 1

HISTOGRA - Largest Rectangle in a Histogram

悬线法裸题。

题意

从 $1$ 到 $n$ 每个位置有一个高度为 $h_i$，宽度为 $1$ 的矩形。

求所有矩形覆盖面积中最大子矩形。

P2801 教主的魔法

分块裸题，作为初学者用来练手。

题意

维护长度为 $n$ 序列，有两种操作：

1. 区间加法。
2. 求区间中大于 $k$ 的数的个数。

[USACO03FALL]Cow Exhibition G

题意

给定 $n$ 个数分别有 $2$ 个权值 $a_i,b_i$，选取一些数使得 $\sum a_i\geq 0,\sum b_i\geq 0$ 的条件下求 $\sum a_i+b_i$ 的最大值。

P1064 金明的预算方案

存在依赖关系背包转化分组背包。

题意

给定 $n$ 个物品的价值和体积，他们之间存在简单的依赖关系，即一个结点要么是父亲结点，要么是儿子结点，且一个父亲结点最多有两个儿子结点。

[USACO12OPEN]Bookshelf G

题意

考虑现在有 $n$ 本书并给定一个最大长度 $L$，第 $i$ 本书有高度 $h_i,w_i$。每次选取一段范围满足该段范围内的所有书的 $\sum w_i\leq L$，那么这次选取的贡献为 $\max\{h_i\}$。

Railgun

题意

给定 $n,a,b$，你现在在 $0$ 处跳格子，每次可以向前跳 $a$ 格或者 $b$ 格。

求到达 $n$ 格的方案数，答案对 $10,007$ 取模。$(n,a,b\in[1,10^9])$

CF1305G-Kuroni and Antihype

给定的数据范围是一个弱化版本。

题意

给定 $n$ 个点权 $\{a\}$，并按照规则：对于 $i,j$，如果 $i \& j=0$ 则对 $i,j$ 连边，生成图 $G$。

现在要求 $G$ 中的每个点都要按照如下规则加入集合 $S$：

1. 直接将点 $i$ 加入集合 $S$，贡献为 0；
2. 如果集合中已经存在点 $j$ 且点 $i,j$ 之间存在连边，那么将 $i$ 加入集合 $S$，贡献为 $a_i$。

求最大贡献，$n\leq 2\times10^3,a_i\leq10^9$。

CF1375G-Tree Modification

题意

给定一棵有 $n$ 个结点的树，每次操作选取 3 个点 $i,j,k$ 满足 $i,j$ 存在连边，$j,k$ 存在连边，定义一次操作为：

1. 将 $i$ 的所有出边删除。
2. 将原先除去 $j$ 外与 $i$ 存在连边的点与 $k$ 连边。
3. 连接 $i,k$ 两点。

求最小的操作次数使得树存在度为 $n-1$ 的点。

Teleport

题意

给定一个长度为 $n$ 的序列 $\{a\}$，$q$ 次询问。每次查询区间 $[l,r]$，若能选出 1 个三元组 $(a_i,a_j,a_k)$ 使得能够构成三角形，输出 Triangle，否则输出 Not triangle。注意 $i\ne j,j\ne k$，$n\leq 2\times 10^5,a_i\leq10^9$。