牛客OI周赛15-普及组 ABD题解

A - 咪咪游戏

Solution

直接构造一个字符串 $t$ 使得长度和 $s$ 相同且由连续的mq组成。

如果构造不出长度相同的或者 $s$ 和 $t$ 长得不一样的输出No，否则输出Yes即可。

时间复杂度 $O(n)$

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int q; cin >> q;
  while(q--) {
    string s; cin >> s;
    string t;
    while(t.size() < s.size()) t += "mq"; // 构造字符串t
    if(s == t) cout << "Yes\n";
    else cout << "No\n";
  }
}

B - 三角形

Solution

令 $q[i]$ 表示取了 $i$ 件物品时所有宝物价值的总和的集合。

我们只需要最终集合的前 $k$ 小个，那么本来就不是前 $k$ 小的物品再加一些宝物的价值时肯定不会是前 $k$ 小的。于是每一个集合只需要前 $k$ 小的即可，剩余的丢弃，这样的复杂度才是好的。

最终答案即 $\sum\limits_{i=1}^{k} q_{n,i}$ 。

上面的 $q$ 可以用priority_queue来做，且可以作为滚动数组。

时间复杂度 $O((n\cdot m+k)\log(k))$

Code

#include<bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; size_t k; cin >> n >> k;
  priority_queue<int> q[2]; // 用于存放集合 滚动数组
  q[1].push(0);
  for(int i = 0; i < n; i++) {
    int m; cin >> m; vector<int> v(m);
    for(int i = 0; i < m; i++) cin >> v[i];
    while(!q[~i & 1].empty()) {
      const int cur = q[~i & 1].top();
      q[~i & 1].pop();
      for(int j = 0; j < m; j++) {
        // 当集合个数大于等于k 那么需要控制集合个数不超过k个
        if(q[i & 1].size() >= k && q[i & 1].top() > cur + v[j]) {
          q[i & 1].push(cur + v[j]);
          q[i & 1].pop();
        // 集合个数不超过k个 无条件放入
        } else if(q[i & 1].size() < k) {
          q[i & 1].push(cur + v[j]);
        }
      }
    }
  }
  int tot = 0;
  while(!q[~n & 1].empty()) {
    tot += q[~n & 1].top();
    q[~n & 1].pop();
  }
  cout << tot << '\n';
}

D - 多元组

Solution

这题和树状数组求逆序对差不多，这题可以说是求一个数组的 $m$ 长度的顺序对个数。

令 $dp[i][j]$ 表示 $p_i$ 的是 $a_j$ 的 $i$ 元组满足 $[p_1,...,p_i]|(a_{p_1}<...<a_{p_i},p_1<...<p_i)]$ 的个数。

显然有：

$dp[i][j]= \begin{cases} 1, &i=1\\ \sum\limits_{k=1}^{j-1}(dp[i-1][k]\cdot [a_k<a_j]), &i\ge 2 \end{cases}$

首先对数组下标排一个序，需要让 $a_i$ 比较小的先进行计算，若两个 $a_i$ 相同，则下标大的优先处理。即下边的这个函数是做这种操作的：

sort(id.begin() + 1, id.end(), [&](const int& x, const int& y) {
  if(v[x] == v[y]) return x > y;
  return v[x] < v[y];
});

那么当 $i\ge 2$ 时，就可以无视 $[a_k<a_j]$ 的限制，因为此时 $dp[i-1][k]$ 是等于 $0$ 的。那么直接用树状数组就可以轻松求解。

时间复杂度 $O(n\cdot m\log(n))$ 空间复杂度 $O(n\cdot m)$

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 50, MOD = 1e9 + 7;
int base[M][N]; // M个树状数组
// 快乐取模大法
void add(int &x, int y) {
  x += y;
  if(x >= MOD) x -= MOD;
}
// upd(第几个树状数组，在第几个位置，增加多少值)
void upd(int id, int at, int x) {
  for(int i = at; i < N; i += i & (-i)) {
    add(base[id][i], x);
  }
}
// query(第几个树状数组，询问前多少个位置) 返回总和
int query(int id, int at) {
  int ans = 0;
  for(int i = at; i > 0; i -= i & (-i)) {
    add(ans, base[id][i]);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m; cin >> n >> m;
  vector<int> v(n + 1), id(n + 1);
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    id[i] = i; // 排序的是下标值
  }
  // 排序定先后顺序
  sort(id.begin() + 1, id.end(), [&](const int& x, const int& y) {
    if(v[x] == v[y]) return x > y;
    return v[x] < v[y];
  });
  // 状态转移
  for(int i = 1; i <= n; i++) {
    upd(0, id[i], 1);
    for(int j = 1; j < m; j++) {
      upd(j, id[i], query(j - 1, id[i] - 1));
    }
  }
  cout << query(m - 1, n) << '\n'; // 求和即最终结果
}