歡迎辭歡迎來到“篤志以礪，決起而飛”！ 如果您是第一次來到本站，建議訪問 本站導讀以便更快地了解本站。 如果您喜歡本站， 歡迎訂閱。 | 一道非常簡單的並查集題目，只需要把每組人均合併到一起。最後統計和 0 是一個父親的數量即可，20 分鐘 Accepted. 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
| /* POJ 1611
* By Ceeji
* Union
*/
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_N 30000
int m, n;
int father[MAX_N];
int get_father(const int p)
{
if (father[p] == -1 || father[p] == p)
{
father[p] = p;
return p;
}
father[p] = get_father(father[p]);
return father[p];
}
void set_union (const int x, const int y)
{
int fx = get_father (x);
int fy = get_father (y);
father[fx] = fy;
}
void do_work ()
{
for (int i = 0; i < MAX_N; ++i)
father[i] = -1;
for (int j = 0; j < m; ++j)
{
int gn, tmp, first;
cin >> gn >> first;
for (int i = 0; i < gn - 1; ++i)
{
cin >> tmp;
if (get_father(tmp) != get_father(first))
set_union (tmp, first);
}
}
int f = get_father(0);
int num = 0;
for (int i = 0; i < n; ++i)
{
if (get_father(i) == f)
++num;
}
cout << num << endl;
}
int main ()
{
while (true)
{
cin >> n >> m;
if (m == 0 && n == 0)
return 0;
do_work ();
}
return 0;
} |
1、二胡曲：賽馬 音頻片段：需要 Adobe Flash Player（9 或以上版本）播放音頻片段。 點擊這裡下載最新版本。您需要開啟瀏覽器的 JavaScript 支持。 可以說，賽馬貫穿了我的整個音樂生涯。在小時候學習電子琴的時候，賽馬是我最為拿手的曲目之一。後來，我參加全國冰心藝術器樂大賽，這首曲目的單人雙琴表演獲得了冰心藝術特別獎。在初中的一次由口語老師舉辦的聖誕晚會上，我受邀再次表演了這首曲子，這時候距離我開始接觸這個曲目估計有六年了吧。
後來學習鋼琴，這首曲目並不適合鋼琴演奏，但是我還是時不常地喜歡在鋼琴上彈一下。高三時學習竹笛，雖然吹得不好，但是我也經常會吹一下這首曲目。
到了現在，賽馬已經融入了我的靈魂，我也非常敬仰創作這首樂曲的大師。
我演奏的樂器並不是這首曲目原本的演奏樂器。這是一首二胡曲目，是根據中國北方少數民族蒙古族音樂創作而成。樂曲將蒙古風格的音階和節奏同漢族音樂中常用的裝飾音巧妙地結合使用，使樂曲即有歡快奔騰的場景，又有抒情般地歌唱景象。同時，撥奏和連奏的技巧運用，使樂曲顯得更加生動活潑。 2、沙巴（的）女王 音頻片段：需要 Adobe Flash Player（9 或以上版本）播放音頻片段。 點擊這裡下載最新版本。您需要開啟瀏覽器的 JavaScript 支持。 這首樂曲是我小時候印象很深刻的樂曲之一，主要原因是風格比較迥異。時隔這麼多年，還能回想起當初的感覺。 3、鋼琴曲：水邊的阿狄麗娜 音頻片段：需要 Adobe Flash Player（9 或以上版本）播放音頻片段。 點擊這裡下載最新版本。您需要開啟瀏覽器的 JavaScript 支持。 第一次聽到它是在理查德的一張音樂專輯上。當時看到屏幕上的高山、流水、清音，簡直不能自己。現在也是我最喜歡彈奏的鋼琴曲目。 4、鋼琴曲：夢中的婚禮 音頻片段：需要 Adobe Flash Player（9 或以上版本）播放音頻片段。 點擊這裡下載最新版本。您需要開啟瀏覽器的 JavaScript 支持。 多麼想和我的她擁有一場如夢一般的婚禮。 5、竹笛：姑蘇行 音頻片段：需要 Adobe Flash Player（9 或以上版本）播放音頻片段。 點擊這裡下載最新版本。您需要開啟瀏覽器的 JavaScript 支持。 江南，這一讓人柔情似水的字眼；小橋、流水、人家。當站在那一葉扁舟之上，吹着姑蘇行，欣賞蘇州園林的美景，這是一種怎樣的情懷？我最喜歡的竹笛曲目之一。 這道題是一道並查集的題目。和普通並查集相比，主要有幾點需要注意：
1、注意空樹的處理。
2、如果在合併的時候，這兩個點已經在樹中，說明路徑重複，不是合法的樹。 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
| /* POJ 1308
* By Ceeji
* http://poj.org/problem?id=1308
*
*/
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 200;
int father[MAX_N];
bool has_point[MAX_N];
int case_number = 0;
void init_set ()
{
memset (father, 0, sizeof(father)); // 0 means that the father is itself.
memset (has_point, 0, sizeof(has_point));
}
int get_father (const int i)
{
if (father[i] == 0 || father[i] == i)
{
father[i] = i;
return i;
}
int tmp = get_father(father[i]);
father[i] = tmp;
return tmp;
}
/* union : point x to y */
void set_union (const int x, const int y)
{
int fx = get_father(x);
int fy = get_father(y);
father[fx] = fy;
}
int maxof (const int x, const int y)
{
return x > y ? x : y;
}
int do_work ()
{
init_set ();
int s, t, max = 0;
bool finish = false;
while (cin >> s >> t)
{
if (s > 0 && t > 0) // if s or t is not greater than 0, it is the end descripter.
{
max = maxof (maxof (max, s), t);
has_point[s] = true;
has_point[t] = true;
if (get_father(s) != get_father(t))
set_union(s, t);
else
{
cout << "Case " << case_number << " is not a tree." << endl;
finish = true;
}
}
else
{
if (s == -1 && t == -1)
{
return 1;
}
break;
}
}
if (!finish)
{
int f = get_father(max);
for (int i = 2; i <= max; ++i)
if (has_point[i] && get_father(i) != f)
{
cout << "Case " << case_number << " is not a tree." << endl;
finish = true;
break;
}
}
if (!finish)
cout << "Case " << case_number << " is a tree." << endl;
return 0;
}
int main()
{
while (true)
{
++case_number;
if (do_work())
return 0;
}
return 0;
} |
在 C++ 中，我們可以利用下面的方法，將一個十進制數直接轉換為二進制數並輸出。
1、bitset<size_t len> 類型可以代表任意長度的二進制集合。
2、bitset<size_t len>() 構造函數可以將一個十進制數轉換為其二進制形式。
3、stream << bitset<size_t len> 被重載，可以自動輸出 bitset 的值。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <limits>
#include <bitset>
using namespace std;
int main()
{
/*
Use bitset to create a binary set.
numeric_limits<unsigned int>::digits is the binary length of type unsigned int.
use constructor : bitset<T>(unsigned int binary_length);
*/
cout << bitset<numeric_limits<unsigned int>::digits>(123) << endl;
return 0;
} |
這道題是一個純粹的深度優先搜索，而且是其中最簡單的一種：不需要判重。 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
| /*
* POJ 1321
* URL: http://poj.org/problem?id=1321
* Author: Ceeji Cheng
* Type: Depth First Search
* Status: Programing
* Visit http://ceeji.net/ for more information.
* 2011-02-24 15:34
*/
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAX_N 8
int matrix[MAX_N][MAX_N];
bool has[MAX_N];
int n, k, res = 0;
string ts;
void search(int p, int line)
{
if (line >= n)
{
if (p == k)
++res;
return;
}
for (int i = 0; i < n; ++i)
{
if (matrix[line][i] && !has[i])
{
has[i] = true;
search(p + 1, line + 1);
has[i] = false;
}
}
search(p, line + 1);
}
int main (int argc, char const* argv[])
{
while (cin >> n >> k && n != -1)
{
// clear the matrix.
memset(matrix, 0, sizeof(matrix));
// init.
for (int i = 0; i < n; ++i)
{
cin >> ts;
for (int j = 0; j < n; ++j)
matrix[i][j] = ts[j] == '#' ? 1 : 0;
}
res = 0;
search(0, 0);
cout << res << endl;
}
return 0;
} |
| |
近期評論