0%

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

题目链接

A - 咪咪游戏

Solution

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

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

时间复杂度$O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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$元组满足题意条件的个数。

显然有:

$$
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$相同,则下标大的优先处理。即下边的这个函数是做这种操作的:

1
2
3
4
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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'; // 求和即最终结果
}

回到开头