算法题解

牛客周赛 Round 156 | 题解

2026-08-17 #字符串#二分#前缀和#牛客#模拟#数学#dfs#状态压缩

牛客156

A、小红找数字

知识点:字符串,模拟,遍历

对字符串 s 进行从左到右扫描,如果发现 s[i] >= '0' && s[i] <= '9' ,则找到了一个数字字符,直接输出;否则输出 -1。

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

int main()
{
string s; cin >> s;
for(int i = 0; i < s.size(); i ++)
{
if(s[i] >= '0' && s[i] <= '9')
{
cout << s[i];
return 0;
}
}
cout << -1 << endl;
return 0;
}

B、小红的回文串

知识点: 回文串,模拟,枚举

先从 a ~ z 把字符串 s 中的字符进行剔除,然后用前后指针进行回文串的判定,同时统计合法数量。

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
 #include <iostream>
#include <cstring>
using namespace std;

bool check(string a, string b)
{
if(a == "") return 1;
if(a == b) return 0;
for(int i = 0, j = a.size() - 1; i < j; i ++, j --)
if(a[i] != a[j]) return 0;
return 1;
}

int main()
{
int n ; cin >> n; int cnt = 0;
string s; cin >> s;
for(int i = 0; i < 26; i ++)
{
char c = 'a' + i;
string t = "";
for(auto ss: s)
if(ss != c)
t += ss;
if(check(t, s)) cnt ++;
}
cout << cnt << endl;
}

C、小红的权值

知识点: 前缀和,二分,数学,排序

题目要求对于每一个 K 而言,a 数组的权值都不大于它,而且 x 的值是固定的,那么我们可以把它们看成一个数轴,要进行若干次操作时其权值最小,那必然是尽可能离 x 最近,即直接赋予数组元素为 x 。因此我们可以先维护出一个距离数组来看各个元素给 a 权值的贡献,然后进行从大到小排序,如果原始状态不满足,则可以直接从第一个距离贡献开始删除,但 n 和 q 是一个量级的(2e5),因此我们需要维护一个前缀和数组 s[i] 来做,并通过二分来找答案,总体时间复杂度 O(max(n, q) log(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 <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

const int N = 2E5 + 10;
int a[N], s[N], n, q, x;

bool check(int idx, int val)
{
return s[n] - s[idx] <= val;
}

signed main()
{
cin >> n >> q >> x;
for(int i = 1; i <= n ; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n ;i ++) a[i] = abs(a[i] - x);
sort(a + 1, a + 1 + n, greater<int>());
for(int i = 1; i <= n ; i ++) s[i] = s[i - 1] + a[i];

while(q --)
{
int k; cin >> k;
int l = 0, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid, k)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
return 0;
}

D、小红的01矩阵

知识点:dfs / 状态压缩

由题可知,一共只有三行,且要求的合法矩阵为任意一列都不相同,因此当 n > 8 时,找不到合法矩阵,直接输出 0 ;在 n <= 8 时,我们可以先用 map<int, vector<string>> 来存储每一列的所有选法,然后再进行 dfs2 来对于每一列的所有选法进行组合判别,最后统计方案数,时间复杂度为 O(8 ^ 8 * 3)

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>

using namespace std;
const int N = 5, K = 2e5 + 10;

int n, m, cnt;
set<string> s;
char g[N][K];
map<int, vector<string>> mp;

void dfs1(int row, string s, int u)
{
if(u > 3) {
mp[row].push_back(s);
return ;
}

if(s[u] == '?')
{
s[u] = '1';
dfs1(row, s, u + 1);
s[u] = '0';
dfs1(row, s, u + 1);
}
else dfs1(row, s, u + 1);
}

void dfs2(int u)
{
if(u > m) {
cnt ++;
return ;
}

auto v = mp[u];
for(auto c: v)
{
if(s.size() && s.find(c) == s.end())
{
s.insert(c);
dfs2(u + 1);
s.erase(c);
}
else if(s.size() == 0)
{
s.insert(c);
dfs2(u + 1);
s.erase(c);
}
}
}

int main()
{
cin >> m;
for(int i = 1; i <= 3; i ++)
for(int j = 1; j <= m ;j ++)
cin >> g[i][j];

if(m > 8)
{
cout << 0 << endl;
return 0;
}

for(int i = 1; i <= m; i ++)
{
string ss;
ss += g[1][i];
ss += g[2][i];
ss += g[3][i];
dfs1(i, ss, 0);
}

// cout << mp[1].size() << endl;

dfs2(1);

cout << cnt << endl;

return 0;
}

E、小红的树染色

知识点:树的直径,LCA,dfs,倍增

本题要求对于每一个 i ,依次将其在原始状态的基础上染红求被染红节点两两之间的最大距离,对于节点间的最大距离我们可以想到树的直径,可以先建树,选择一个合适的根节点,然后进行两次dfs找到树的直径,存一下树直径的两端点A、B和距离,再对节点依次进行染色,每染一次可以用倍增思路来做LCA求当前节点与端点的距离,整体时间复杂度 O(nlogn)

  • 如果当前节点已经染过色,直接输出原始答案
  • 当前节点为染色,则输出 max({max_val, dist(A, i), dist(B, 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
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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2E5 + 10, M = 2 * N;

int n, m, root;
int e[M], ne[M], h[M], idx;
int fa[N][19], depth[N];
string s;
int din[N], max_c = -1, max_val = -1;

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int u)
{
queue<int> q;
q.push(u);

memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;


while(q.size())
{
int t = q.front();
q.pop();

for(int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if(depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for(int k = 1; k <= 18; k ++)
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}

void dfs(int u, int p, int d)
{
// cout << u << " " << p << " " << d << " " << h[2] << endl;
if(s[u - 1] == '1' && d > max_val) {
max_c = u, max_val = d;
// cout << u << " " << d << endl;
}

for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == p) continue;
dfs(j, u, d + 1);
}
}

int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a, b);

for(int k = 18; k >= 0; k --)
if(depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if(a == b) return a;

for(int k = 18; k >= 0; k --)
if(fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}

int dist(int a, int b)
{
// cout << depth[a] << " " << depth[b]
// << " " << depth[lca(a, b)] << endl;
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}

int main()
{
cin >> n; cin >> s;
memset(h, -1, sizeof h);

for(int i = 1; i < n ; i ++)
{
int a, b; cin >> a >> b;
add(a, b), add(b, a);
din[a] += 2, din[b] += 2;
}

for(int i = 1; i <= n; i ++)
if(din[i] == 2) {
root = i;
break;
}

bfs(root);

int A = -1, B = -1;

for(int i = 0; i < s.size(); i ++)
if(s[i] == '1') {
A = i + 1;
break;
}

dfs(A, -1, 0);
A = max_c;

max_val = max_c = -1;

// cout << A << endl;

dfs(A, -1, 0);
B = max_c;

// cout << root << " " << A << " " << B << " " << max_val << endl;

for(int i = 0; i < s.size(); i ++)
{
// cout << i << " ";

if(s[i] == '1') cout << max_val << endl;
else
{
cout << max({max_val,
dist(A, i + 1), dist(B, i + 1)}) << endl;
}
}
return 0;
}
Comments
赞赏
Share
← 返回