日记 2024.3.15：2024 年 syzx 春季训练 1
A
找出在 \(1, 2\) 周围一圈的点，挑出最远点 \(u, v\)（找不到说明 \(d_{1, 2}=1\)），判一下 \(d_{u, v}\) 与 \(d_{u, 2}\) 的关系以区分 \(\pm1\)。这样比较好看。
B
普通冒泡 \(n(n-1)/2\) 次，这题 \(n^2\)，说明每做一次操作可以浪费一次操作。
对 \(4\cdots n\) 普通冒泡，动不了就搞 \(1, 2\)。最后只剩三个数，一共六种情况，经验证，直接做都对。
C
枚举一个学生，枚举这人回答的问题，枚举和他回答相同的学生暴力验证。\(O(n^2m)\)。
发现，枚举一个学生后，如果枚举了超过 \(O(nk)\) 个学生，说明已经有一个人和你相似了（否则鸽巢原理）。然后再去枚举与这个学生相似的，暴力验证。\(O(n^2k+nm)\)。
D1
显然有 \(O(nd(n)\log n)\) 的做法。考虑你这个修改，可以拆成前后缀去询问，那个 \(\log n\) 就能精细实现干掉。
D2
\(k\) 必定是 \(n\) 的某个素因子。
你想象一下。已经有一个 \(k\)，再次划分之。
\[\dfrac{S'_{\max}}{S'_{\min}}\leq \dfrac{aS_{\max}}{aS_{\min}}=\dfrac{S_{\max}}{S_{\min}} \]（新的最大值所在的组，\(\leq\) 缩放成全部都是原来的最大值；最小值同理；然后除掉一个同样的个数。最终发现比原来还优（不劣）。）
于是 \(O(nw(n))\) 做法就出现了。
标签：2024.3,15,dfrac,syzx,2024,枚举 From： https://www.cnblogs.com/caijianhong/p/18076181