「NOI2005」瑰丽华尔兹
题目链接题目大意现在有一个 $n\times m$ 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。 其中 $1 \leq n,m \leq 200$,区间个数 $k \l...
题目链接题目大意现在有一个 $n\times m$ 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。 其中 $1 \leq n,m \leq 200$,区间个数 $k \l...
题目链接题意有长度为 n 的序列，定义一个集合的代价是$(MAX-MIN)^2$，要求你找出 m 个集合，在满足下面图片的限制的情况下，使得总代价最小。 多组数据，每组数据 $n \leq 10^4,m \leq 5 \times 10^3$，保证答案在 int 范围内。题解观察题目 发现让你选取 M 个集合使得代价最小。 首先一个观察是，取得代价最小的方案一定是按照排序后按顺序取的，并且...
题目描述We have a convex polygon in the XY plane. The vertices of the polygon are the points (x[0], y[0]), (x[1], y[1]), ... in clockwise order. You are given the vector s x and y.In order to make the ...
题目链接题目描述题目大意：给你前 $alphabet$ 个小写字母组成的字符集，以及 $n$ 个单词，定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$，其中 $Taboo[i]$ 是第 $i$ 个单词（禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数）。现在给定一个长度 $len$，求随机一个用字符集生成的长度为 $len$ 的...
题目链接题目大意给定一棵树，每个点有一个权值，每次询问给你一些链，求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。题解首先我们考虑如何做一条链的情况。发现我们可以分块，对于每一个块都维护一下这个块中所有的权值的集合，只需要用能求并的结构（例如 bitset）维护就可以了。查询的时候仍然是整块暴力边角二分。 然后我们考虑放在树上：我们可以随机钦定 $\sqrt{n}$ 个...