A. Sum (排序+贪心)
有一个长度为 $n$ 的数列 $a_n$, 每次可以任意选 $k, k \ge 2$ 个数, 这 $k$ 个数的和 $S$ 会成为这次行动的 得分
操作结束后, 将选取的 $k$ 个数从数列里删除, 并将和 $S$ 加入数列, 在进行下一次操作, 操作数可以为 $0$
问: 任意次操作后, 最大得分???
思路:
排序, 每次选取最大的两个数 $a$ 和 $b$, 获得这次操作的得分 $a+b$
直到 $a + b \le 0$ 或者 数列只剩一个数字, 此时不会再增加总得分
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
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
void slove() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a.rbegin(), a.rend());
long long ans = 0;
long long temp = a[0];
long long mod = 1e7 + 7;
for (int i = 1; i < n; i++)
{
temp += a[i];
if (temp < 0)
{
break;
}
ans += temp;
ans %= mod;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
slove();
}
return 0;
}
B. Gaming (线段树 / 差分)
有 $n$ 个房间, $m$ 个debuff
当进入第 $i$ 个房间时, 会获得编号在 $[l_i, r_i]$ 上的所有debuff, 并获得 $S_i$ 积分
如果多次获得编号为 $x$ 的debuff, 视为一个
问: 在能打过boss(未集满所有 $m$ 种debuff)的前提下, 能获得的最大积分???
思路:
- 方法1: 差分
差分的 区间加, 再利用前缀和计算每种debuff的分数, 并更新debuff的最小分数, 最后利用所有房间的分数和减去最小debuff分数即为答案
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<long long> a(m + 2);
long long total = 0;
for (int i = 0; i < n; i++)
{
int l, r;
long long s;
cin >> l >> r >> s;
a[l] += s;
a[r + 1] -= s;
total += s;
}
long long mn = 1e18;
for (int i = 1; i <= m; i++)
{
a[i] += a[i - 1];
mn = min(mn, a[i]);
}
cout << total - mn << endl;
return 0;
}
- 方法2: 线段树
枚举每一个debuff, 计算除去该debuff所能拿到的最大得分
使用线段树的 区间加, 计算每种debuff的分数, 并计算全部房间的总分数
枚举每种debuff, 用总分数减去该debuff的分数, 即为除去该debuff所能拿到的最大分数
C. School (区间合并+二分查找)
一天有 $h$ 小时, $m$ 分钟
共有 $n$ 个时间段, 第 $i$ 段从 $a_i$ 小时 $b_i$ 分钟到 $c_i$ 小时 $d_i$ 分钟不能通话
问: 有 $q$ 个询问, 询问在 $x$ 小时 $y$ 分钟是否可以通话
思路:
首先, 将所有时间改成 分钟 的形式: 1小时10分钟 就是 70分钟, 时间段 1小时10分钟到2小时20分钟 就是 70分钟到140分钟
将所有不能通话的时间段全部转化为分钟形式的区间
询问时, 将询问的 x小时y分钟 也转化为分钟形式, 二分查找即可
不能通话的时间段有可能发生重叠, 需要先合并重叠的区间, 再二分搜索
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long n, h, m, q;
cin >> n >> h >> m >> q;
vector<pair<long long, long long>> t1;
for (int i = 0; i < n; i++)
{
long long a, b, c, d;
cin >> a >> b >> c >> d;
t1.emplace_back(make_pair(a * m + b, c * m + d));
}
sort(t1.begin(), t1.end());
vector<pair<long long, long long>> t2;
t2.emplace_back(t1[0]);
for (int i = 1; i < t1.size(); i++)
{
if (t1[i].first <= t2.back().second)
{
t2.back().second = max(t1[i].second, t2.back().second);
} else {
t2.emplace_back(t1[i]);
}
}
sort(t2.begin(), t2.end());
for (int i = 0; i < q; i++)
{
long long x, y;
cin >> x >> y;
long long cur = x * m + y;
int l = 0, r = t2.size() - 1;
bool flag = true;
while (l <= r)
{
int mid = (l + r) / 2;
if (t2[mid].first <= cur && t2[mid].second >= cur)
{
cout << "No" << endl;
flag = false;
break;
} else if (t2[mid].first > cur) {
r = mid - 1;
} else if (t2[mid].second < cur)
{
l = mid + 1;
}
}
if (flag)
{
cout << "Yes" << endl;
}
}
return 0;
}
D. Word (BFS)
给定 $n$ 个单词的单词表, 需要将字符串 s 转换为 t
转换规则:
每次改变
s的一个字母, 并且保证每次转变后的字符串出现在给定的字母表中
问: 1. 最小操作数 2. 操作的过程
思路: 暴力BFS
leetcode类似的题目: https://leetcode.cn/problems/om3reC/
单词表最多只有2000个单词, 每个单词最长20字符, 那么完全可以 暴力BFS
对于当前字符串 cur 的每一个位置, 遍历 $a, b, …, z$, 修改当前字符串, 检查修改后的字符串是否出现在单词表中, 直到字符串变为 t 为止
为了防止陷入循环, 比如: “qwq” -> “qwa” -> “qwq”, 需要检查修改后的字符串是否出现在单词表中, 如果是, 就将该字符串从单词表中删除, 避免重复计算
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
set<string> words;
for (int i = 0; i < n; i++)
{
string temp;
cin >> temp;
words.insert(temp);
}
string s, t;
cin >> s >> t;
queue<pair<string, vector<string>>> q;
vector<string> ans;
q.emplace(make_pair(s, ans));
while (!q.empty())
{
int cnt = q.size();
for (int i = 0; i < cnt; i++)
{
pair<string, vector<string>> p = q.front();
string cur = q.front().first;
// vector<string> temp = q.front().second;
q.pop();
for (int j = 0; j < m; j++)
{
for (char c = 'a'; c <= 'z'; c++)
{
string word = cur;
word[j] = c;
if (word == t)
{
// cout the ans
vector<string> temp = p.second;
cout << temp.size() << endl;
cout << s << endl;
for (auto & w : temp)
{
cout << w << endl;
}
cout << t << endl;
return 0;
}
if (words.count(word))
{
vector<string> temp = p.second;
temp.emplace_back(word);
q.emplace(make_pair(word, temp));
words.erase(word);
}
}
}
}
}
cout << -1 << endl;
return 0;
}
E. Slash (DP)
给定字符串 s 和一个 $n * m$ 的矩阵, 要求从矩阵左上角顶点出发只能往左走, 往下走, 最大化路线上包含的所有字符连起来的字符串中字符串 s 的数量
这里 s 的个数指的是字符串中不存在相交部分的与 s 相等的子串
思路:
定义 $dp[i][j][k]$: 从矩阵左上角运动到 $[i, j]$处, 匹配到字符串 s 第 $k$个字符的最大数量
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
string s;
cin >> s;
int len = s.size();
s = ' ' + s; // 这样下标可以从1开始
vector<vector<char>> grid(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> grid[i][j];
}
}
// dp[i][j][k]: 从[1, 1]到[i, j]匹配到第k位的最大值
vector<vector<vector<int>>> dp(n + 5, vector<vector<int>>(m + 5, vector<int>(s.size() + 5, -1)));
// [i,j] 处的答案记录
vector<vector<int>> ans(n + 5, vector<int>(m + 5, -1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= len; k++)
{
if (grid[i][j] != s[k])
{
continue;
}
if (k == 1)
{
// 新开一段
dp[i][j][k] = max(0, max(ans[i - 1][j], ans[i][j - 1]));
} else {
// 继承 k-1
dp[i][j][k] = max(dp[i][j][k], max(dp[i-1][j][k-1], dp[i][j-1][k-1]));
}
if (k == len)
{
// 已经匹配出一个完整的 字符串s
dp[i][j][k] += 1;
}
}
ans[i][j] = max(dp[i][j][len], max(ans[i - 1][j], ans[i][j - 1]));
}
}
cout << ans[n][m] << endl;
return 0;
}