自学1

Problem1 明明的随机数

## 题目描述

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N <= 100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

## 输入格式

输入有两行,第 1 行为 1 个正整数,表示所生成的随机数的个数 N。

第 2 行有 N 个用空格隔开的正整数,为所产生的随机数。

## 输出格式

输出也是两行,第 1 行为 1 个正整数 M,表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

## 样例输入

10

20 40 32 67 40 20 89 300 400 15

## 样例输出

8
15 20 32 40 67 89 300 400

## 题解

由题目可知,这是一道关于“排序”和“去重”的问题,我们首先要进行排序,因为排序后的数列如果有相同的数字那一定是连续的,可以由它后面的一个数字代替(即当出现相同数字时,后面整体数字前移一位)。

## AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main() {
 5     int n, sum = 0;
 6     int a[110];
 7     cin >> n;
 8     for(int i = 1; i <= n; i ++)
 9         cin >> a[i];
10     sort(a + 1, a + 1 + n);
11     for(int i = 1; i <= n; i ++)
12         if(a[i] != a[i + 1])
13             sum ++;
14     cout << sum << endl;
15     for(int i = 1; i <= n; i ++)
16         if(a[i] != a[i + 1])
17             cout << a[i] << " ";
18     return 0;
19 }

## 拓展

这道题可以通过使用STL做,代码如下:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 set<int> s;
 5 
 6 int main() {
 7     int n, num;
 8     cin >> n;
 9     for(int i = 0; i < n; i ++) {
10         cin >> num;
11         s.insert(num);
12     }
13     cout << s.size() << endl;
14     while(s.empty() == 0) {
15         cout << *s.begin() << " ";
16         s.erase(s.begin());
17     }
18     return 0;
19 }

Problem2 村村通

## 题目描述

某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路?

## 输入格式

输入包含若干组测试数据,每组测试数据的第一行给出两个用空格隔开的正整数,分别是城镇数目 n 和道路数目 m ;随后的 m 行对应 m 条道路,每行给出一对用空格隔开的正整数,分别是该条道路直接相连的两个城镇的编号。简单起见,城镇从 1 到 n 编号。

注意:两个城市间可以有多条道路相通。

在输入数据的最后,为一行一个整数 00,代表测试数据的结尾。

## 输出格式

对于每组数据,对应一行一个整数。表示最少还需要建设的道路数目。

## 样例输入

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

## 样例输出

1
0
2
998

## 题解

这道题考察的是并查集。

我们首先要处理每一条存在的边,把所有存在的边所连接的两个结点用并查集合并。

然后记录不同的代表元素个数,即可得知连通块数量。

## AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int f[N];
 6 int n, m;
 7 
 8 //初始化
 9 void init() {
10     for(int i = 1; i <= n; i ++)
11         f[i] = i;//自己的父亲就是自己
12 }
13 
14 //寻找祖先
15 int find(int x) {
16     if(f[x] == x)
17         return x;
18     return f[x] = find(f[x]);
19 }
20 
21 int main() {
22 
23     while(cin >> n >> m) {
24         init();
25         while(m --) {
26             int a, b;
27             cin >> a >> b;
28             int x = find(a), y = find(b);//压缩路径
29             f[x] = y;
30         }
31         int ans = 0;
32         for(int i = 1; i <= n; i ++)
33             if(f[i] == i)//合并集合后,自己的父亲就是自己的,视作生成树
34                 ans ++;
35         //ans个连通块可以看作ans个结点,那么ans个结点并入一个生成树需要ans-1条边
36         cout << ans - 1 << endl;
37     }
38     return 0;
39 }

 

热门相关:首席的独宠新娘   仗剑高歌   仗剑高歌   大神你人设崩了   惊世毒妃:轻狂大小姐