写在前面：
题目信息获取来源https://www.nowcoder.com/discuss/467108267630534656，仅交流学习，如有侵权或涉密请联系我删除。
题目 1
题目内容
米小游拿到了一个矩阵，矩阵上有一格有一个颜色，为红色( R )。绿色( G
)和蓝色( B )这三种颜色的一种。
然而米小游是蓝绿色盲，她无法分游蓝色和绿色，所以在米小游眼里看来，这个矩阵只有两种颜色，因为蓝色和绿色在她眼里是一种颜色。
米小游会把相同颜色的部分看成是一个连通块。请注意，这里的连通划是上下左右四连通的。
由于色盲的原因，米小游自己看到的连通块数量可能比真实的连通块数量少。
你可以帮米小游计算连通块少了多少吗？
输入描述
第一行输入两个正整数 n 和 m ，代表矩阵的行数和列数。
接下来的 n 行，每行输入一个长度为 m 的，仅包含 R 、G 、B
三种颜色的字符串，代表米小游拿到的矩阵。
\(1 \le n, m \le 1000\)
输出描述
一个整数，代表米小游视角里比真实情况少的连通块数量。
样例
输入
输出
解题方法
模拟题，只需要进行两遍 DFS 即可。
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
| #include<bits/stdc++.h>
using namespace std;
int main() {
const int offset[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int n, m;
cin>>n>>m;
vector<vector<int>> g(n, vector<int>(m, 0x3f3f3f3f));
vector<vector<bool>> visit(n, vector<bool>(m, false));
for (int i = 0; i < n; i++) {
string s;
cin>>s;
for (int j = 0; j < m; j++) {
if (s[j] == 'R') {
g[i][j] = 0;
}
else if (s[j] == 'G') {
g[i][j] = 1;
}
else {
g[i][j] = 2;
}
}
}
function<void(int, int, bool)> dfs = [&](int x, int y, bool isreal) {
visit[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + offset[i][0], ny = y + offset[i][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny]) {
continue;
}
if (isreal && g[nx][ny] != g[x][y] ||
!isreal && (g[nx][ny] == 0 && g[x][y] != 0 || g[nx][ny] != 0 && g[x][y] == 0)) {
continue;
}
dfs(nx, ny, isreal);
}
};
int real_ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visit[i][j]) {
continue;
}
real_ans++;
dfs(i, j, true);
}
}
for (int i = 0; i < n; i++) {
fill(visit[i].begin(), visit[i].end(), false);
}
int fake_ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visit[i][j]) {
continue;
}
fake_ans++;
dfs(i, j, false);
}
}
cout << real_ans - fake_ans << endl;
return 0;
}
|
题目 2
题目内容
米小游拿到了一个字符串 s 。她可以进行任意次以下两种操作：
删除 s 的一个 "mhy" 子序列。 添加一个 "mhy" 子序列在 s 上。
例如，给定 s 为 "mhbdy" ，米小游进行一次操作后可以使 s 变成 "bd"
，或者变成 "mhmbhdyy" 。
米小游想知道，经过若干次操作后 s 是否可以变成 t ？
注：子序列在原串中的顺序也是从左到右，但可以不连续。
输入描述
第一行输入一个正整数 q ，代表询问的次数。
接下来每两行为一次询问：每行均为一个字符串，分别代表 s 和 t 。
\(1 \le q \le {10^3}\)
字符串的长度均不超过 \({10^3}\)。
输出描述
输出 q 行，每行输入一行答案。若可以使 s 变成 t ，则输出 "Yes"
。否则输出 "No" 。
样例
输入
1
2
3
4
5
6
7
| 3
mhbdy
bd
mhbdy
mhmbhdyy
mhy
abc
|
输出
解题方法
yhm->mhyhmy->mhyhmy->hym
通过上例可以看出插入的序列顺序无关，可互相转换，因此只需要统计 hmy
的字母个数和剩余序列即可
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
| #include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while (t--) {
string s, target;
cin>>s>>target;
vector<int> s_cnts(3, 0), target_cnts(3, 0);
string s_res = "", target_res = "";
for (auto &ch : s) {
if (ch == 'm') {
s_cnts[0]++;
}
else if (ch == 'h') {
s_cnts[1]++;
}
else if (ch == 'y') {
s_cnts[2]++;
}
else {
s_res.push_back(ch);
}
}
for (auto &ch : target) {
if (ch == 'm') {
target_cnts[0]++;
}
else if (ch == 'h') {
target_cnts[1]++;
}
else if (ch == 'y') {
target_cnts[2]++;
}
else {
target_res.push_back(ch);
}
}
if (s_res == target_res) {
if (s_cnts[0] - target_cnts[0] == s_cnts[1] - target_cnts[1] &&
s_cnts[1] - target_cnts[1] == s_cnts[2] - target_cnts[2]) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
else {
cout << "No" << endl;
}
}
}
|
题目 3
题目内容
米小游拿到了一个集合（集合中元素互不相等）。
她想知道，该集合有多少个元素数量大于 1
的子集，满足子集内的元素两两之间互为倍数关系？
由于数量可能过大，请对 1e9 + 7 取模。
输入描述
第一行输入一个正整数 n ，代表集合大小。
第二行输入 n 个正整数 \(a_i\)，代表集合的元素。
\(1 \le n \le {10}^5\)
\(1 \le a_i \le {10}^6\)
输出描述
一个整数，代表满足题意的子集数量对 对 1e9 + 7 取模的值。
样例
输入
输出
解题方法
之前在Leetcode上遇到过类似的题目368.
最大整除子集，所以最开始想到一种时间复杂度为 \(O(n^2)\) 的 DP 做法，其中 \(dp[i]\) 表示以第 i
个元素结尾的整除子集元素数量，对于每一个这样的集合，其包含的合法子集个数为
\({2}^{dp[i] - 1} -
1\)，借助快速幂可以求出答案。
但是本题的数据范围要求 \(O(n^2)\)
以下，所以该做法只通过了 20% 的弱数据。本题的正解也是 DP 的做法，不过
\(dp[i]\) 表示包含第 i
个元素的合法子集个数，可以通过枚举第 i
个元素的所有因子进行状态转移，时间复杂度可以优化到 \(O(n\sqrt{n})\) ，代码如下：
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
| #include<bits/stdc++.h>
using namespace std;
int main() {
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int n;
cin>>n;
vector<int> nums(n);
vector<int> pos(maxn, -1);
for (int i = 0; i < n; i++) {
cin>>nums[i];
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
pos[nums[i]] = i;
}
vector<int> dp(n, 0);
long long int ans = 0;
for (int i = 0; i < n; i++) {
int cur = nums[i];
for (int j = 1; j * j <= cur; j++) {
if (cur % j == 0) {
if (pos[cur/j] != -1 && cur/j != j) {
dp[i] += dp[pos[cur/j]];
}
if (pos[j] != -1) {
dp[i] += dp[pos[j]];
}
}
}
ans = (ans + dp[i])%mod;
dp[i]++;
}
cout << ans << endl;
}
|