owned this note
owned this note
Published
Linked with GitHub
# 1205 題解
## A
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
// 用一個 set 記錄所有輸入過的詞
set<string> dict;
string tmp;
while (cin >> tmp) {
string toInsert = "";
for (int i = 0; i < tmp.length(); i++) {
if (isalpha(tmp[i])) {
toInsert += tolower(tmp[i]);
} else {
if (toInsert.length() > 0) dict.insert(toInsert);
toInsert = "";
}
}
if (toInsert.length() > 0) {
dict.insert(toInsert);
}
}
for (auto s : dict) {
cout << s << endl;
}
}
```
## B
這題蠻多做法的,這裡用 set 存已經計算過的醜數,並用 priority queue 紀錄接下來要操作(x2、x3、x5)的數。因為操作的過程中會爆 int 變成負數導致 priority queue 爆炸,所以要用 long long。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
set<long long> s;
priority_queue<long long, vector<long long>, greater<long long>> pq;
pq.push(1);
s.insert(1);
int cnt = 0;
long long tmp;
while (cnt < 1500) {
tmp = pq.top();
pq.pop();
int mul[] = {2, 3, 5};
for (int i = 0; i < 3; i++) {
long long meow = tmp * mul[i];
if (s.find(meow) == s.end()) {
pq.push(meow);
s.insert(meow);
}
}
cnt++;
}
cout << "The 1500'th ugly number is " << tmp << "." << endl;
return 0;
}
```
## C
```cpp
#include <iostream>
#include <queue>
#include <sstream>
#include <string>
#include <utility>
#include <algorithm>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// 用來檢查是否超過 5x5 的框框
bool inBound(int x, int y) {
if (x < 0 || y < 0 || x >= 5 || y >= 5) {
return false;
}
return true;
}
int main() {
// m:地圖
// path:路徑
int m[5][5];
int path[5][5] = {0};
path[0][0] = 1;
// 輸入
for (int i = 0; i < 5; i++) {
for (int k = 0; k < 5; k++) {
cin >> m[i][k];
}
}
// way 紀錄下一個要走的方塊
queue<pair<int, int>> way;
int x = 0, y = 0;
way.push(make_pair(0, 0);
// 當 queue 裡面有東西就表示還沒走完
while (!way.empty()) {
pair<int, int> p = way.front();
way.pop();
x = p.first, y = p.second;
int nextStep = path[x][y] + 1;
// 將上、下、左、右四個方向的框框加進 way,並記錄其 path
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (inBound(tx, ty) && path[tx][ty] == 0 && m[tx][ty] == 0) {
path[tx][ty] = nextStep;
way.push(make_pair(tx, ty));
}
}
}
// 從尾巴開始走回來並處理輸出
x = y = 4;
stringstream ss;
while (x != 0 || y != 0) {
ss << "\n)" << y << " ," << x << '(';
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (inBound(tx, ty) && path[tx][ty] == path[x][y] - 1) {
x = tx;
y = ty;
break;
}
}
}
ss << "\n)" << 0 << " ," << 0 << '(';
string output = ss.str();
reverse(output.begin(), output.end());
cout << output << endl;
}
```
## D
```cpp
#include <iostream>
using namespace std;
bool map[105][105] = {0};
bool visited[105] = {0};
int d[105] = {0};
int f[105] = {0};
int timestamp = 0;
int n;
void dfs(int now) {
visited[now] = true;
d[now] = ++timestamp;
for (int i = 1; i <= n; i++) {
if (map[i][now] && !visited[i]) {
dfs(i);
}
}
f[now] = ++timestamp;
}
int main() {
// 輸入
cin >> n;
for (int i = 0; i < n; i++) {
int u;
cin >> u;
map[u][u] = true;
int k;
cin >> k;
for (int s = 0; s < k; s++) {
int t;
cin >> t;
map[t][u] = true;
}
}
// 開始搜尋
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
}
}
// 輸出
for (int i = 1; i <= n; i++) {
cout << i << " " << d[i] << " " << f[i] << endl;
}
}
```