AcWing第18场周赛

第18场周赛

地址：https://www.acwing.com/activity/content/introduction/73/

战绩

A	B	C	得分	时间	排名
1	1	0	2	0:30:33	186/1061

题目

A: AcWing 3988. 不同的数

知识点：哈希

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;

int n, k;
unordered_map<int, int> mp;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        mp[x] = i;
    }
    
    if (mp.size() < k) {
        puts("NO");
    }else {
        puts("YES");
        int cnt = 0;
        for (auto [x, idx] : mp) {
            if (++cnt > k) break;
            cout << idx << " ";
        }
    }
    return 0;
}

B: AcWing 3989. 看图做题

知识点：找规律

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << 6 * n * (n - 1) + 1 << endl;
    return 0;
}

C:3990. 砍树

知识点：贪心、思维题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100010;
int n;
vector<int> q[N];
int ans = 0;

int dfs(int u, int father) {
    int sz = 1;
    for (int c : q[u]) {
        if (c == father) continue;
        int s = dfs(c, u);
        if (s % 2== 0) ans ++;
        sz += s;
    }
    return sz;
}
int main()
{
    cin >> n;
    if (n & 1) {
        puts("-1");
        return 0;
    }
    for (int i = 1; i < n; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        q[a].push_back(b);
        q[b].push_back(a);
    }
    
    dfs(1, -1);
    
    cout << ans;
    
    return 0;
}