小白月赛94

A 小苯的九宫格

现在小苯有一个可能乱序的九宫格按键，但他没注意到九宫格是乱序，因此他还是按照正常九宫格顺序点击的按键。
（正常九宫格：也就是按照 1 到 9分为三行三列，从上到下，从左到右都是递增的）

请你告诉他，在他点击完按键后，屏幕上显示的数字都应该是什么？

void solve() {
    int a[4][4] = {};
    for (int i = 0;i < 3;i++) {
        for (int j = 0;j < 3;j++) {
            cin >> a[i][j];
        }
    }
    string s;cin >> s;
    for (int i = 0;i < s.size();i++) {
        cout << a[(s[i] - '0' - 1) / 3][(s[i] - '0' + 2) % 3];
    }
}

B 小苯的好数组

如果一个数组按升序排序后和原来不完全相同，则其是一个好数组。

小苯想知道，如果想要使得选择的子序列构成一个“好数组”，最长可以选多长的子序列？

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 2;i <= n;i++) {
        if (a[i] < a[i - 1]) {
            cout << n << "\n";return;
        }
    }
    cout << 0 << '\n';
}

C 小苯的数字合并

给定一个数组 a，要求按照操作最大化其极差。

可以执行操作任意次：将两个数字合并。

很明显的前缀和

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)pre[i] = pre[i - 1] + a[i];
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int x = pre[i - 1] - pre[0] - a[i];
        int y = pre[n] - pre[i] - a[i];
        ans = max({ans,x,y});
    }
    cout << ans << '\n';
}

D 小苯的排列构造

给定一个数组 a，ai=gcd(p1,p2,…pi)，求 p 排列的一种可能形式，若不存在，则输出 -1

非常致命的坑点：last，若不用一个变量来保存的话，若前后两个 ai 相等(这种情况是最多的)，会导致每个 ai 都会重复计算一遍，会导致超时。如：在这份代码若将 last 拿出 if 条件将会超时。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), ans(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int last = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i] != a[i - 1]) {
            if (a[i - 1] % a[i] != 0) {
                cout << -1 << "\n";return;
            }
            last = a[i];
        }
        while (last <= n && vis[last])last += a[i];
        if (last > n) {
            cout << "-1\n";return;
        } else {
            ans[i] = last, vis[last] = 1;
        }
    }
    for (int i = 1;i <= n;i++)
        cout << ans[i] << " \n"[i == n];
}

E/F 小苯的 01 背包

一个背包的容量为 k，有 n 个物品，每个物品带有体积 v 和价值 w。

在体积不超过 k 的前提下，最多能装价值为多少的物品。

本题物品的总体积与总价值都定义为所装物品的按位与 (&)

easy：

这个版本的思路就是枚举答案：

由于体积和价值都是 ≤2000 的，所以可以枚举最后选择物品的价值与的结果，选择所有物品中完全包含枚举值的物品，这样就选好了这一轮次的物品，将其体积与起来，若总体积满足 ≤k，则取最大值即可。

void solve() {
  int n, k;cin >> n >> k;
  vector<pair<int, int>> p(n);
  for (auto& [v, w] : p) cin >> v >> w;
  int ans = 0;
  for (int i = 0; i <= 2000; i ++) {
    vector<pair<int, int>> s;
    for (auto [v, w] : p)
      if ((w & i) == i) s.emplace_back(v, w);
    if (s.empty()) continue;
    auto [sv, sw] = s[0];
    for (auto [v, w] : s) {
      sv &= v,sw &= w;
    }
    if (sv <= k) ans = max(ans, sw);
  }
  cout << ans;
}

hard：

和简单版本相比只是从枚举答案到枚举每一位，从高到低位贪心的看相应那一位是否满足。得到的一定是最大的。

void solve() {
    int n, k;cin >> n >> k;
    vector<pair<int, int>> p(n);
    for (auto& [v, w] : p) cin >> v >> w;
    int i = 0;
    for (int j = 30; j >= 0; j --) {
        vector<pair<int, int>> s;
        i += 1 << j;
        for (auto [v, w] : p)
            if ((w & i) == i) s.emplace_back(v, w);
        if (s.empty()) {
            i -= 1 << j;
            continue;
        }
        auto [sv, sw] = s[0];
        for (auto [v, w] : s) {
            sv &= v;
            sw &= w;
        }
        if (sv > k) i -= 1 << j;
    }
    cout << i;
}