专栏文章

2025-11-18 NOIP模拟赛总结

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5rgfd
此快照首次捕获于
2025/12/01 21:01
3 个月前
此快照最后确认于
2025/12/01 21:01
3 个月前
查看原文

【MX-S10】梦熊 NOIP 2025 模拟赛 2 & FeOI Round 4（同步赛）

总算发挥好一次了……
100+100+0+0=200100 + 100 + 0 + 0 = 200，在洛谷应该是能进第一版了吧。都怪 cutezrr，T3 T4暴力都没写出来😓 不过没挂分，还是比较好的。眼睛也是发力了好吧，T1 T2 全是大眼观察法做出来的。
最开始还是看 T1，感觉一点也不好做。看到要对每个点求最小时间，感觉还是跑最短路什么的，不过没想到怎么跑。硬是看了半个小时，毫无头绪，只好看 T2。
？T2 是什么鬼题目，神秘多项式求导递推求系数，一看就很复杂。刚看完题，有感觉没那么难。手搓完样例才发现错了，本来以为 F′(x)F'(x) 就是题目中定义的一个固定多项式。有感觉 F′(x)F'(x) 是像 F(x)F(x) 、G(x)G(x) 一样的递推式，然后发现又错了。好一会才知道 F′(x)F'(x) 就是求导😰
于是就比较好做了，直接开始推式子。
Fi(x)=Gi−1(x)+Gi−1′(x)F_i(x) = G_{i - 1}(x) + G'_{i - 1}(x) Gi(x)=Fi−1(x)−Fi−1′(x)G_i(x) = F_{i - 1}(x) - F'_{i - 1}(x)
把他展开后一个一个算，越算到后面发现越不对劲，还以为有什么长度为 kmkm 的循环节，毕竟 m≤5×103m \le 5 \times 10^3。不过显然是什么都没有发现，而且到后面越来越麻烦，只好试着写了一个代码帮我算，不知道有没有什么神秘规律。
递推代码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，输出来一大堆东西，看着我都头疼，不过貌似真的有这么多东西……就是用 fif_i 和 gig_i 将 Fn(x)F_n(x) 和 Gn(x)G_n(x) 的系数表示出来，感觉会有什么规律的。
Fn(x),Gn(x)F_n(x), G_n(x) 系数表CPP
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)
感觉 kn,i,jk_{n, i, j} 和 kn−1,i,jk_{n - 1, i, j} 有一定的倍数关系，具体算了一下，发现 kn,i,jk_{n, i, j} 是 kj,i,jk_{j, i, j} 的倍数……吗？弄了一下发现不太对劲，根本没有什么规律可言。再一看比赛时间已经过半了🥱，该放弃吗？不，还是得坚持，就不信今天做不出这道题！不过还是得给其他题留足时间，打算在 10:0010 : 00 前要是还没做出来就放弃。
首先观察了一下 k7,0k_{7, 0}，不知道这里面的数有没有什么规律。看了看两两之间的比，居然是 1,−6,3,−4,5,−21, -6, 3, -4, 5, -2 和 −1,6,−3,4,−5,2-1, 6, -3, 4, -5, 2。算了算其他的数，发现也都有这样的规律！我瞬间来了精神，既然已经可以求出 kn,0k_{n, 0}，那 knk_n 的通项公式也一定不远了😲。
发现 kn,ik_{n, i} 前面都有一段 00，且个数为 ii，所以当作 kn,ik_{n, i} 从第 ii 位开始计算。我感觉还是有一定的比例关系，于是设 kn,i,j=qi,jkn,i−1,j−ik_{n, i, j} = q_{i, j} k_{n, i - 1, j - i}，立刻可以算出 qq，而且非常有规律：
q1={1,2,3,4,5,6,7}q_1 = \{1, 2, 3, 4, 5, 6, 7\}\\ q2={1,3,6,10,15,21,28}q_2 = \{1, 3, 6, 10, 15, 21, 28\} q3={1,4,10,20,35,54,82}q_3 = \{1, 4, 10, 20, 35, 54, 82\} ⋮\vdots
不过有规律的也只是 q1q_1 和 q2q_2，之后的也完全看不出来，突然发现一个很神奇的规律：qiq_i 不就是 qi−1q_{i - 1} 的前缀和数组吗？太好了！现在离 AC 只有一步之遥了——代码。
有了规律，代码就只是看起来比较难，实际上一点也不简单。对于 nn 是奇数的时候，还需要交换 ff 和 gg，因为 Fn(x)F_n(x) 和 Gn(x)G_n(x) 是交替递推的。而且 kn,i,jk_{n, i, j} 也并非那么好算，因为中间会出现许多抵消，所以有不少 kn,i,j=0k_{n, i, j} = 0。不过有了之前生成的那张表，一下子就写出来了。
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:0011 : 00 了，看样子 T1 是没有时间写了。不过还有整整一个小时，还是得在临死前努把力吧。放弃之前的歪思路，从头开始（其实是已经忘光了，T2 还是太烧脑了）
突然发现一个很重要的结论，要想走到 dd，至少得等 kdkd 秒拿完 dd 个铁锭。所以此时的最优方案应该是先把 d−1d - 1 步走完，最后跑回 00 拿最后一个铁锭，再跑到 d−1d - 1，铺到 dd。可仔细一想不太对，他不一定要走 d−1d - 1，说不定 d−2,d−3,⋯d - 2,d - 3,\cdots 会更优。
哎呀！我怎么就没想到呢，不就是 dp 嘛。设 fif_i 表示走到 ii 的最少时间，转移就很简单了
fi=min⁡j=1i−1{max⁡(fj+t2j,ki)+t2j+t1(i−j)}f_i = \min_{j = 1}^{i - 1}\{\max(f_j + t_2 j, k i) + t_2 j + t_1 (i - j)\}
马上就写了出来，哇！这出题人也太良心了吧，O(m2)\mathcal{O}(m^2) 有 9090 分？！😙 但看着还有时间，打算继续优化，毕竟这个式子看起来一点也不难求。不过当我把线段树、树状数组、算贡献等各种奇葩方法试了一遍，发现并没有那么简单。不过看着眼前这么短的式子，看着这么短的代码，我陷入了沉思🤔。
眼睛还在持续发力，你怎么知道可以用三分呢😜，我赌，我赌它是一个单谷函数，不试一下怎么知道呢。wow，大样例再次奇迹般地过了。怕他不保险，还对拍了好多组数据，毫无漏洞。
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 暴力貌似并没有那么难，O(qn3log⁡n)\mathcal{O}(q n^3 \log n) 暴力轻轻松松，但貌似没有这一档分……只好优化成了 O(qn3)\mathcal{O}(q n^3)，再一看
测试点 1∼21 \sim 2，满足 n,q≤300n, q \le 300。
你认真的吗，那我还有个鸡毛的分啊。突然发现可以继续优化成 O(qn2log⁡n)\mathcal{O}(q n^2 \log n)，大概是勉强通过了。可写着写着才发现，我会在规定时间内求好区间，可在时限内调出好的好区间又不会了啊……我真是个人物，后来改成了 O(qn3)\mathcal{O}(q n^3) 暴力，不知道有没有分，可居然这个纯暴力都没有调出来，也是生无可恋了。
接下来的时间就是向 zrr 保佑 T1 T2 不挂分了，那样至少还能上 200200。
一分没挂，第一次上 200200，也算是最好的一次了😀
要没有倔强的探索，死磕的精神，也许也就没有了这次的成绩，三小时的努力终究是没有付之一炬。
只有毅力才会使我们成功，而毅力的来源又在于毫不动摇，坚决采取为达到成功所需要的手段。——车尔尼雪夫斯基

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...