題解 CF545A 【Toy Cars】

• 2020 年 5 月 4 日
• 筆記
• C++, 題解

題目傳送門

太弱了，只能寫寫A題的題解

題意

給你一個 \(n·n\) 的矩陣，翻車分三種情況：

• 如果 \(a_i,_j=1\) ，記錄第 \(i\) 輛車
• 如果 \(a_i,_j=2\) ，記錄第 \(j\) 輛車
• 如果 \(a_i,_j=3\) ，記錄第 \(i\) 和 \(j\) 輛車
  問最後總共記錄多少輛車（不重複）？它們分別是第幾輛？

思路

這題可以用set (好喜歡用set)，因為set可以去重，用在這裡可以有效減少時間複雜度。
一邊輸入一邊將 \(i\) 或 \(j\) 存入set並標記bool數組，然後輸出 n-set的長度，最後再輸出沒有被標記的下標。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n;
bool f[N];
int main() {
    memset(f,false,sizeof f);
    cin>>n;
    set<int> s;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            int x;
            cin>>x;
            if(x==1) {
                s.insert(i);
                f[i]=1;
            }
            else if(x==2) {
                s.insert(j);
                f[j]=1;
            }
            else if(x==3) {
                s.insert(i);
                s.insert(j);
                f[i]=f[j]=1;
            }
        }
    }
    cout<<n-(int)s.size()<<endl;
    for(int i=1;i<=n;i++) if(!f[i]) cout<<i<<" ";
    return 0;
}