1. 路徑偵測
用三個變數 x, y, dir 分別記錄現在的 x 座標，y 座標，以及前進的方向。每次走到一個新的點就可以利用新的方向與舊的方向判斷需不需要轉彎或是迴轉。我自己的寫法是用數字表示方向，並從 0 是右邊開始逆時針表示 1: 上, 2: 左, 3: 下。找到自己習慣的方式寫就可以了!
複雜度: O(n)
主要知識: 條件判斷與迴路 (conditional expressions and loop)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int x = 0, y = 0, dir = 0;
int left = 0, right = 0, turn = 0;
// 0: 右, 1: 上, 2: 左, 3: 下
for(int i = 0;i < n;i++) {
int nx, ny;
cin >> nx >> ny;
if(nx == x) { // x 座標不變，所以是垂直移動
if(ny > y) { // 往上走
if(dir == 0) left ++;
if(dir == 2) right ++;
if(dir == 3) turn ++;
dir = 1;
} else { // 往下走
if(dir == 2) left ++;
if(dir == 0) right ++;
if(dir == 1) turn ++;
dir = 3;
}
} else { // 水平移動
if(nx > x) { // 往右走
if(dir == 3) left ++;
if(dir == 1) right ++;
if(dir == 2) turn ++;
dir = 0;
} else { // 往左走
if(dir == 1) left ++;
if(dir == 3) right ++;
if(dir == 0) turn ++;
dir = 2;
}
}
x = nx, y = ny;
}
cout << left << ' ' << right << ' ' << turn << '\n';
}2. 特殊位置
先宣告一個二維陣列把輸入儲存下來。由於 n, m 都很小 (50 ^ 4 = 6.25 * 10^6)，我們可以直接枚舉每個點 (i, j)，把對於他曼哈頓距離 <= a[i][j] 的位置的值都加起來。計算曼哈頓距離的方式可以用 C++ 的 abs 函數，判斷 abs(x1 – x2) + abs(y1 – y2) 是不是 <= x。
複雜度: O(n^2m^2)
主要知識: 條件判斷與迴路 (conditional expressions and loop)，陣列與結構 (arrays and structures)
#include <bits/stdc++.h>
using namespace std;
int a[55][55];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
cin >> a[i][j];
}
}
vector <pair<int,int> > ans; // 紀錄特殊位置的座標
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
int sum = 0;
int x = a[i][j];
for(int ni = 0;ni < n;ni++){
for(int nj = 0;nj < m;nj++){
if(abs(ni-i) + abs(nj-j) <= x) { // 判斷曼哈頓距離是否 <= a[i][j]
sum += a[ni][nj];
}
}
}
if(sum % 10 == x) ans.push_back({i, j});
}
}
cout << ans.size() << '\n';
for(auto p : ans) {
cout << p.first << ' ' << p.second << '\n';
}
}3. 磁軌移動序列
我們可以發現一個迴圈裡面的指針的距離可以用乘的方式計算，不需要每次都重新跑。
例如 L5T10T20，我們實際上只需要算 abs(10 – 20) * 5 就可以了。
因此，我們的想法是開一個變數 mul，來計算現在這兩個指針的移動距離需要乘上幾倍。
但是，要注意雖然迴圈裡的兩個指針的距離是不變的，但是第一個指針與上一個在迴圈外的指針的距離並不應該被算到迴圈裡面。只有第一次進入迴圈時，這個距離會被算到。之後，我們應該是要用迴圈裡的最後一個指針跟第一個指針的距離計算才是對的。
因此，我們可以用一個 stack 來記錄所有迴圈的資訊。我們想要紀錄每個迴圈會重複幾次，以及迴圈中的第一個指針在哪。用 stack 的原因是越後面進來的迴圈，也就是越內層的迴圈，應該要越早離開，而 stack 的後進先出特性就很適合。
而記錄每個迴圈的次數很簡單，只要拿到 L 下一個數字就可以了。只是迴圈中的第一個數字並不一定會馬上出現在 L 後面，例如: L9L9L9T22EEE。
所以，我們可以在每次遇到一個 T 的指針位置時，在 stack 往前看，有沒有迴圈還沒有數字的，有的話就把現在的數字當成那些迴圈的第一個數字即可。在往前看時，順便把那些還沒有數字的迴圈的次數都乘進變數 mul，因為之後的距離都應該要乘上那些迴圈的次數。但是，要注意，我們應該先把這個數字與上一個數字的距離先加進答案，因為這個距離不會被迴圈重複。
在遇到 L 時，我們就先把次數推進去 stack，並把第一個數字的值設定成 -1，代表還沒有。
遇到 E 時，代表 stack 最上面的迴圈應該要退出了。因為這會是最後一個數字，我們要把他跟第一個數字的距離乘以 (次數 – 1) ，要 -1 是因為第一次應該是迴圈外的數字進來迴圈第一個數字的距離，之後才會是最後一個數字跟第一個數字的距離。計算完之後將 stack 最上面的迴圈 pop 掉。
記得數字範圍可能會到 2^60，所以要開 long long !
另外，這題也有遞迴的解題方法，不過因為用 stack 我感覺比較方便而且會跑比較快。各位同學也可以想想要怎麼用遞迴！
複雜度: O(|s|)
主要知識: 堆疊 (stacks), 函數呼叫與遞迴 (function call and recursion)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
long long mul = 1;
int now = 10; // 初始位置為 10
long long ans = 0;
stack <pair<int, long long> > st; // <第一個數字, 次數>
for(int i = 0;i < s.size();i++) {
if(s[i] == 'T') {
int nnow = stoi(s.substr(i+1, 2));
vector <pair<int,int> > tmp;
ans += abs(nnow - now) * mul;
while(!st.empty() && st.top().first == -1) {
tmp.push_back({nnow, st.top().second});
mul *= st.top().second;
st.pop();
}
reverse(tmp.begin(), tmp.end());
for(auto p : tmp) st.push(p);
now = nnow;
i += 2;
} else if(s[i] == 'L'){
int cnt = (int)(s[i+1] - '0');
st.push({-1, cnt});
i += 1;
} else if(s[i] == 'E'){
int cnt = st.top().second;
int first_num = st.top().first;
mul /= cnt;
ans += abs(now - first_num) * (cnt - 1) * mul;
st.pop();
}
}
cout << ans << '\n';
}4. 開啟寶盒
我們可以用圖論的方式思考這題，把鑰匙以及寶箱當作點。如果我們把一個寶箱需要的鑰匙的關係寫成 鑰匙 -> 寶箱，並且寶箱打開可以獲得的鑰匙寫成 寶箱 -> 鑰匙，要打開一個寶箱的話，必須所有連到他的點都先被走過，而打開寶箱之後，他連到的點都可以走。
我們可以用拓撲排序來處理連到寶箱的點都要先被走過才可以走到寶箱。
只是寶箱連到鑰匙的部分就跟原本的拓撲排序不太一樣，要改成只要走到就可以直接用。雖然這題可能會有環的存在，但是我們可以用 visited 陣列避免，因為實際上我們走過一個點，就不需要再走一次了。如果是寶箱的話，就把鑰匙都加入隊列。如果是鑰匙的話，就把所有連到的寶箱 in degree – 1。
其實這題只要這樣就可以做完了。實作上，我是把寶箱的編號設定成 m ~ m+n-1，這樣可以很方便判斷一個點是寶箱還是鑰匙。
複雜度: O(k(m + n))
主要知識: 圖形 (graph)
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2e5 + 5;
vector <int> G[mxn];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
int t;
cin >> t;
queue <int> order;
vector <int> in(n+m, 0);
for(int i = 0;i < t;i++) {
int x;
cin >> x;
order.push(x);
}
for(int i = 0;i < n;i++) {
for(int j = 0;j < k;j++) {
int x;
cin >> x;
G[x].push_back(i+m);
in[i+m] ++;
}
}
for(int i = 0;i < n;i++) {
for(int j = 0;j < k;j++) {
int x;
cin >> x;
G[i+m].push_back(x);
}
}
int ans = 0;
vector <bool> vis(n+m, false);
while(!order.empty()) {
int u = order.front();
order.pop();
if(vis[u]) continue;
else vis[u] = true;
if(u >= m) ans ++;
for(int v : G[u]) {
if(v >= m) {
in[v] --;
if(in[v] == 0) {
order.push(v);
}
} else {
order.push(v);
}
}
}
cout << ans << '\n';
}
發表迴響