标签多项式下的文章

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$（可能是负数）。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$，其中 $n$ 为每个手环的装饰物个数，第一个手环的 $i$ 号位置装饰物亮度为 $x_i$，第二个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为：

$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

数据范围：$1 \le n \le 5 \times 10 ^4$，$1 \le a_{i} \le m \le 100$。

Siyuan

2019 年 07 月 31 日

暂无评论

「2019 Multi-University Training Contest 2」Fantastic Magic Cube

题目链接：HDU 6596

你有一个正整数 $n$ 和一个六元组集合，我们定义六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 的权值为 $\sum_{l_{x} \le x \le r_{x}, l_{y} \le y \le r_{y}, l_{z} \le z \le r_{z}} x \oplus y \oplus z$。

初始集合中只有一个元素 $(0, n - 1, 0, n - 1, 0, n - 1)$。接下来你要重复进行以下操作，直到集合的大小为 $n ^ 3$。

从集合中选择一个六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 满足 $l_{x} < r_{x}$ 或 $l_{y} < r_{y}$ 或 $l_{z} < r_{z}$。
然后你需要从 $\{ x, y, z \}$ 中选择恰好一个元素，选择元素 $k$ 的条件是 $l_{k} < r_{k}$。
- 如果你选择了 $x$，接下来你需要选择一个整数 $t \in [l_{x}, r_{x})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, t, l_{y}, r_{y}, l_{z}, r_{z})$ 和 $(t +1, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
- 如果你选择了 $y$，接下来你需要选择一个整数 $t \in [l_{y}, r_{y})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, t, l_{z}, r_{z})$ 和 $(l_{x}, r_{x}, t + 1, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
- 如果你选择了 $z$，接下来你需要选择一个整数 $t \in [l_{z}, r_{z})$，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除，将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, t)$ 和 $(l_{x}, r_{x}, l_{y}, r_{y}, t + 1, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。

请你求出可以获得的最大权值，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le n \le 10 ^ 6$，$1 \le \sum n \le 3 \times 10 ^ 6$。

Siyuan

2019 年 07 月 29 日

暂无评论