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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550945.html
標籤：其他
上一篇：AtCoder Beginner Contest 299
下一篇：返回列表