信息奥赛题单｜set

本篇博客还在持续更新润色中～

STL - set

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
HDU - 2095	find your present(2)	链接🔗	思维 + set	🟢
AtCoder - ABC 118C	Monsters Battle Royale	链接🔗	set + stack	🟢
HDU - 2094	产生冠军	链接🔗	思维 + set	🟡

---

题解 🚀

find your present(2)

题目信息 📚

【题目名称】HDU 2094 - find your present(2)

【题目描述】

In the new year party, everybody will get a “special present”. Now it’s your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.

Each present has a card number on it, and your present’s card number will be the one that different from all the others, and you can assume that only one number appear odd times.

For example, there are $5$ present, and their card numbers are $1, 2, 3, 2, 1$. so your present will be the one with the card number of $3$, because $3$ is the number that different from all the others.

【输入】

The input file will consist of several cases, you need to terminate your program when $n=0$.

Each case will be presented by an integer $n\ (1\le n\lt 1000000\text{, and }n\text{ is odd})$ at first.

Following that, n positive integers will be given in a line, all integers will smaller than $2^{31}$. These numbers indicate the card numbers of the presents.

【输出】

For each case, output an integer in a line, which is the card number of your present.

【输入样例】

5
1 1 3 2 2
3
1 2 1
0

【输出样例】

3
2

【原题链接】

https://vjudge.net/problem/HDU-2095

---

题目解析 🍉

【题目分析】

法一：利用 set.find 和 set.erase，在 log(n) 的复杂度内完成查找和删除

法二：利用 「异或」运算（本质是不进位加法），消除所有偶数个相同的数，留下唯一出现1次的数字。

【C++ 代码】set ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, tmp;

int main() {
    while (scanf("%d", &n) != EOF && n != 0) {
        // 创建一个set
        set<int> s;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            // 当前set中找不到该元素，就加入set
            if (s.find(tmp) == s.end())
                s.insert(tmp);
            else  // 当前set可以找到该元素，将其消除
                s.erase(tmp);
        }
        for (auto t: s) printf("%d\n", t);
    }

    return 0;
}

【C++ 代码】异或和 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, tmp;

int main() {
    while (scanf("%d", &n) != EOF && n != 0) {
        // 输出异或和
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            sum = sum ^ tmp;
        }
        printf("%d\n", sum);
    }

    return 0;
}

---

Monsters Battle Royale

题目信息 📚

【题目名称】AtCoder ABC 118C - Monsters Battle Royale

【题目描述】

There are $N$ monsters, numbered $1, 2, …, N$.

Initially, the health of Monster $i$ is $A_i$.

Below, a monster with at least $1$ health is called alive.

Until there is only one alive monster, the following is repeated:

• A random alive monster attacks another random alive monster.
• As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.

Find the minimum possible final health of the last monster alive.

【输入】

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\ldots$ $A_n$

【输出】

Print the minimum possible final health of the last monster alive.

【输入样例】

4
2 10 8 40

【输出样例】

2

【原题链接】

https://atcoder.jp/contests/abc118/tasks/abc118_c

---

题目解析 🍉

【题目分析】

法一：利用 set 的自动升序、$O(logn)$ 插入和 stack 模拟该过程。

法二：对于两个怪兽来说，互相攻击存活的最小血量，其实是他们的 $gcd$（更相减损法）

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n, tmp;

int main() {
    set<int> s;
    set<int>::iterator it;
    // 读入数据，并且将数据存入set中（自动升序）
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        s.insert(tmp);
    }

    // 用stack存储当前最小值
    stack<int> st;
    while (!s.empty()) {
        // 取出set中最小的元素，并且在set中"弹出"（利用set.erase）
        it = s.begin();
        s.erase(*it);

        // 若当前栈为空，将该元素直接存入栈中
        if (st.empty()) {
            st.push(*it);
        } else {
            // 当前栈非空，则将栈顶元素与该元素的取模值进行比较
            // 若取模值为0，说明该元素可以被栈顶元素一直攻击，直至消去
            int m = *it % st.top();
            if (m) {
                // 若取模值不为0，说明该元素可以被攻击到小于栈顶元素，且无法消去
                // 此时弹出栈顶元素，并将栈顶元素重新加入set
                // 往栈中推入更小的取模值
                s.insert(st.top());
                st.pop();
                st.push(m);
            }
        }
    }
    // 最后的栈顶元素即为答案
    cout << st.top() << endl;

    return 0;
}

---

产生冠军

题目信息 📚

【题目名称】HDU 2094 - 产生冠军

【题目描述】

有一群人，打乒乓球比赛，两两捉对撕杀，每两个人之间最多打一场比赛。

球赛的规则如下：

• 如果 A 打败了 B，B 又打败了 C，而 A 与 C 之间没有进行过比赛，那么就认定，A 一定能打败 C。
• 如果 A 打败了 B，B 又打败了 C，而且 C 又打败了 A，那么 A、B、C 三者都不可能成为冠军。

根据这个规则，无需循环较量，或许就能确定冠军。你的任务就是面对一群比赛选手，在经过了若干场撕杀之后，确定是否已经实际上产生了冠军。

【输入】

多组数据，请处理到 $n=0$ 为止。

每组数据以一个整数 $n\ (n\lt 1000)$ 开头，后跟 $n$ 对选手的比赛结果，比赛结果以一对选手名字（中间隔一空格）表示前者战胜后者。

【输出】

对于每组数据，若你判断出产生了冠军，则在一行中输出 Yes，否则在一行中输出 No。

【输入样例】

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

【输出样例】

Yes
No

【原题链接】

https://vjudge.net/problem/HDU-2094

---

题目解析 🍉

【题目分析】

思维题。

结合 STL 中的 set 使用，效果巨佳。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    string win, lose;
    while (cin >> n && n) {
        // 设定两个集合，存储胜者和败者
        set<string> winners, losers;

        // 根据n轮结果，往集合中加入玩家
        for (int i = 1; i <= n; i++) {
            cin >> win >> lose;
            // 当前赢家未出现在败者名单中，将其加入胜者名单
            if (losers.find(win) == losers.end()) winners.insert(win);
            // 当前败者出现在胜者名单中，将其从胜者名单中抹去
            if (winners.find(lose) != winners.end()) winners.erase(lose);
            losers.insert(lose);
        }
        // 判断是否有胜者
        if (winners.size() == 1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

---