白哥很黑模拟赛总结

DFbd · 2025-10-04 15:21:17 · 个人记录

我又没开long long！

预期：100 + 100 + 24 + 40

实际：100 + 100 + 4 + 32

T1

很快就想到了，但是写了1.5h。

题意：有一个长度为 n 的排列 a。可以选择一个 2 \le x \le n−1，并将 a_{x−1},a_x,a_{x+1} 替换为 a_{x+1},a_{x−1},a_x。求能否利用上述操作将整个排列升序排序。

正常人的想法是逆序对，但我不是正常人，所以我想到了链表。

可以发现，只要我从 n 到 3 一个个往后移，剩下 1 和 2 是移不了的。

那么我就判断一下 1 在 2 前还是后。

暴力移动是 \mathcal{O(n)} 的，总复杂度是 \mathcal{O(n^2)}，所以我们来看看如何 \mathcal{O(1)} 移动。

我们发现将 a_x 移动到 y，只需要先把 a_{x-1} 移动到 y - 1，就可以直接移动了，剩下的顺序不变。

于是可以用链表维护，注意当 x = 1 时，需要先特殊移动一次，把 a_x 移动到第二个，就可以正常操作。

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e6 + 5;

int t, n, a[kMaxN], pre[kMaxN], nxt[kMaxN], ed;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      pre[a[i]] = a[i - 1];
      nxt[a[i - 1]] = a[i];
    }
    nxt[a[n]] = 0;
    ed = a[n];
    for (int i = n; i >= 3; i--) {
      if (!pre[i]) {
        int x = nxt[nxt[i]];
        pre[i] = x;
        nxt[nxt[i]] = nxt[nxt[nxt[i]]];
        pre[nxt[x]] = nxt[i];
        nxt[x] = i;
        pre[x] = 0;
      }
      if (i == ed) {
        ed = pre[ed];
        continue;
      }
      nxt[ed] = pre[i];
      nxt[pre[pre[i]]] = nxt[i];
      pre[nxt[i]] = pre[pre[i]];
      nxt[i] = 0;
      pre[pre[i]] = ed;
      ed = pre[i];
    }
    cout << (pre[2] ? "Yes\n" : "No\n");
  }
  return 0;
}

T2

数学爽题，很好玩，写了1.5h。

题意：一个数，初始为 1，可以花费 c_1 把数加 x_1，也可以花费 c_2 把数乘 x_2，求把数变为 n 的最小花费，无解输出 -1。

先特判一下 x_2 = 1，不然会炸。这时乘操作无效，直接看加操作即可。

不难发现，乘的次数只有 \mathcal{O(\log n)}，于是枚举乘的次数 i。

这个 i 的上限建议算一下 \log_{x_2}n，不然数字会超级大。

先处理一下初始的 1，显然最后这个 1 会变成 {x_2}^i，所以先把 n = n - {x_2}^i。

而加操作只有 x_1，所以 n 必须是 x_1 的倍数，否则无解。

接下来我们再把 n = \frac{n}{x_1}，现在一次加操作，就相当于给一个 x_2 进制数的一位加 1。

那么把 x_2 进制下的 n 的后 i + 1 位加起来，再加上剩下的位转化成十进制的数，即为加操作次数。

写完出去吃个包子，剩下55min，足够了。

#include <bits/stdc++.h>

#define int long long

using namespace std;

int c, t, n, x1, c1, x2, c2;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (cin >> c >> t; t; t--) {
    cin >> n >> x1 >> c1 >> x2 >> c2;
    if (x2 == 1) {
      n--;
      cout << (n % x1 ? -1 : (n / x1) * c1) << "\n";
      continue;
    }
    int mn = 1e18, lim = 0;
    for (__int128_t i = 1; i <= n; i *= x2, lim++);
    for (int i = 0, x = n, y = 1; i < lim; i++, y *= x2, x = n) {
      int sum = 0, ans = 0;
      ans = i * c2;
      x -= y;
      if (x % x1)
        continue;
      x /= x1;
      int ty = y;
      for (int j = i; j >= 0; j--) {
        sum += x / ty;
        x %= ty;
        ty /= x2;
      }
      mn = min(mn, ans + sum * c1);
    }
    cout << (mn == 1e18 ? -1 : mn) << "\n";
  }
  return 0;
}

T3

没开二度。

当时我竟然没有预料到它的答案会那么大，明明有平方。

预估24pts，实际4pts，开long long后40pts写完人类智慧100pts。

题意：给定一个长度为 n 的序列 a_1,a_2,\dots,a_n，问将序列 a 划分成若干个连续子段的最大值减最小值的平方的最大值。

显然最优方案的每个子段两端必然是最大值和最小值，所以 n^2 做法就很显然了。

转移方程可以用李超线段树维护。

但是我不会，所以这里有另外一种能过的方法。

经过同学的实验，判掉特殊性质（单增），每个数只往前找 18 个就可以过（虽然可以被卡）。

所以，我们充分发扬人类智慧：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int kMaxN = 1e6 + 5;

int n, a[kMaxN], f[kMaxN];

signed main() {
  cin >> n;
  int flag = 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] < a[i - 1])
      flag = 0;
  }
  if (flag)
    cout << (a[n] - a[1]) * (a[n] - a[1]);
  else {
    for (int i = 1; i <= n; i++)
      for (int j = max(1ll, i - 20); j <= i; j++)
        f[i] = max(f[i], f[j - 1] + (a[i] - a[j]) * (a[i] - a[j]));
    cout << f[n];
  }
  return 0;
}

T4

数据又骗人，本来20个测试点，每个有5pts，8个就有40pts，结果又有25个，只剩32pts。

题意：一棵 n 个点的树，加了 m 条边，求把每个点染 k 种颜色之一，且相邻两点颜色不同的染色方案数。

当 m = 0 时，显然除了根节点，剩下的都有 k - 1 种情况，根节点有 k 种情况，答案就是 (k - 1)^{n - 1} \times k。

总结

我已经连续两次没开long long了🤬

上一次我吸取了同学的教训，于是我在今天空间足够的情况下 #define int long long，但是只有T2、4开了。

下次打框架就加上，我已经黑化了😈