contest1 题解
A. 序列分割容易发现分割顺序并不影响答案。因为你确定下来最终状态后，设每段的和分别为 $x_1,x_2,\ldots x_m$，发现你这个分割实际上是统计了 $\prod_{i < j} x_ix_j$。（每次都是统计跨过某个点的所有对，然后递归）所以我们可以设计一个 dp：$f_{i,j}$ 表示分了 $i$ 段，第 $i$ 次分的位置是 $j$ 的答案。记前缀和为 $s_i$，转...
A. 序列分割容易发现分割顺序并不影响答案。因为你确定下来最终状态后，设每段的和分别为 $x_1,x_2,\ldots x_m$，发现你这个分割实际上是统计了 $\prod_{i < j} x_ix_j$。（每次都是统计跨过某个点的所有对，然后递归）所以我们可以设计一个 dp：$f_{i,j}$ 表示分了 $i$ 段，第 $i$ 次分的位置是 $j$ 的答案。记前缀和为 $s_i$，转...
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
题目大意维护一个序列 支持以下操作：序列末尾插入一个向量$(x,y)$序列末尾删除一个向量询问区间 $[l,r]$ 中和向量 $(u,v)$ 叉积的最大值（设 $(x,y) \in [l,r]$,要求 $(u,v)\times(x,y)$ 最大）$n \leq 5\times 10^5$题解看到叉积 先想到斜率优化。给出 $(u,v)$，要求最大化 $uy-vx$。设 $b=uy-vx$ 变...
题目链接题意有长度为 n 的序列，定义一个集合的代价是$(MAX-MIN)^2$，要求你找出 m 个集合，在满足下面图片的限制的情况下，使得总代价最小。 多组数据，每组数据 $n \leq 10^4,m \leq 5 \times 10^3$，保证答案在 int 范围内。题解观察题目 发现让你选取 M 个集合使得代价最小。 首先一个观察是，取得代价最小的方案一定是按照排序后按顺序取的，并且...