思路
本题的输入是一个数的前序遍历, 只要通过前序遍历构造一棵树即可.
pair有两个孩子, 左孩子和右孩子分别合法即pair合法. 分解成子问题递归解决
这道题没写出来的原因主要就是对于没有确定的连续输入不太熟悉
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
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string ans;
string s;
int flag = 0;
void dfs()
{
if(cin >> s)
{
ans += s;
if(s == "pair")
{
ans += '<';
dfs();
ans += ',';
dfs();
ans += '>';
}
}
else flag = 1;
}
int main()
{
int n;
cin >> n;
string s;
dfs();
if(cin >> s) flag = 1;
if(!flag) cout << ans;
else cout << "Error occured";
return 0;
}
|
思路
并查集维护集合, 无向图中每一个集合最大的边为 $n - 1$ , 我们只要计算最后集合中有几个点即可能算出最大的度为多少
若两个点已经在一个集合中, 我们会多出一个边,如何最大化利用多出来的边?
只要将这条边连在两个不同的集合中,将两个集合合并为一个集合
菊花图, 所有的边都都连向同一个点.
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
| #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int q[N], s[N], n, m;
int sz[N], tt, cnt;
int find(int x)
{
if(q[x] != x) q[x] = find(q[x]);
return q[x];
}
int main()
{
cin >> n >>m ;
for(int i = 0 ; i<= n; i++) q[i] = i, s[i] = 1;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
x = find(x), y = find(y);
if(x != y)
{
s[y] += s[x];
q[x] = y;
}
else cnt++;
int tt = 0;
for(int i = 1; i <= n; i++) if(q[i] == i) sz[tt++] = s[i];
int sum = 0;
sort(sz, sz + tt, greater<int>());
for(int i = 0; i <= tt && i < cnt + 1; i++) sum += sz[i];
cout << sum - 1 << endl;
}
return 0;
}
|
