牛客-美团暑期2025-20250322-前两题和第三题的思路

【LetMeFly】牛客-美团暑期2025-20250322-前两题和第三题的思路

第三题刚开始想复杂了,后面想到了个思路但是没来得及实现。

一:对称回文串

标签:回文串

题目描述

判断一个字符串有多少个长度大于1的对称回文子串

一个字符串为对称回文串当且仅当:

  • 该字符串为回文串
  • 该字符串只由字母AHIMOTUVWXY组成

数据范围:字符串长度不超过$100$

解题思路

$O(n^2)$枚举每个字符串子串,判断当前字符串是否为对称回文串

AC代码

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
/*
* @Author: LetMeFly
* @Date: 2025-03-22 19:14:07
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-22 19:25:02
*/
#include <bits/stdc++.h>
using namespace std;

inline bool isOk(char c) {
static const string okList = "AHIMOTUVWXY";
for (char ok : okList) {
if (c == ok) {
return true;
}
}
return false;
}

bool isOk(string s) {
for (char c : s) {
if (!isOk(c)) {
return false;
}
}
for (int i = 0; i < s.size() / 2; i++) {
if (s[i] != s[s.size() - i - 1]) {
return false;
}
}
return true;
}

int solve(string s) {
int ans = 0;
for (int i = 0; i < s.size(); i++) {
for (int j = i + 1; j < s.size(); j++) { // 长度大于1
bool thisIsOk = isOk(s.substr(i, j - i + 1));
ans += thisIsOk;
#ifdef _WIN32
if (thisIsOk) {
printf("i = %d, j = %d, s.substr(%d, %d) = %s : OK\n", i, j, i, j, s.substr(i, j).c_str());
}
#endif
}
}
return ans;
}

int main() {
#ifdef _WIN32
vector<string> S = {"AHHAMTT"};
vector<int> ANS = {3};
for (int i = 0; i < S.size(); i++) {
int ans = solve(S[i]);
cout << S[i] << ": " << ans << endl;
assert(ans == ANS[i]);
}
#else
string s;
cin >> s;
cout << solve(s) << endl;
#endif
return 0;
}

二:下一个更大元素

标签:暴力模拟

题目描述

判断一个“全排列”的数组有多少个长度为奇数的子数组满足:

数组最中间的元素正好为数组的中位数

数据范围:单个测试用例多组输入字符串总长度不超过$10^4$

解题思路

本来想着先暴力一波看看能得多少分,结果就AC了,并且只用了84ms。

AC代码

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
/*
* @Author: LetMeFly
* @Date: 2025-03-22 19:30:14
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-22 19:36:56
*/
// 诶,不是哥们,还没利用“排列中数各不相同的性质”呢,咋就84ms然后AC了
#include <bits/stdc++.h>
using namespace std;

int a[10010];

int solve(int n) {
int ans = 0;
for (int start = 0; start < n; start++) {
int lt = 0, gt = 0;
ans++;
for (int i = 1; start - i >= 0 && start + i < n; i++) {
if (a[start - i] > a[start]) {
gt++;
} else {
lt++;
}
if (a[start + i] > a[start]) {
gt++;
} else {
lt++;
}
ans += lt == gt;
}
}
return ans;
}

int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int ans = solve(n);
printf("%d\n", ans);
}
return 0;
}

三:移动的机器人最终停在哪里

标签:模拟

题目描述

共n个位置机器人初始位置在$k$,问机器人执行完指令可能停在哪些位置。

指令执行方式为:

一个指令字符串,一个字符为一个指令。

字符L表示机器人向左移动一个位置,R表示向右移动一个位置,?表示既可以向左移动一个位置又可以向右移动一个位置。

若机器人达到了边界的位置无法向目标方向移动,则停在原地。

数据范围$10^6$

解题思路

假设位置有无限多个,那么不论移动多少次,最终的可能位置要么全是奇数,要么全是偶数:

例如初始位置是5,移动一次可能到4或6(都是偶数)

移动两次可能到3或5或7(都是奇数)

除非移动到了边界可能导致终点既有可能奇数又可能有偶数。

因此可以使用如下结构:

1
2
3
4
5
struct Range {
int start, end;

Range(int a, int b) : start(a), end(b) {};
};

那么vector<Range>则表示所有终点的可能范围,其中Rangestart=3, end=7的话代表终点范围可能是3, 5, 7

每次移动都更新所有可以到达的终点。并合并。

为什么要合并呢

因为不合并的话,最终的合法终点范围可能会越来越多,并且有重复现象。

怎么个合并法呢?

例如有段范围表示1, 3, 5, 7,有段范围表示3, 5, 7, 9,那么它们就可以合并为1, 3, 5, 7, 9(使用Range(1, 9)表示即可)

具体怎么做?

可以奇偶分开合并。例如对于奇数:先将位置排序,然后判断下一个位置和上一个位置是否重复或可拼接,若能拼接则合并之。

没有具体验证,由于最多存在:开头、中间、结尾的奇数和偶数等有限个“终点可达区间”,所以每次都合并的话似乎区间个数不会超过$6$,$6\times 10^6$在合理范围内。

WA代码

嗐,没写完时间就到了,还好在没合并的时候就交了一版,过了%20

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
* @Author: LetMeFly
* @Date: 2025-03-22 20:15:56
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-03-22 20:38:50
*/

#include <bits/stdc++.h>

using namespace std;


struct Range {
int start, end;

Range(int a, int b) : start(a), end(b) {};
};

int n, k;
string s;
vector<Range> OkList;
bool a[1000010] = {false};



void print() {
for (Range& r : OkList) {
for (int i = r.start; i <= r.end; i += 2) {
a[i] = true;
}
}
for (int i = 1; i <= n; i++) {
putchar(a[i] ? '1' : '0');
}
}

vector<Range> genOdd() {
vector<Range> ans;
for (Range r : OkList) {
if (r.start % 2) {
ans.push_back(r);
}
}
return ans;
}

vector<Range> genEven() {
vector<Range> ans;
for (Range r : OkList) {
if (r.start % 2 == 0) {
ans.push_back(r);
}
}
return ans;
}

vector<Range> mergeOddOrEven(vector<Range>& odd) { // 全是奇数或全是偶数
if (odd.empty()) {
return {};
}
vector<Range> ans;
int l = odd[0].start, r = odd[0].end;
for (int i = 1; i <= odd.size(); i++) {
if (i == odd.size() || odd[i].start > r + 2) {
ans.push_back(Range(l, r));
l = odd[i].start, r = odd[i].end;
} else {
r = max(r, odd[i].end);
}
}
return ans;
}


void mergeList() {
vector<Range> odd = genOdd();
vector<Range> even = genEven();
OkList = mergeOddOrEven(odd);
for (Range r : mergeOddOrEven(even)) {
OkList.push_back(r);
}
}

void left(vector<Range>& leftOk) {
for (Range r : OkList) {
int left = r.start;
int right = r.end;
left--;
right--;
if (left == 0) {
leftOk.push_back(Range(1, 1));
left = 2;
}
if (left <= right) {
leftOk.push_back(Range(left, right));
}
}
}

void right(vector<Range>& leftOk) {
for (Range& r : OkList) {
int left = r.start;
int right = r.end;
left++;
right++;
if (right == n + 1) {
leftOk.push_back(Range(n, n));
right = n - 1;
}
if (left <= right) {
leftOk.push_back(Range(left, right));
}
}
}

/*
3 2
RL?

010
*/

/*
5 2
?????

11111
*/

int main() {
cin >> n >> k;
cin >> s;
OkList.push_back(Range(k, k));

for (char c : s) {
vector<Range> nextOk;
if (c == 'L' || c == '?') {
left(nextOk);
}
if (c == 'R' || c == '?') {
right(nextOk);
}
OkList = move(nextOk);
mergeList();
}

print();
return 0;
}

End

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


牛客-美团暑期2025-20250322-前两题和第三题的思路
https://blog.letmefly.xyz/2025/03/22/Nowcoder-MeiTuan-Summer2025-20250322/
作者
发布于
2025年3月22日
许可协议