算法题解

牛客周赛 Round 158 | 题解

2026-08-28 #牛客#树状数组#哈希#差分#计数

周赛158

A、小月的材料

知识点:模拟、绝对值

直接按定义计算 3 段差值并加权即可

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << 4 * abs(a - b) + 2 * abs(b - c) + abs(c - a) << endl;
return 0;
}

B、小月的点歌台

知识点:模拟、字符串、计数

从左到右扫描字符串。处理第 i 次点歌时,将对应类别的计数加一;第 1 次使计数达到 3 的位置就是答案。若扫描结束仍没有类别达到 3 次,则输出 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>
#include <cstring>
using namespace std;

int main()
{
int n; cin >> n;
string s; cin >> s;
map<char, int> mp;
for(int i = 0 ; i < s.size(); i ++)
{
char c = s[i];
mp[c] ++;
if(mp[c] >= 3) {
cout << i + 1 << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}

C、小月的书架

知识点:哈希、计数

根据题意,求当前元素的左右边出现次数相同时对当前元素的位置进行求和,我们可以发现一个特性:若该元素在整个数组中出现了偶数次,那它一定没有贡献;否则出现基数次,我们可以把中间元素位置的加上,此时就是最终答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N = 2E5 + 10;
int n, m, a[N];
map<int, vector<int>> mp;

int main()
{
cin >> n;
for(int i = 1 ; i <= n ;i ++) {
int x; cin >> x;
mp[x].push_back(i);
}
long long res = 0;
for(auto [k, v]: mp)
if(v.size() % 2)
res += v[v.size() / 2];
cout << res << endl;
return 0;
}

D、小月的相同数对

知识点:双指针、滑动窗口、计数

题目要求最短的一段连续元素,使其所得到的权值不小与k,很显然我们可以用双指针。先对初始左端点找到一个满足权值大于 k 的右端点,记录当前长度 len,然后再推进左端点位置,直到 当前区间的权值小于 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
#include <iostream>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N];
map<int, int> mp;

signed main()
{
cin >> n >> m;
for(int i = 1; i <= n ; i ++) cin >> a[i];
int l = 1, r = 1, res = 0, len = n + 1;

mp[a[1]]++;
while(l <= r && r <= n)
{
while(r + 1 <= n && res < m)
{
res += mp[a[r + 1]];
mp[a[r + 1]] ++;
r ++;
}

while(res >= m && l < r)
{
len = min(len, r - l + 1);
mp[a[l]]--;
res -= mp[a[l]];
l++;
}
if(r == n) break;
}
if(len != n + 1) cout << len << endl;
else cout << -1 << endl;

return 0;
}

E、小月的相邻数组

知识点:树状数组、差分、单点修改 + 区间查询

题意要求单点修改和区间查询,因此我们可以用树状数组来维护差分,对于满足 相邻差递增 的位置,直接在差分数组对应位置 +1,若对某个位置进行修改,则需要处理前一个位置、当前位置和后一个位置的情况,根据原先值进行 +1、-1、不变,然后每次[l, r]查询,直接用 sum(r - 1) - sum(l) 即可拿到答案。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, m, q;
int b[N], a[N], tr[N];

int lowbit(int x)
{
return x & -x;
}

void add(int x, int c)
{
for(int i =x; i <= n ; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for(int i = x; i ;i -= lowbit(i)) res += tr[i];
return res;
}

int check(int i) {
return 2 * a[i] < a[i - 1] + a[i + 1] ? 1 : 0;
}


signed main()
{
cin >> n >> q;
for(int i = 1; i <= n ;i ++) cin >> a[i];
for(int i = 2; i < n; i ++) if(check(i)) b[i] = 1;
for(int i = 1; i <= n ;i ++) add(i, b[i]);

while(q --)
{
int op; cin >> op;
if(op == 1)
{
int p, x; cin >> p >> x;
a[p] = x;
for(int i = max(2ll, p - 1); i <= min(n - 1, p + 1); i ++)
{
int t = check(i);
add(i, t - b[i]);
b[i] = t;
}
}
else
{
int l, r; cin >> l >> r;
cout << sum(r - 1) - sum(l) << endl;
}
}
return 0;
}
Comments
赞赏
Share
← 返回