专栏文章

白哥很黑模拟赛总结

DDFbd
个人记录参与者 1已保存评论 0

文章操作

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

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

我又没开long long！

预期：100 + 100 + 24 + 40
实际：100 + 100 + 4 + 32

T1

很快就想到了，但是写了1.5h。
题意：有一个长度为 nn 的排列 aa。可以选择一个 2≤x≤n−12 \le x \le n−1，并将 ax−1,ax,ax+1a_{x−1},a_x,a_{x+1} 替换为 ax+1,ax−1,axa_{x+1},a_{x−1},a_x。求能否利用上述操作将整个排列升序排序。
正常人的想法是逆序对，但我不是正常人，所以我想到了链表。
可以发现，只要我从 nn 到 33 一个个往后移，剩下 11 和 22 是移不了的。
那么我就判断一下 11 在 22 前还是后。
暴力移动是 O(n)\mathcal{O(n)} 的，总复杂度是 O(n2)\mathcal{O(n^2)}，所以我们来看看如何 O(1)\mathcal{O(1)} 移动。
我们发现将 axa_x 移动到 yy，只需要先把 ax−1a_{x-1} 移动到 y−1y - 1，就可以直接移动了，剩下的顺序不变。
于是可以用链表维护，注意当 x=1x = 1 时，需要先特殊移动一次，把 axa_x 移动到第二个，就可以正常操作。
CPP
#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。
题意：一个数，初始为 11，可以花费 c1c_1 把数加 x1x_1，也可以花费 c2c_2 把数乘 x2x_2，求把数变为 nn 的最小花费，无解输出 -1。
先特判一下 x2=1x_2 = 1，不然会炸。这时乘操作无效，直接看加操作即可。
不难发现，乘的次数只有 O(log⁡n)\mathcal{O(\log n)}，于是枚举乘的次数 ii。
这个 ii 的上限建议算一下 log⁡x2n\log_{x_2}n，不然数字会超级大。
先处理一下初始的 11，显然最后这个 11 会变成 x2i{x_2}^i，所以先把 n=n−x2in = n - {x_2}^i。
而加操作只有 x1x_1，所以 nn 必须是 x1x_1 的倍数，否则无解。
接下来我们再把 n=nx1n = \frac{n}{x_1}，现在一次加操作，就相当于给一个 x2x_2 进制数的一位加 11。
那么把 x2x_2 进制下的 nn 的后 i+1i + 1 位加起来，再加上剩下的位转化成十进制的数，即为加操作次数。
写完出去吃个包子，剩下55min，足够了。
CPP
#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。
题意：给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\dots,a_n，问将序列 aa 划分成若干个连续子段的最大值减最小值的平方的最大值。
显然最优方案的每个子段两端必然是最大值和最小值，所以 n2n^2 做法就很显然了。
转移方程可以用李超线段树维护。
但是我不会，所以这里有另外一种能过的方法。
经过同学的实验，判掉特殊性质（单增），每个数只往前找 1818 个就可以过（虽然可以被卡）。
所以，我们充分发扬人类智慧：
CPP
#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。
题意：一棵 nn 个点的树，加了 mm 条边，求把每个点染 kk 种颜色之一，且相邻两点颜色不同的染色方案数。
当 m=0m = 0 时，显然除了根节点，剩下的都有 k−1k - 1 种情况，根节点有 kk 种情况，答案就是 (k−1)n−1×k(k - 1)^{n - 1} \times k。

总结

我已经连续两次没开long long了🤬
上一次我吸取了同学的教训，于是我在今天空间足够的情况下 #define int long long，但是只有T2、4开了。
下次打框架就加上，我已经黑化了😈

评论

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

正在加载评论...