在讨论《这个题是NP-Hard的吗》回复：

@[N_z_](luogu://user/320087)怎么规约呢

好像找不到真多项式做法，又不知道怎么证明

Java 组题当然要用 Java 做。 发现只有 $O\!\left(n^3m^3\right)$ 种状态（枚举小人、箱子、终点的位置，各 $O\!\left(nm\right)$ 种，且小人不与箱子重叠），其中如果三者皆不重叠则计入答案。不妨从终点开始反向搜索有多少合法位置，拉箱子的逆过程为推箱子。对于每一个状态，至…

由于 $a_i,b_i$ 为正，获得奖金最多的大臣一定是第 $n$ 位大臣。发现答案为 $\max_{i=1}^n\!\left(\sum_{j=1}^ia_j+\sum_{j=i}^nb_j\right)$ 考虑交换相邻两项会产生什么影响，不妨设这两项为 $a_t,a_{t+1}$。max 式子中只有 $i=t$ 和…

在讨论《关于这个题》回复：

经过对 $6$ 的阶乘种情况暴力判断发现只要六个 $a,b$ 全不相等，这个不等式就有传递性 所以只需要强行让这些 $a,b$ 不相等，然后排序即可

在讨论《建议去掉“区间DP”标签》回复：

现在标签去掉了，但是用这个标签仍然能搜到这题，就很奇怪

本题已经移除了 区间DP 标签，但是使用这个标签仍然会搜到这题

在讨论《为什么题解中没有对操作2和操作4的特判啊》回复：

因为没有特殊性，用同样的方法不会出问题

在讨论《每次1/2随机合并的Treap复杂度是不是错的》回复：

@[aaalys](luogu://user/902158) 最坏插入序列随机合并树高期望是 $\Theta(n)$，随机权值不是

在讨论《每次1/2随机合并的Treap复杂度是不是错的》回复：

@[aaalys](luogu://user/902158) 但是树高是最坏 $\Theta\!\left(n\right)$ 的，怎么解释

按照这种方式不断向右合并单节点的话树高是期望 $O\!\left(n\right)$ 的（每次合并至少有 $\frac12$ 的概率让树高 $+1$），这样之后操作的复杂度是均摊 $O\!\left(\log n\right)$ 还是就是 $O\!\left(n\right)$

前置知识：乐理（音程），差分，剩余系，字符串匹配（KMP） 不妨使用 A 以上的半音数来代表音高，例如 $A\sharp=1,D\flat=4$ 等。此时自然小调音阶 ABCDEFG 可以被表示为 $0,2,3,5,7,8,10$（可以通过图片或者表格处理出来）。以这个规则将旋律转换为数组。 两个旋律相似当且仅当构成的…

### 思路 可以用累乘的方式 $O\left(n^2\right)$ 算出每一个子序列的乘积。 ### 算法 具体的，固定左端点，不断扩张右端点并且乘当前值，并更新答案即可。 注意到答案最多可为 ${999999}^{100}$，需要使用高精度。只需要实现一个数乘和大小比较即可。复杂度 $O(n^3)$，对于通过本题…

在讨论《本地未开O2，跑了6.5-6.9s平均6.7》回复：

那为什么不开 O2 呢）

在讨论《千万别开O2》回复：

我本机程序关了 O2 跑十秒，开 O2 不到 1 秒

在讨论《千万别开O2》回复：

这题默认 O2 你开不开都是 O2 的，只是你这点正好侥幸过了或者不幸卡掉了

在讨论《建议升橙》回复：

set 换成 vector，于是这就是 string 板子题 另外这种深度的 set 考察并不足以提升难度等级

在讨论《本题难度建议总结》回复：

紫紫紫紫紫紫紫紫紫紫

我用一堆 $vector$ 存状态被卡常出翔了，改一维数组直接过

如果是官方的，是否有公开途径？

在讨论《并查集复杂度疑问》回复：

@[MarSer020](/user/475112) 但是 Tarjan 算法流程只能把父亲设为根啊，怎么保证并查集的复杂度呢

1. 按序合并（编号大的往编号小的上合并）+ 路径压缩，复杂度是 $O(n\log n)$ 还是 $O(n\alpha(n))$？ 1. 朴素 Tarjan 离线 LCA 时间复杂度为什么是 $O(n\alpha(n))$？Wiki 没找到解释

在讨论《20分求调，悬关》回复：

@[awdfkewd](/user/1420919) 先读题吧。。。这题不是让你判断 $n$ 是不是 $k$ 阶天才数

在讨论《20分求调，悬关》回复：

你题意都理解错了。。。

在讨论《不懂就问，关于三级模拟》回复：

@[AllenJYL](/user/459170) 一个非负数x的平方等于a，则x叫作a的算术平方根。 然后呢，有什么问题吗

求一个正整数的算术平方根，怎么个枚举法啊。。。 正整数的算术平方根又不一定是正整数啊。。。

在讨论《本题有误。》回复：

@[Luka__Modric](/user/839893) 公元 1582 年之前格里高利历并没有推行，儒略历只有 4 年一闰的规则。

由常识可得，公元 1500 年，公元 100 年显然为闰年，但是题解以及数据都没考虑到这一点。

由常识可得，公元 1500 年，公元 100 年显然为闰年，但是题解以及数据都没考虑到这一点。

算法：依次朴素 $O\left(\sqrt n\right)$ 判断质数。 显然时间复杂度是 $O\left(n\sqrt n\right)$，稍加分析可以得到取不到这个上界，那么有没有方法计算出这个算法的时间复杂度紧确界呢?