关于 B - Star or Not 的一些领悟

2024-03-06 15:15:02

原题：UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200200 points

Problem Statement

You are given a tree with NN vertices and N-1N−1 edges.
The vertices are numbered 1,2,\ldots,N1,2,…,N. The ii-th edge connects Vertex a_iai and Vertex b_ibi.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

3 \leq N \leq 10^53≤N≤105
1 \leq a_i \lt b_i \leq N1≤ai<bi≤N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

NN
a_1a1 b_1b1
\vdots⋮
a_{N-1}aN−1 b_{N-1}bN−1

Output

If the given graph is a star, print Yes; otherwise, print No.

Sample Input 1 Copy

Sample Output 1 Copy

Yes

The given graph is a star.

Sample Input 2 Copy

Sample Output 2 Copy

No

The given graph is not a star.

Sample Input 3 Copy

Sample Output 3 Copy

Yes

先说一下个人思路：

由于没有接触过树的学习，所以做这题时有些费劲！

个人认为，需要将两列组合起来，形成一个新的数组，

然后进行除重操作，利用最近刚学的 unique 函数，

实际上，利用的是 C++ 独有的 STL 容器。

再利用 sort 进行排序，如果这些数的最小值到最大值中间没有间断，

输出 “YES” ，反之，输出 “NO” 。

WA：

/*
      B  Star or Not
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 1000+100
using namespace std;

int main(){
    long long n, i = 0;
    cin >> n;
    int a[maxn*2], b[maxn];
    while(n--){
        cin >> a[i] >> b[i];
        i++;
    }
    for (int j = n, c = 0; j < 2 * n, c < n; j++)
    {
        a[j] = b[c];
    }
    int len;
    len = unique(a, a + 2 * n) - a;
    for (int c = 0; c < len;c++){
        cout << a[c] <<" ";
    }
        return 0;
}

接下来，介绍下一个提速的操作：

std::ios::sync_with_stdio(false);

经常出现程序无故超时，最终发现问题处在cin和cout上，这是因为C++中，cin和cout要与stdio同步，中间会有一个缓冲，所以导致cin，cout语句输入输出缓慢，这时就可以用这个语句，取消cin，cout与stdio的同步，说白了就是提速，效率基本与scanf和printf一致。然后就可放心的使用cin，cout了。

tip:

其实cin和cout也可以像scanf和printf一样快

只不过是C++为了兼容C，避免一些问题

cin构造出来就会调用cin.tie();与cout绑定

cin的每次格式化输入都会调用cout.flush();导致效率低

可以使用cin.tie(NULL);解除绑定

cout.tie(NULL);

AC：

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x, y;
    cin >> n;
    int a[n+1] = {0};
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        a[x]++;
        a[y]++;
    }
    x = 0;
    for(int i = 1; i <= n; i++) if(a[i] > 1) x++;
    if(x == 1) cout << "Yes";
    else cout << "No";
    return 0;
}

有些小细节在里面，上面介绍的提速操作就运用到了！

还有些大佬用 map 和 vector 来写：

MAP

#include <bits/stdc++.h> using namespace std; typedef long long int ll;
int main() { map<int, int> deg; int n; cin >> n; int flag = 0; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; deg[a]++; deg[b]++; if (deg[a] == n - 1) flag = 1; if (deg[b] == n - 1) flag = 1; } if (flag) cout << "Yes" << endl; else cout << "No" << endl; }

VECTOR

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n + 1, 0);
    for (int i = 1; i <= n - 1; i++){
        int a, b;
        cin >> a >> b;
        v[a]++;
        v[b]++;
    }
    for (int i = 1; i <= n; i++){
        if (v[i] == n - 1){
            cout << "Yes" << "\n";
            return 0;
        }
    }
    cout << "No" << "\n";
    return 0;
}

显然 map 比 vector 更加高效！

码农公寓