目录
Contest Info
| 8/13 | O | - | O | - | O | O | - | O | - | O | - | O | O |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. Cat
题意：
每次询问给出\(L, R, S\)，要求找一个最长的连续区间\(l, r\)，满足\(l \oplus (l + 1) \oplus, \cdots, \oplus r <= S\)。
思路：
考虑\(4k \oplus (4k + 1) \oplus (4k + 2) \oplus (4k +3) = 0\)
那么我们枚举一下头，枚举一下尾，暴力判断一下即可。
代码：
B. Cats line up
题意：
给出\(n\)个数，问有多少个排列使得任意相邻两个数的差距小于等于\(K(1 \leq K \leq 3)\)
C. <3 numbers
题意：
令\(x\)为区间\([L, R]\)内素数个数，每次询问给出\([L, R]\)，判断下式是否成立：
\[\begin{eqnarray*}\frac{x}{R - L + 1} < \frac{1}{3}\end{eqnarray*}\]
思路：
考虑素数密度，大区间直接'Yes'
小区间暴力判断
代码：
E. Multiply
题意：
给出\(n\)个数\(a_i\)，令\(Z = a_1! \times a_2! \times \cdots \times a_n!\)
现在给出\(X, Y\)，令\(b_i = Z \times X^i\)，它想要一个最大的\(i\)，使得\(b_i \;|\; Y!\)
思路：
考虑分解\(X\)得到它的所有素因子及幂次。
然后找出其每个因子在\(\frac{Y!}{Z}\)中还剩多少个。
然后贪心拼\(X\)就可以了
代码：
F. The Answer to the Ultimate Question of Life, The Universe, and Everything.
题意：
每次询问给出\(x(0 \leq x \leq 200)\)，需要找出\(a, b, c(|a|, |b|, |c| \leq 5000)\)满足\(a^3 + b^3 + c^3 = x\)
思路：
\(x\)只有201个，可以暴力打表。
打表的时候可以枚举两维，第三维直接算。
打表代码：
H. Yuuki and a problem
题意：
给出一个序列\(a_i\)，支持两个操作：
- 将\(a_x\)改成\(y\)
- 询问最小的不能被\(a_l \cdots a_r\)里面的数表示出来的正整数
思路：
考虑没有修改操作怎么做：
主席树权值\(i\)表示\(i\)这个数的和.
然后考虑每次递增上去，假设已经能够表示出\([1, x]\)范围的数，那么我们可以将\([1, x + 1]\)范围内还未加入的数加进去。
这个可以在主席树上查。
并且这个加入次数跟斐波那契列类似，不会很多。
那么有修改，就敲个动态主席树
注意不要把vector当参数传下去，空间要给够
代码：
J. Loli, Yen-Jen, and a graph problem
题意：
给出一个完全图，要将这张图分成\(n - 1\)条路径，第\(i\)条路径的长度为\(i\)，并且一条边只能存在于一条路径中。
代码：
K. K-rectangle
题意：
给出\(n\)个点\((x_i, y_i)(x_i < x_{i + 1}, 0 < y_i)\)
现在你要找若干个矩形覆盖这些点，矩形的底边必须在\(x\)轴上，矩形之间不能有面积交，矩形的花费是\(h(w + k)\)，\(h\)为高，\(w\)为宽，\(k\)为给定参数。
求最小花费。
L. Loli, Yen-Jen, and a cool problem
题意：
给出一个Trie，每次询问给出一个\(x_i, L_i\)，问有多少个结点为起点向上跳\(L - 1\)步连成的长度为\(L\)的字符串和以\(x_i\)为起点连成的字符串相同
这里的字符在点上，不在边上
思路：
多加一个根节点，就能将点上的字符转化成边上的字符
然后Trie上建SAM，每次查找倍增跳深度最深的合法祖先，它的cnt就是答案
代码：
M. Kill the tree
题意：
给出一棵有根树，根节点为\(1\)，定义\(d(u, v)\)为\(u\)到\(v\)简单路径的长度，\(c(w) = \sum_{v \in T} d(w, v)\)，定义结点\(w\)为一棵树\(T\)的'critical point'，当且仅当\(c(w) \leq min_{u \in T} c(u)\)
现在要对于每个\(i \in [1, n]\)，要找出以\(i\)为根节点的子树中的'critical point'
思路：
猜想'critical point'就是重心。
问题转化成找重心。
我们考虑假设\(x\)的子树中的所有重心都找出来了：
- 那么\(x\)子树的重心不可能在它的轻儿子的子树中，因为选\(x\)本身肯定更优
- 并且\(x\)的重心不可能在它重儿子重心的子树中。
- 只可能在其重儿子的重心到\(x\)的路径上
暴力判断一下即可，每个点只会被判断一次。
但是这里要求输出所有可能的点，考虑重心最多只有两个，并且是连着的，那么我们找到深度最大的一个，另一个如果存在的话，那么就是它父亲，判一下即可。
代码：