2025.7.30 模拟赛

建筑升级

序列dp

首先看到 $1\le n,m\le 1000$ 就很不能让人不想到 $\mathcal{O}(nm)$ 的 dp。dp 状态中，第一位表示长度为 $i$ 的建筑前缀是必须的，那么第二维是什么呢？由于最终获得的额外分数和所有建筑的最小级别有关系，因此第二维就存前缀中所有建筑中最低的级别。

设 $d{p}_{i,j}$ 表示在前 $i$ 个建筑中，等级最小为 $j$，最多能得多少分。那么对于新的一个建筑，假设我们选择让这个建筑升级到 $k$ 级，那么有以下两种情况：

• 如果 $k\ge j$，那么最低等级 $j$ 不会改变；
• 如果 $k<j$，那么最低等级 $j$ 会变成 $k$。

因此假设当前转移到 $d{p}_{i,j}$，那么有两种方式，一种是从最小值比当前大的状态，但是当前选择的等级就是 $j$ 的转移；另一种是最小值和当前一样，那么当前的等级就可以是任意比之前最小值大的而等级。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1005;
 
LL a[kMaxN][kMaxN], dp[kMaxN][kMaxN], d[kMaxN], t, n, m, ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    for (LL i = 1; i <= n; i++) {
      for (LL j = 1; j <= m; j++) {
        cin >> a[i][j];
        a[i][j] += a[i][j - 1];
      }
    }
    for (LL i = 0; i <= m; i++) {
      cin >> d[i];
      if (i >= 1) {
        d[i] += d[i - 1];
      }
    }
    fill(dp[0], dp[0] + m, -1e18);
    dp[0][m] = 0;
    for (LL i = 1; i <= n; i++) {
      for (LL j = m, pre = -1e18, mx = a[i][j]; j >= 0; j--) {
        mx = max(mx, a[i][j]);
        dp[i][j] = max(dp[i - 1][j] + mx, pre + a[i][j]);  // 最低等级不变或降低最低等级
        pre = max(pre, dp[i - 1][j]);
      }
    }
    ans = -1e18;
    for (LL i = 0; i <= m; i++) {
      ans = max(ans, dp[n][i] + d[i]);
    }
    cout << ans << '\n';
  }
  return 0;
}

快速蜗蜗变换

状压dp 枚举 集合 位运算

最开始我想到的是 01 trie，但是后面发现不能考虑到所有的情况。

最后还是写了个子集枚举，即对于每个 $i$ 枚举 $i$ 的二进制的子集，然后把 $a_i$ 和 $b_i$ 存入所有 $i$ 的子集的值中间，并且分别取最大、最小值，然后倒序枚举 $i$，把之前的最大、最小 $a,b$ 值取出来以四种情况中取最大值，然后再做一个后缀 $\max$，累加即可。

正确性证明：如果 $k\subset i$ 且 $k\subset j$，那么必然有 $k\subset (i\cap j)$，因为 $k$ 有的每一个 $1$ 都在 $i$ 和 $j$ 里面出现过，此时 $k\le i\&j$，然后我们再做一个后缀和就可以覆盖所有的 $i\&j\ge k$ 的情况。

时间复杂度高达 $\mathcal{O}\left(\sum _{i=1}^n{2}^{\text{popcount}(i)}\right)$，当 $n=2\times 10^5$ 时大约是 $2\times 10^8$ 左右，但是可以直接卡过。其实正解和这个区别不大，这个是枚举出所有的子集，正解是每次从已有的 $1$ 中间掏去一个。

#include <iostream>
#include <algorithm>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kMod = 998244353;
 
LL a[kMaxN], b[kMaxN], mxa[kMaxN], mxb[kMaxN], mna[kMaxN], mnb[kMaxN], t, n, ans, mx;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (LL i = 0; i < n; i++) {
      cin >> a[i];
    }
    for (LL i = 0; i < n; i++) {
      cin >> b[i];
      mna[i] = mnb[i] = 1e18;
      mxa[i] = mxb[i] = -1e18;
    }
    for (LL i = 0; i < n; i++) {
      for (LL x = i; x; x = (x - 1) & i) {
        mxa[x] = max(mxa[x], a[i]);
        mna[x] = min(mna[x], a[i]);
        mxb[x] = max(mxb[x], b[i]);
        mnb[x] = min(mnb[x], b[i]);
      }
      mxa[0] = max(mxa[0], a[i]);
      mna[0] = min(mna[0], a[i]);
      mxb[0] = max(mxb[0], b[i]);
      mnb[0] = min(mnb[0], b[i]);
    }
    ans = 0;
    mx = -1e18;
    for (LL i = n - 1; i >= 0; i--) {
      mx = max(mx, max(
                    max(mna[i] * mnb[i], mna[i] * mxb[i]),
                    max(mxa[i] * mnb[i], mxa[i] * mxb[i])));
      ans = ((ans + mx) % kMod + kMod) % kMod;
    }
    cout << ans << '\n';
  }
  return 0;
}

互不相同

贪心

我使用的是暴力。

对于子任务 3，可以采用迭代加深搜索，由于答案大概在 $\frac{n}{2}$ 左右，因此最多也就迭代 $4$ 次，单次瞎选一个区间，然后加一个特别大且特殊的值（我是 $4\times 10^9\times 2^x$，$x$ 是当前深度，二进制保证不会重复），如果满足条件就可以退出了。这个搜索可以帮助我们找出子任务 1、2 的规律。

对于子任务 1，全部 $a_i$ 都是 $1$，使用我们的搜索不难得到

$$\{\begin{array}{ll}1& \text{if}n=1\\ \lceil \frac{n}{2}\rceil & \text{if}n>1\end{array}$$

对于子任务 2，我的式子猜错了，导致 wa 最后一个子测试点。

运货

平衡树

我的思路是错的。

我最开始想的是二分，二分出一个答案进行 $\mathcal{O}(n)$ 判断，时间复杂度 $\mathcal{O}(n^2{\log }_{2}V)$，但是答案根本没有单调性（如 6 3 2， 如果承重为 $5$ 可以带 $2$ 个，但是当承重为 $6$ 时只能带 $1$ 个），于是趋势。

总结

分数 $100+100+23+0=223$。

下次写题目的时候不能看着好像可以二分就写二分，应该仔细判断单调性。然后更改做题侧重点，应该把重点放在第二题和第三题上而非第四题。