算法题解

牛客周赛 Round 157 | 题解

2026-08-18 #前缀和#牛客#哈希#模拟

周赛157

A、小月的魔法

知识点:模拟

直接模拟即可

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
import sys
import math
import bisect
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify

sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

# ===================== 快速读入整行全部数据,大数据用 =====================
def readints():
return list(map(int, sys.stdin.readline().split()))

def readstr():
return sys.stdin.readline().strip()

# 一次性读全部输入(超大输入加速)
def read_all():
data = sys.stdin.read().split()
ptr = 0
def get():
nonlocal ptr
x = int(data[ptr])
ptr += 1
return x
return get

# ===================== 主函数,比赛写逻辑放这里 =====================
def main():
# 示例
n, m = readints()
if (n + m == 10):
print("YES")
else:
print("NO")

if __name__ == "__main__":
main()

B、小月的拨盘

**知识点:模拟。 **

对于 '+' d = (d + 1) % 10,对于 '-',d = (d - 1 + 10) % 10,然后用 cnt 来记录次数

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
# Problem: 小月的拨盘
# Contest: NowCoder
# URL: https://ac.nowcoder.com/acm/contest/139206/B
# Memory Limit: 512 MB
# Time Limit: 2000 ms
#
# Powered by CP Editor (https://cpeditor.org)

import sys
import math
import bisect
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify

sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

# ===================== 快速读入整行全部数据,大数据用 =====================
def readints():
return list(map(int, sys.stdin.readline().split()))

def readstr():
return sys.stdin.readline().strip()

# 一次性读全部输入(超大输入加速)
def read_all():
data = sys.stdin.read().split()
ptr = 0
def get():
nonlocal ptr
x = int(data[ptr])
ptr += 1
return x
return get

# ===================== 主函数,比赛写逻辑放这里 =====================
def main():
# 示例
n, d = readints()
s = readstr()
xx = d
tt = 0
for c in s:
if c == '+':
d = (d + 1) % 10
else:
d = (d - 1 + 10) % 10
if d == xx:
tt += 1

print(d, tt)

if __name__ == "__main__":
main()

C、小月的特效

知识点:哈希

用哈希表记录一下每个元素第一次和最后一次出现的位置。

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
# Problem: 小月的拨盘
# Contest: NowCoder
# URL: https://ac.nowcoder.com/acm/contest/139206/B
# Memory Limit: 512 MB
# Time Limit: 2000 ms
#
# Powered by CP Editor (https://cpeditor.org)

import sys
import math

sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

# ===================== 快速读入整行全部数据,大数据用 =====================
def readints():
return list(map(int, sys.stdin.readline().split()))

def readstr():
return sys.stdin.readline().strip()

# 一次性读全部输入(超大输入加速)
def read_all():
data = sys.stdin.read().split()
ptr = 0
def get():
nonlocal ptr
x = int(data[ptr])
ptr += 1
return x
return get

# ===================== 主函数,比赛写逻辑放这里 =====================
def main():
# 示例
get = read_all()
n = get()
a = [get() for _ in range(n)]

mp1 = dict()
mp2 = dict()
mp3 = dict()
for idx, x in enumerate(a):
if x not in mp3:
mp3[x] = 1
else:
mp3[x] += 1

if x not in mp1 :
mp1[x] = idx;
else:
mp1[x] = min(mp1[x], idx)

if x not in mp2 :
mp2[x] = idx
else:
mp2[x] = max(mp2[x], idx)

cnt = 0
for k, v in mp1.items():
if (mp2[k] - v) % 2 == 0 and mp3[k] > 1:
cnt += 1

print(cnt)



if __name__ == "__main__":
main()

D、小月的石阶

知识点:二分、前缀和

对于每一个二分的区间,从每一个数组位置开始判定

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
# Problem: 小月的拨盘
# Contest: NowCoder
# URL: https://ac.nowcoder.com/acm/contest/139206/B
# Memory Limit: 512 MB
# Time Limit: 2000 ms
#
# Powered by CP Editor (https://cpeditor.org)

import sys
import math
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
# ===================== 快速读入整行全部数据,大数据用 =====================
def readints():
return list(map(int, sys.stdin.readline().split()))

def readstr():
return sys.stdin.readline().strip()

# 一次性读全部输入(超大输入加速)
def read_all():
data = sys.stdin.read().split()
ptr = 0
def get():
nonlocal ptr
x = int(data[ptr])
ptr += 1
return x
return get

# ===================== 主函数,比赛写逻辑放这里 =====================
def main():
get = read_all()
n = get()
k = get()
h = []

for _ in range(n):
h.append(get())

a = []
for i in range(0, n):
if i != 0:
a.append(abs(h[i] - h[i - 1]))
# print(h)
# print(a)

b = [0] * (n - 1)

for idx in range(0, n - 1):
b[idx] = b[idx - 1] + a[idx]

ll = 1
rr = n

# print(b)
tt = 0
while ll < rr:

mid = (ll + rr + 1) // 2
st = 0

for i in range(0, n - mid + 1):

s = b[i + mid - 2] - b[i - 1]
# print(i, mid, s)

if i == 0:
s = b[i + mid - 2]
else:
s = b[i + mid - 2] - b[i - 1]

if s <= k:
st = 1
tt = 1
break

if(st == 1):
ll = mid
else:
rr = mid - 1

if tt == 1:
print(ll)
else:
print(1)

if __name__ == "__main__":
main()

E、小月的清单

知识点:前缀和、维护左右最小值数组

考虑如下几种情况:

  • S_i 不变,则原先任意前缀必须都非负。
  • ‘+’ → ‘-’ ,则原先小于 i 的前缀必须都非负,且大于等于 i 的位置中前缀和最小的减去 2 * a[i] 必须非负。
  • '-' → '+' ,则原先小于 i 的前缀必须都非负,且大于等于 i 的位置中前缀和最小的加上 2 * a[i] 必须非负。
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
// Problem: 小月的清单
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/139206/E
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

#define fast_ ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);

#define ffi(a, b) for(int i = a; i <= b; i ++)
#define ffj(a, b) for(int j = a; j <= b; j ++)
#define ffk(a, b) for(int k = a; k <= b; k ++)

int qpow(int a, int b, int mod) { int res = 1; while(b) { if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod;} return res; }

#define pb push_back
#define ins insert
#define piii pair<pair<int, int>, int>
#define pii pair<int, int>
#define umap unordered_map
#define int long long

// #define MORE
const int N = 2e5 + 10, mod = 1e9 + 7;

int n, m, qq;
int a[N], b[N], c[N], d[N];
string s;

void solve()
{
cin >> n >> m;
for(int i = 1; i <= n ;i ++) cin >> a[i];
string s; cin >> s;
for(int i = 1; i <= n ; i ++)
if(s[i - 1] == '+')
b[i] = b[i - 1] + a[i];
else
b[i] = b[i - 1] - a[i];

c[0] = d[n + 1] = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n; i ++) c[i] = min(c[i - 1], b[i]);
for(int i = n ; i >= 1; i --) d[i] = min(d[i + 1], b[i]);

int pp = 1e18, idx = -1;
for(int i = 1; i <= n ;i ++) {
if(c[i] < 0)
{
pp = c[i];
idx = i;
break;
}
}

while( m --)
{
int x; char t; cin >> x >> t;
if(s[x - 1] != t)
{
if(t == '-')
{
if(c[x - 1] < 0) cout << "NO\n";
else if(d[x] >= 2 * a[x]) cout << "YES\n";
else cout << "NO\n";
}
else
{
if(c[x - 1] < 0) cout << "NO\n";
else if(d[x] >= -2 * a[x])cout << "YES\n";
else cout << "NO\n";
}
}
else
{
if(idx == -1)cout << "YES\n";
else cout << "NO\n";
}
}
}

void Coding() { fast_; int t = 1;
#ifdef MORE
cin >> t;
#endif
while(t --) solve(); }

signed main() { Coding(); return 0; }
Comments
赞赏
Share
← 返回