alan23273850 的刷題筆記
d275: 11586 - Train Tracks
Tags: puzzle
出處：https://zerojudge.tw/ShowProblem?problemid=d275
提交：https://zerojudge.tw/Submissions?problemid=d275&account=allllllan123456
問題：給定 1 ~ 50 個軌道片段，每個片段可以兩端都是公頭、兩端都是母頭，或者是一端公頭、一端母頭，任兩個不同片段必須透過公頭與母頭方能相結合，請問這些片段能否拼裝成一個環形軌道？不考慮長度、形狀。
解法：這題用不著圖論，其實很簡單。只有一個片段的話確定不行，兩個片段以上的話只要全部片段的公頭與母頭的數量總和一樣多，就必定能拼裝成環形軌道，按照下面的要領操作即可：(MMFF)…(MMFF)(MF)…(MF)。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int T; cin >> T >> ws; // 消化 T 後面多餘的無效字元
6 while (T--) { string str;
7 getline(cin, str); int mm = 0;
8 if (str.length() <= 3) cout << "NO ";
9 else {
10 for (int j=0; j<str.length(); j+=3)
11 if (str[j] == str[j+1]) {
12 if (str[j] == 'M') mm++;
13 if (str[j] == 'F') mm--;
14 }
15 if (mm) cout << "NO ";
16 }
17 cout << "LOOP\n";
18 }
19 return 0;
20}