题解 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;
}