2025-11-18 NOIP模拟赛总结
liuyi0905
·
·
生活·游记
【MX-S10】梦熊 NOIP 2025 模拟赛 2 & FeOI Round 4（同步赛）
总算发挥好一次了……
---
最开始还是看 T1，感觉一点也不好做。看到要对每个点求最小时间，感觉还是跑最短路什么的，不过没想到怎么跑。硬是看了半个小时，毫无头绪，只好看 T2。
？T2 是什么鬼题目，神秘多项式求导递推求系数，一看就很复杂。刚看完题，有感觉没那么难。手搓完样例才发现错了，本来以为 $F'(x)$ 就是题目中定义的一个固定多项式。有感觉 $F'(x)$ 是像 $F(x)$ 、$G(x)$ 一样的递推式，然后发现又错了。好一会才知道 $F'(x)$ 就是求导😰
于是就比较好做了，直接开始推式子。
$$F_i(x) = G_{i - 1}(x) + G'_{i - 1}(x)$$
$$G_i(x) = F_{i - 1}(x) - F'_{i - 1}(x)$$
把他展开后一个一个算，越算到后面发现越不对劲，还以为有什么长度为 $km$ 的循环节，毕竟 $m \le 5 \times 10^3$。不过显然是什么都没有发现，而且到后面越来越麻烦，只好试着写了一个代码帮我算，不知道有没有什么神秘规律。
::::success[递推代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 305, M = 1e9 + 7;
LL n, m, f[N][N][N], g[N][N][N];
int main() {
freopen("x.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i <= m; i++)
f[0][i][i] = g[0][i][i] = 1;
for (int t = 1; t <= n; t++) {
cout << t << "\n";
for (int i = 0; i <= m; i++)
for (int j = 0; j <= m; j++) {
f[t][i][j] = g[t - 1][i][j] + (i + 1) * g[t - 1][i + 1][j];
g[t][i][j] = f[t - 1][i][j] - (i + 1) * f[t - 1][i + 1][j];
}
for (int i = 0; i <= m; i++) {
cout << "(";
for (int j = 0; j <= m; j++)
cout << f[t][i][j] << (j < m ? ", " : ") ");
}
cout << "\n";
for (int i = 0; i <= m; i++) {
cout << "(";
for (int j = 0; j <= m; j++)
cout << g[t][i][j] << (j < m ? ", " : ") ");
}
cout << "\n";
}
return 0;
}
```
::::
就输了个 `20 7`，输出来一大堆东西，看着我都头疼，不过貌似真的有这么多东西……就是用 $f_i$ 和 $g_i$ 将 $F_n(x)$ 和 $G_n(x)$ 的系数表示出来，感觉会有什么规律的。
::::info[$F_n(x), G_n(x)$ 系数表]
```
1
(1, 1, 0, 0, 0, 0, 0) (0, 1, 2, 0, 0, 0, 0) (0, 0, 1, 3, 0, 0, 0) (0, 0, 0, 1, 4, 0, 0) (0, 0, 0, 0, 1, 5, 0) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, 0, 0, 0, 0, 0) (0, 1, -2, 0, 0, 0, 0) (0, 0, 1, -3, 0, 0, 0) (0, 0, 0, 1, -4, 0, 0) (0, 0, 0, 0, 1, -5, 0) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
2
(1, 0, -2, 0, 0, 0, 0) (0, 1, 0, -6, 0, 0, 0) (0, 0, 1, 0, -12, 0, 0) (0, 0, 0, 1, 0, -20, 0) (0, 0, 0, 0, 1, 0, -30) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -2, 0, 0, 0, 0) (0, 1, 0, -6, 0, 0, 0) (0, 0, 1, 0, -12, 0, 0) (0, 0, 0, 1, 0, -20, 0) (0, 0, 0, 0, 1, 0, -30) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
3
(1, 1, -2, -6, 0, 0, 0) (0, 1, 2, -6, -24, 0, 0) (0, 0, 1, 3, -12, -60, 0) (0, 0, 0, 1, 4, -20, -120) (0, 0, 0, 0, 1, 5, -30) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -2, 6, 0, 0, 0) (0, 1, -2, -6, 24, 0, 0) (0, 0, 1, -3, -12, 60, 0) (0, 0, 0, 1, -4, -20, 120) (0, 0, 0, 0, 1, -5, -30) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
4
(1, 0, -4, 0, 24, 0, 0) (0, 1, 0, -12, 0, 120, 0) (0, 0, 1, 0, -24, 0, 360) (0, 0, 0, 1, 0, -40, 0) (0, 0, 0, 0, 1, 0, -60) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -4, 0, 24, 0, 0) (0, 1, 0, -12, 0, 120, 0) (0, 0, 1, 0, -24, 0, 360) (0, 0, 0, 1, 0, -40, 0) (0, 0, 0, 0, 1, 0, -60) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
5
(1, 1, -4, -12, 24, 120, 0) (0, 1, 2, -12, -48, 120, 720) (0, 0, 1, 3, -24, -120, 360) (0, 0, 0, 1, 4, -40, -240) (0, 0, 0, 0, 1, 5, -60) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -4, 12, 24, -120, 0) (0, 1, -2, -12, 48, 120, -720) (0, 0, 1, -3, -24, 120, 360) (0, 0, 0, 1, -4, -40, 240) (0, 0, 0, 0, 1, -5, -60) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
6
(1, 0, -6, 0, 72, 0, -720) (0, 1, 0, -18, 0, 360, 0) (0, 0, 1, 0, -36, 0, 1080) (0, 0, 0, 1, 0, -60, 0) (0, 0, 0, 0, 1, 0, -90) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -6, 0, 72, 0, -720) (0, 1, 0, -18, 0, 360, 0) (0, 0, 1, 0, -36, 0, 1080) (0, 0, 0, 1, 0, -60, 0) (0, 0, 0, 0, 1, 0, -90) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
7
(1, 1, -6, -18, 72, 360, -720) (0, 1, 2, -18, -72, 360, 2160) (0, 0, 1, 3, -36, -180, 1080) (0, 0, 0, 1, 4, -60, -360) (0, 0, 0, 0, 1, 5, -90) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -6, 18, 72, -360, -720) (0, 1, -2, -18, 72, 360, -2160) (0, 0, 1, -3, -36, 180, 1080) (0, 0, 0, 1, -4, -60, 360) (0, 0, 0, 0, 1, -5, -90) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
8
(1, 0, -8, 0, 144, 0, -2880) (0, 1, 0, -24, 0, 720, 0) (0, 0, 1, 0, -48, 0, 2160) (0, 0, 0, 1, 0, -80, 0) (0, 0, 0, 0, 1, 0, -120) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -8, 0, 144, 0, -2880) (0, 1, 0, -24, 0, 720, 0) (0, 0, 1, 0, -48, 0, 2160) (0, 0, 0, 1, 0, -80, 0) (0, 0, 0, 0, 1, 0, -120) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
9
(1, 1, -8, -24, 144, 720, -2880) (0, 1, 2, -24, -96, 720, 4320) (0, 0, 1, 3, -48, -240, 2160) (0, 0, 0, 1, 4, -80, -480) (0, 0, 0, 0, 1, 5, -120) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -8, 24, 144, -720, -2880) (0, 1, -2, -24, 96, 720, -4320) (0, 0, 1, -3, -48, 240, 2160) (0, 0, 0, 1, -4, -80, 480) (0, 0, 0, 0, 1, -5, -120) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
10
(1, 0, -10, 0, 240, 0, -7200) (0, 1, 0, -30, 0, 1200, 0) (0, 0, 1, 0, -60, 0, 3600) (0, 0, 0, 1, 0, -100, 0) (0, 0, 0, 0, 1, 0, -150) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -10, 0, 240, 0, -7200) (0, 1, 0, -30, 0, 1200, 0) (0, 0, 1, 0, -60, 0, 3600) (0, 0, 0, 1, 0, -100, 0) (0, 0, 0, 0, 1, 0, -150) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
11
(1, 1, -10, -30, 240, 1200, -7200) (0, 1, 2, -30, -120, 1200, 7200) (0, 0, 1, 3, -60, -300, 3600) (0, 0, 0, 1, 4, -100, -600) (0, 0, 0, 0, 1, 5, -150) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -10, 30, 240, -1200, -7200) (0, 1, -2, -30, 120, 1200, -7200) (0, 0, 1, -3, -60, 300, 3600) (0, 0, 0, 1, -4, -100, 600) (0, 0, 0, 0, 1, -5, -150) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
12
(1, 0, -12, 0, 360, 0, -14400) (0, 1, 0, -36, 0, 1800, 0) (0, 0, 1, 0, -72, 0, 5400) (0, 0, 0, 1, 0, -120, 0) (0, 0, 0, 0, 1, 0, -180) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -12, 0, 360, 0, -14400) (0, 1, 0, -36, 0, 1800, 0) (0, 0, 1, 0, -72, 0, 5400) (0, 0, 0, 1, 0, -120, 0) (0, 0, 0, 0, 1, 0, -180) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
13
(1, 1, -12, -36, 360, 1800, -14400) (0, 1, 2, -36, -144, 1800, 10800) (0, 0, 1, 3, -72, -360, 5400) (0, 0, 0, 1, 4, -120, -720) (0, 0, 0, 0, 1, 5, -180) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -12, 36, 360, -1800, -14400) (0, 1, -2, -36, 144, 1800, -10800) (0, 0, 1, -3, -72, 360, 5400) (0, 0, 0, 1, -4, -120, 720) (0, 0, 0, 0, 1, -5, -180) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
14
(1, 0, -14, 0, 504, 0, -25200) (0, 1, 0, -42, 0, 2520, 0) (0, 0, 1, 0, -84, 0, 7560) (0, 0, 0, 1, 0, -140, 0) (0, 0, 0, 0, 1, 0, -210) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -14, 0, 504, 0, -25200) (0, 1, 0, -42, 0, 2520, 0) (0, 0, 1, 0, -84, 0, 7560) (0, 0, 0, 1, 0, -140, 0) (0, 0, 0, 0, 1, 0, -210) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
15
(1, 1, -14, -42, 504, 2520, -25200) (0, 1, 2, -42, -168, 2520, 15120) (0, 0, 1, 3, -84, -420, 7560) (0, 0, 0, 1, 4, -140, -840) (0, 0, 0, 0, 1, 5, -210) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -14, 42, 504, -2520, -25200) (0, 1, -2, -42, 168, 2520, -15120) (0, 0, 1, -3, -84, 420, 7560) (0, 0, 0, 1, -4, -140, 840) (0, 0, 0, 0, 1, -5, -210) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
16
(1, 0, -16, 0, 672, 0, -40320) (0, 1, 0, -48, 0, 3360, 0) (0, 0, 1, 0, -96, 0, 10080) (0, 0, 0, 1, 0, -160, 0) (0, 0, 0, 0, 1, 0, -240) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -16, 0, 672, 0, -40320) (0, 1, 0, -48, 0, 3360, 0) (0, 0, 1, 0, -96, 0, 10080) (0, 0, 0, 1, 0, -160, 0) (0, 0, 0, 0, 1, 0, -240) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
17
(1, 1, -16, -48, 672, 3360, -40320) (0, 1, 2, -48, -192, 3360, 20160) (0, 0, 1, 3, -96, -480, 10080) (0, 0, 0, 1, 4, -160, -960) (0, 0, 0, 0, 1, 5, -240) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -16, 48, 672, -3360, -40320) (0, 1, -2, -48, 192, 3360, -20160) (0, 0, 1, -3, -96, 480, 10080) (0, 0, 0, 1, -4, -160, 960) (0, 0, 0, 0, 1, -5, -240) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
18
(1, 0, -18, 0, 864, 0, -60480) (0, 1, 0, -54, 0, 4320, 0) (0, 0, 1, 0, -108, 0, 12960) (0, 0, 0, 1, 0, -180, 0) (0, 0, 0, 0, 1, 0, -270) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -18, 0, 864, 0, -60480) (0, 1, 0, -54, 0, 4320, 0) (0, 0, 1, 0, -108, 0, 12960) (0, 0, 0, 1, 0, -180, 0) (0, 0, 0, 0, 1, 0, -270) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
19
(1, 1, -18, -54, 864, 4320, -60480) (0, 1, 2, -54, -216, 4320, 25920) (0, 0, 1, 3, -108, -540, 12960) (0, 0, 0, 1, 4, -180, -1080) (0, 0, 0, 0, 1, 5, -270) (0, 0, 0, 0, 0, 1, 6) (0, 0, 0, 0, 0, 0, 1)
(1, -1, -18, 54, 864, -4320, -60480) (0, 1, -2, -54, 216, 4320, -25920) (0, 0, 1, -3, -108, 540, 12960) (0, 0, 0, 1, -4, -180, 1080) (0, 0, 0, 0, 1, -5, -270) (0, 0, 0, 0, 0, 1, -6) (0, 0, 0, 0, 0, 0, 1)
20
(1, 0, -20, 0, 1080, 0, -86400) (0, 1, 0, -60, 0, 5400, 0) (0, 0, 1, 0, -120, 0, 16200) (0, 0, 0, 1, 0, -200, 0) (0, 0, 0, 0, 1, 0, -300) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
(1, 0, -20, 0, 1080, 0, -86400) (0, 1, 0, -60, 0, 5400, 0) (0, 0, 1, 0, -120, 0, 16200) (0, 0, 0, 1, 0, -200, 0) (0, 0, 0, 0, 1, 0, -300) (0, 0, 0, 0, 0, 1, 0) (0, 0, 0, 0, 0, 0, 1)
```
::::
感觉 $k_{n, i, j}$ 和 $k_{n - 1, i, j}$ 有一定的倍数关系，具体算了一下，发现 $k_{n, i, j}$ 是 $k_{j, i, j}$ 的倍数……吗？弄了一下发现不太对劲，根本没有什么规律可言。再一看比赛时间已经过半了🥱，该放弃吗？不，还是得坚持，就不信今天做不出这道题！不过还是得给其他题留足时间，打算在 $10 : 00$ 前要是还没做出来就放弃。
首先观察了一下 $k_{7, 0}$，不知道这里面的数有没有什么规律。看了看两两之间的比，居然是 $1, -6, 3, -4, 5, -2$ 和 $-1, 6, -3, 4, -5, 2$。算了算其他的数，发现也都有这样的规律！我瞬间来了精神，既然已经可以求出 $k_{n, 0}$，那 $k_n$ 的通项公式也一定不远了😲。
发现 $k_{n, i}$ 前面都有一段 $0$，且个数为 $i$，所以当作 $k_{n, i}$ 从第 $i$ 位开始计算。我感觉还是有一定的比例关系，于是设 $k_{n, i, j} = q_{i, j} k_{n, i - 1, j - i}$，立刻可以算出 $q$，而且非常有规律：
$$q_1 = \{1, 2, 3, 4, 5, 6, 7\}\\$$
$$q_2 = \{1, 3, 6, 10, 15, 21, 28\}$$
$$q_3 = \{1, 4, 10, 20, 35, 54, 82\}$$
$$\vdots$$
不过有规律的也只是 $q_1$ 和 $q_2$，之后的也完全看不出来，突然发现一个很神奇的规律：$q_i$ 不就是 $q_{i - 1}$ 的前缀和数组吗？太好了！现在离 AC 只有一步之遥了——代码。
有了规律，代码就只是看起来比较难，实际上一点也不简单。对于 $n$ 是奇数的时候，还需要交换 $f$ 和 $g$，因为 $F_n(x)$ 和 $G_n(x)$ 是交替递推的。而且 $k_{n, i, j}$ 也并非那么好算，因为中间会出现许多抵消，所以有不少 $k_{n, i, j} = 0$。不过有了之前生成的那张表，一下子就写出来了。
::::success[T2 青年晚报]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5005, M = 1e9 + 7;
LL n, m, a[N], b[N], f[N], g[N], k[N], s[N], x[N], y[N];
int main() {
// freopen("b5.in", "r", stdin);
// freopen("b.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i <= m; i++) cin >> a[i];
for (int i = 0; i <= m; i++)
cin >> b[i], n % 2 && (swap(a[i], b[i]), 1);
for (int i = x[0] = y[0] = 1; i <= m; i++) {
LL k = (i % 2 ? i : n / 2 * 2 + 2 - i);
x[i] = x[i - 1] * ((n % 2 ? (i % 2 ? 1 : -1) : (i % 2 ? -1 : 1)) * k + M) % M;
y[i] = y[i - 1] * ((n % 2 ? (i % 2 ? -1 : 1) : (i % 2 ? 1 : -1)) * k + M) % M;
}
for (int i = 0; i <= m; i++) {
!(n % 2) && i % 2 && (x[i] = y[i] = 0);
f[0] = (f[0] + x[i] * a[i] % M) % M, g[0] = (g[0] + y[i] * b[i] % M) % M;
}
iota(s, s + m + 1, 1);
for (int i = 1; i <= m; i++) {
for (int j = i; j <= m; j++) {
f[i] = (f[i] + x[j - i] * s[j - i] % M * a[j] % M) % M;
g[i] = (g[i] + y[j - i] * s[j - i] % M * b[j] % M) % M;
}
for (int j = 1; j <= m; j++) s[j] = (s[j - 1] + s[j]) % M;
}
for (int i = 0; i <= m; i++) cout << f[i] << " \n"[i == m];
for (int i = 0; i <= m; i++) cout << g[i] << " ";
return 0;
}
```
::::
稍作调试，大样例全过！😀😁😂🤣😃😄😅😆😊 简直不要太高兴，在检查了一会，直接回去看 T1。
啊啊啊啊啊 突然发现已经 $11 : 00$ 了，看样子 T1 是没有时间写了。不过还有整整一个小时，还是得在临死前努把力吧。放弃之前的歪思路，从头开始（其实是已经忘光了，T2 还是太烧脑了）
突然发现一个很重要的结论，要想走到 $d$，至少得等 $kd$ 秒拿完 $d$ 个铁锭。所以此时的最优方案应该是先把 $d - 1$ 步走完，最后跑回 $0$ 拿最后一个铁锭，再跑到 $d - 1$，铺到 $d$。可仔细一想不太对，他不一定要走 $d - 1$，说不定 $d - 2,d - 3,\cdots$ 会更优。
哎呀！我怎么就没想到呢，不就是 dp 嘛。设 $f_i$ 表示走到 $i$ 的最少时间，转移就很简单了
$$f_i = \min_{j = 1}^{i - 1}\{\max(f_j + t_2 j, k i) + t_2 j + t_1 (i - j)\}$$
马上就写了出来，哇！这出题人也太良心了吧，$\mathcal{O}(m^2)$ 有 $90$ 分？！😙 但看着还有时间，打算继续优化，毕竟这个式子看起来一点也不难求。不过当我把线段树、树状数组、算贡献等各种奇葩方法试了一遍，发现并没有那么简单。不过看着眼前这么短的式子，看着这么短的代码，我陷入了沉思🤔。
眼睛还在持续发力，你怎么知道可以用三分呢😜，我赌，我赌它是一个单谷函数，不试一下怎么知道呢。wow，大样例再次奇迹般地过了。怕他不保险，还对拍了好多组数据，毫无漏洞。
::::success[T1 寻雾启示]
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
LL t, n, k, x, y, f[N];
LL C(LL i, LL j) {
return max(f[j] + j * y, i * k) + j * (y - x) + i * x;
}
int main() {
// freopen("a2.in", "r", stdin);
// freopen("a.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> k >> x >> y;
for (LL i = 1; i <= n; i++) {
f[i] = 1e18;
LL l = -1, r = i;
for (LL o; l + 1 < r;)
o = l + r >> 1, C(i, o) <= C(i, o + 1) ? r = o : l = o;
cout << (f[i] = C(i, r)) << " ";
}
cout << "\n";
}
return 0;
}
```
::::
接下来的时间就该打 T3 T4 的暴力了，你为什么要在只有二十分钟的时候告诉我只有二十分钟了呢（逻辑清晰），看样子是写不出暴力了。听他们说 T3 非常难，暴力都写不出，但我可没那么好骗，才不信他们的鬼话呢🤨 但当我看到 T3 题面的时候就彻底相信了……
T4 暴力貌似并没有那么难，$\mathcal{O}(q n^3 \log n)$ 暴力轻轻松松，但貌似没有这一档分……只好优化成了 $\mathcal{O}(q n^3)$，再一看
> 测试点 $1 \sim 2$，满足 $n, q \le 300$。
你认真的吗，那我还有个鸡毛的分啊。突然发现可以继续优化成 $\mathcal{O}(q n^2 \log n)$，大概是勉强通过了。可写着写着才发现，我会在规定时间内求好区间，可在时限内调出好的好区间又不会了啊……我真是个人物，后来改成了 $\mathcal{O}(q n^3)$ 暴力，不知道有没有分，可居然这个纯暴力都没有调出来，也是生无可恋了。
接下来的时间就是向 zrr 保佑 T1 T2 不挂分了，那样至少还能上 $200$。
---
一分没挂，第一次上 $200$，也算是最好的一次了😀
要没有倔强的探索，死磕的精神，也许也就没有了这次的成绩，三小时的努力终究是没有付之一炬。
> 只有毅力才会使我们成功，而毅力的来源又在于毫不动摇，坚决采取为达到成功所需要的手段。——车尔尼雪夫斯基