2025.11.18 模拟赛

寻雾启示

序列dp 单调队列 二分

最初我想到的做法是贪心。对于 $t_1\ge t_2$，前若干个铁由于走的路程比较近，因此可以等铁刷出来之后再走。后面就是一次拿多个搭。$t_1<t_2$ 就直接等完了之后一路搭过去。但是这样子需要二分，并且细节非常多，我根本无法处理（况且我根本就不知道正确性）。

烧烤一个小时之后，我偶然发现了对于前 $90\%$ 的数据点有 $m\le 10^3$。欸，$\mathcal{O}\left(m^2\right)$ 可以拿这么多分？于是我开始考虑 DP。

DP 不需要知道最优决策点具体是哪一个，可以直接枚举后计算取最优值。设 $d{p}_i$ 表示搭 $i$ 块且最后在 $i$ 位置，所需要的最少时间。我们可以枚举之前的决策点 $j$，然后花 $t_2\times j$ 的时间返回 $0$，等待/不等待第 $i$ 块铁。这个可以通过取 $\max (d{p}_j+t_2\times j,i\times k)$ 得到。

然后重新回到 $j$ 花费 $t_2\times j$，最后搭到 $i$ 花费 $t_1\times (i-j)$。所以状态转移方程

$$d{p}_i=\underset{j=0}{\overset{i-1}{\min }}\left(\max (d{p}_j+t_2\times j,i\times k)+t_2\times j+t_1\times (i-j)\right)$$

初始 $d{p}_0=0$。现在我们就成功地获得 $90$ 分了，考虑优化转移。

不难通过定义发现 $d{p}_i$ 肯定是单调递增的，而 $t_2\times i$ 随 $i$ 增大而增大，所以 $d{p}_j+t_2\times j$ 随 $j$ 增大而增大，而 $i\times k$ 对于枚举的 $i$ 来说是定值。所以我们可以二分，求出一个分界点，这个分界点右边 $\max$ 的取值为 $d{p}_j+t_2\times j$，左边 $\max$ 的取值为 $i\times k$。

将式子展开，我们只需要知道 $i\times (k+t_1)+j\times (t_2-t_1)$ 的最大值和 $i\times t_1+j\times (2t_2-t_1)+d{p}_j$ 的最大值。红色是我们维护的内容，黑色的是定值。

• 对于 $j\times (t_2-t_1)$，根据 $t_1$ 和 $t_2$ 的大小关系选择 $0$ 或者分界点左边第一个即可（或者直接取 $\min$ 省的特殊处理）。
• 对于 $j\times (2t_2-t_1)+d{p}_j$，不难发现分界线随着 $i$ 增大而右移，所以这是一个滑动窗口。使用单调队列维护即可。

值得注意的是，由于分界线单调递增，可以单独加个指针维护，所以可以将时间复杂度缩减至 $\mathcal{O}(n)$。但是我懒得想了写的 lower_bound，时间复杂度 $\mathcal{O}\left(n{\log }_{2}n\right)$。

const LL kMaxN = 1e5 + 5;
 
LL dp[kMaxN], f[kMaxN], t, m, k, t1, t2;
deque<LL> q;
 
LL calc(LL i) {
  return dp[i] + i * (2 * t2 - t1);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> m >> k >> t1 >> t2;
    dp[0] = 0;
    f[0] = calc(0);
    q.clear();
    q.push_back(0);
    for (LL i = 1; i <= m; i++) {
      LL p = lower_bound(f, f + i, i * k) - f;
      for (; q.size() && q.front() < p; q.pop_front()) { }
      // 注意 t1 和 t2 大小关系，选择更小的那一种（0 或 p-1）
      dp[i] = min(p ? min(i * (k + t1), i * (k + t1) + (p - 1) * (t2 - t1)) : (LL)1e18, q.size() ? calc(q.front()) + i * t1 : (LL)1e18);
      for (; q.size() && calc(q.back()) >= calc(i); q.pop_back()) { }
      q.push_back(i);
      cout << dp[i] << ' ';
      f[i] = dp[i] + t2 * i;
    }
    cout << '\n';
  }
  return 0;
}

青年晚报

数学 组合数学 找规律 结论

发现这个变换有些复杂，因为每次变换 $F$ 和 $G$ 的计算方式都不同（一个加导数，一个减导数），并且每次变换之后相当于还要交换一次 $F$ 和 $G$。

$n\le 10^9$，哎呀，肯定是不能模拟的了，考虑拆贡献或矩阵加速。不过数据范围 $m\le 5000$ 肯定是不能矩阵的了，看看能不能 $\mathcal{O}(m^2)$ 拆贡献。

首先对于 $n$ 为偶数的情况，$F$ 和 $G$ 在变换 $n$ 次后就正好对应了真正的 $F$ 和 $G$，因为交换偶数次后不变，同时可能还会有什么规律等待发掘。对于 $n$ 为奇数，跑偶数的情况后再多算一次即可。

很显然，只有高位会对低位产生贡献，因为导数的 $i$ 次项取决于原函数的 $i+1$ 次项，所以我们考虑计算第 $i$ 为对第 $j$ 位（$j<i$）的贡献，暴力枚举 $(i,j)$ 正好 $\mathcal{O}(m^2)$。

打标结果如下（每行表示进行了 $2k$ 次操作之后的贡献序列，初始时 $9$ 次项为 $1$，其余为 $0$）：

0         0 0         0 0         0 0         0 0         1 
0         0 0         0 0         0 0       -72 0         1
0         0 0         0 0      3024 0      -144 0         1
0         0 0    -60480 0      9072 0      -216 0         1
0    362880 0   -241920 0     18144 0      -288 0         1
0   1814400 0   -604800 0     30240 0      -360 0         1
0   5443200 0  -1209600 0     45360 0      -432 0         1
0  12700800 0  -2116800 0     63504 0      -504 0         1
0  25401600 0  -3386880 0     84672 0      -576 0         1
0  45722880 0  -5080320 0    108864 0      -648 0         1
0  76204800 0  -7257600 0    136080 0      -720 0         1
0 119750400 0  -9979200 0    166320 0      -792 0         1
0 179625600 0 -13305600 0    199584 0      -864 0         1

首先通过模拟可以得到先加后减和先减后加得到的贡献是一样的。然后不难发现对于 $i$ 往 $j$ 的贡献，仅当 $i-j$ 为偶数的时候才不为 $0$，并且根据 $\frac{i-j}{2}$ 的奇偶性一正一负。

但是我们还是找不到系数的规律呀？从右往左看一看每列的第一不为 $0$ 的项，去掉正负后不难发现是 $9\times 8$、$9\times 8\times 7\times 6$、$9\times 8\times \cdots \times 4$，所以对于 $i$ 到 $j$ 的贡献，第一项为 $\frac{i!}{j!}$。

不过下面的项我们还是不知道规律呀？注意到它们都是第一项的倍数，那这个系数是什么呢？猜测它和组合数有关，差不多就相当于在 $n$ 量级元素当中选择 $i-j$ 的量级的元素的组合数（当前位作为导数加到低位，或者直接加过去）。

实测得到是 $\left(\begin{array}{c}n/2\\ (i-j)/2\end{array}\right)$。于是就很好搞了，预处理组合数，然后 $\mathcal{O}\left(m^2\right)$ 算贡献。

最后发现一个问题：$n$ 太大了 $n/2$ 的组合数无法处理。但是 $(i-j)/2$ 比较小，所以直接预处理 $\prod _{k=1}^{(i-j)/2}\left(\frac{n}{2}-k+1\right)$ 即可，算的时候乘上 $\left(\frac{(i-j)}{2}\right)!$ 的逆元即可。

const LL kMaxN = 1e7 + 5, kMod = 1e9 + 7;
 
LL fac[kMaxN], inv[kMaxN], hke[kMaxN], n, m;
 
LL pow(LL a, LL b) {
  LL res = 1;
  for (; b; b /= 2) {
    b % 2 && (res = res * a % kMod);
    a = a * a % kMod;
  }
  return res;
}
 
void init() {
  fac[0] = 1;
  for (LL i = 1; i < kMaxN; i++) {
    fac[i] = fac[i - 1] * i % kMod;
  }
  inv[kMaxN - 1] = pow(fac[kMaxN - 1], kMod - 2);
  for (LL i = kMaxN - 2; i >= 0; i--) {
    inv[i] = inv[i + 1] * (i + 1) % kMod;
  }
  hke[0] = 1;
  for (LL i = 1; i <= m; i++) {
    hke[i] = hke[i - 1] * (n / 2 - i + 1) % kMod;
  }
}
 
LL comb(LL n, LL m) {
  if (m > n) {
    return 0;
  }
  return hke[m] * inv[m] % kMod;
}
 
void solve(const vector<LL> &f, vector<LL> &res) {
  for (LL i = 0; i <= m; i++) {
    LL sum = f[i];
    for (LL j = i; j >= 0; j -= 2) {
      if (i - j > n) {
        break;
      }
      res[j] = (res[j] + comb(n / 2, (i - j) / 2) * sum % kMod) % kMod;
      sum = sum * j % kMod * (j - 1) % kMod;
      sum = (-sum + kMod) % kMod;
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  init();
  vector<LL> f(m + 1), g(m + 1), wyy(m + 1), zrr(m + 1);
  for (LL &i : f) {
    cin >> i;
  }
  for (LL &i : g) {
    cin >> i;
  }
  solve(f, wyy);
  solve(g, zrr);
  if (n % 2) {
    for (LL i = 0; i < m; i++) {
      wyy[i] = (wyy[i] - (i + 1) * wyy[i + 1] % kMod + kMod) % kMod;
      zrr[i] = (zrr[i] + (i + 1) * zrr[i + 1] % kMod + kMod) % kMod;
    }
    swap(wyy, zrr);
  }
  for (LL i : wyy) {
    cout << i << ' ';
  }
  cout << '\n';
  for (LL i : zrr) {
    cout << i << ' ';
  }
  return 0;
}

寻宝游戏

贪心 ST表 线段树

没写任何代码，没有什么思路，贪心暴力也不会。去看题解，发现确实是贪心，维护区间最大和严格次大值，等会看看。

呼吸之野

线段树 二分

采用的可持久化线段树+单调队列判断是否有已经满足条件的区间被包含，但是不知道为什么全 WA 了一分也没有，大分题目。