2024/10/09 模拟赛总结

\(100+40+20+8=168\)，拿到了大众分，至少没挂分吧

#A. 矩阵交换

一个 \(m\) 维偏序，可以使用 \(m-1\) 维树状数组解决

以第 \(i\) 作为第 \(i\) 关键字，进行排序，这样一定最优。排完之后直接判断是否满足条件即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 100 + 5;

struct P {
  int e[kMaxN];
};

int t, n, m;
bool flag = 1;
P a[kMaxN];

void pr(bool pr) {
  cout << (pr ? "YES" : "NO") << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("exchange.in", "r", stdin), freopen("exchange.out", "w", stdout);
  for (cin >> t; t; t--, flag = 1) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        cin >> a[i].e[j];
      }
    }
    sort(a + 1, a + n + 1, [](P l, P r) {
      for (int i = 1; i <= m; i++) {
        if (l.e[i] != r.e[i]) {
          return l.e[i] < r.e[i];
        }
      }
      return 0 == 1;
    });
    for (int j = 1; j <= m; j++) {
      for (int i = 2; i <= n; i++) {
        if (a[i].e[j] < a[i - 1].e[j]) {
          flag = 0;
          break;
        }
      }
      if (!flag) {
        break;
      }
    }
    pr(flag);
  }
  return 0;
}

#B. 砖块摆放/原题

定义 A 为 \(0\)，B 为 \(1\)，C 为 \(2\)

所以可以把每一个值 \(d\) 被其下面两个数 \(d_1,d_2\) 表示：

那么最顶层就可以表示成这样：

可以发现这很像杨辉三角，但是模数只有 \(3\)，没有逆元。只能用 Lucas 解决

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5;

int t, n, a[kMaxN], ans;
char ch;

int C(int p, int k, int ret = 1) {
  if (p < k) {
    return 0;
  }
  for (int i = p - k + 1; i <= p; ret *= i, i++);
  for (int i = 1; i <= k; ret /= i, i++);
  return ret % 3;
}
int Lucas(int p, int k) {
  if (p < k) {
    return 0;
  }
  if (p <= 10) {
    return C(p, k);
  }
  return Lucas(p / 3, k / 3) * C(p % 3, k % 3) % 3;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("brick.in", "r", stdin), freopen("brick.out", "w", stdout);
  for (cin >> t; t; t--, ans = 0) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> ch, a[i] = ch - 'A';
    }
    for (int i = 1; i <= n; i++) {
      (ans += Lucas(n - 1, i - 1) * a[i] % 3) %= 3;
    }
    (n & 1 ^ 1) && (ans = (3 - ans) % 3);
    cout << (char)(ans + 'A') << '\n';
  }
  return 0;
}

#C. 学习 LIS

考虑状压 dp，令 \(dp_{i,j,s}\) 为：正在考虑 \(i\) 填哪里，正在考虑从后向前数第 \(j\) 位是否填 \(i\)，填入的集合是 \(s\) 的方案数

转移直接分是否选 \(i\) 分类讨论即可，具体可以看代码

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 20, kL = 1 << kMaxN, kMaxM = 3e3 + 5;
const LL kP = 998244353;

int n, m, a[kMaxN + 1], mx[kL], ans[kMaxN + 1], dp[2][kMaxN + 1][kL], cur, nxt = 1, cnt;
LL c[kMaxM][kMaxM];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), c[0][0] = c[1][0] = c[1][1] = 1;
  freopen("lis.in", "r", stdin), freopen("lis.out", "w", stdout);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 2; i < kMaxM; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % kP;
    }
  }
  for (int j = 0; j < (1 << n); j++) {
    for (int i = 0; i < n; i++) {
      if (j & (1 << i)) {
        mx[j] = max(mx[j], a[i]);
      }
    }
  }
  dp[0][n - 1][0] = 1;
  for (int u = 1; u <= n; u++) {
    for (int i = n - 1; ~i; i--) {
      for (int j = 0; j < (1 << n); j++)
        if (dp[cur][i][j]) {
          int tmp = dp[cur][i][j];
          (dp[i ? cur : nxt][(i ? i : n) - 1][j] += tmp) %= kP;
          if (!(j & (1 << i)) && mx[j & ((1 << i) - 1)] + 1 == a[i]) {
            (dp[i ? cur : nxt][(i ? i : n) - 1][j | (1 << i)] += tmp) %= kP;
          }
          dp[cur][i][j] = 0;
        }
    }
    ans[u] = dp[nxt][n - 1][(1 << n) - 1], swap(cur, nxt);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i - 1; j >= 1; j--) {
      ans[i] = (ans[i] + (-1 * c[i][j] * ans[j] % kP) + kP) % kP;
    }
    cnt = (cnt + ans[i] * c[m][i] % kP) % kP;
  }
  cout << cnt << '\n';
  return 0;
}

#D. 战略轰炸

人机线段树二分，先咕咕咕