Uol 2025 Wk2 题解

Recount

问题描述

最近的学校董事会选举竞争异常激烈：提案内容包括互换中小学的上学时间，一项备受争议的禁止在校穿着运动服的新着装规定，以及一项旨在提高房地产税以资助新橄榄球训练设施的提案，诸如此类的议题层出不穷。现在，距离投票站关闭已过去数小时，但获胜者仍未揭晓！

在绝望之中，选举官员们求助于您，请您编写一个程序来统计选票！

输入

输入包含一个单一的测试用例，即一张已投选票的列表。输入中的每一行都包含一位被投票的候选人的名字。一个名字可能由多个单词组成，以空格分隔。单词包含字母或连字符，但不含其他标点符号。列表中至少有2张选票。选票列表以包含字符 *** 的单行结束。这一行不应被计入票数。最多可以有100,000张有效选票。

输出

如果某位候选人获得了简单多数或绝对多数的选票（即，票数超过任何其他候选人），则输出这位候选人的名字！如果没有候选人获得简单多数，则输出：“ Runoff!”（别忘了包含感叹号！）

代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

// using namespace std; // 为简洁起见，在单个文件中可以如此使用

namespace recount {
    int main(istream &cin, ostream &cout) {
        // 使用 unordered_map 存储每位候选人的票数。
        // 键是候选人的名字（字符串），值是他们的票数（无符号长整型）。
        std::unordered_map<std::string, unsigned long> m = std::unordered_map<std::string, unsigned long>();
        std::string line;

        // 逐行读取选票，直到遇到哨兵值 "***"。
        while(std::getline(cin, line)) {
            if(line == "***") {
                break;
            }
            // 为当前行所指的候选人增加票数。
            // 如果候选人尚不存在于哈希表中，则会以计票数为1被添加进去。
            m[line]++;
        }

        // 初始化一个字符串来存放获胜者的名字，以及一个变量用于存放最高票数。
        std::string ans             = "***"; // 使用哨兵值来检查是否存在平局。
        unsigned long max_vote = 0;

        // 第一遍遍历：找出所有候选人中的最高票数。
        for(const auto &[k, v]: m) {
            max_vote = std::max(max_vote, v);
        }

        // 第二遍遍历：找出获得最高票数的候选人。
        for(const auto &[k, v]: m) {
            if(v == max_vote) {
                // 如果 'ans' 不再是哨兵值，意味着我们已经找到了一个获胜者。
                // 此时再找到一个说明存在平局。
                if(ans != "***") {
                    cout << "Runoff!";
                    return 0; // 在打印平局结果后退出。
                }
                // 这是找到的第一个获得最高票数的候选人。
                ans = k;
            }
        }
        // 如果循环完成且 'ans' 只被更新过一次，则打印获胜者的名字。
        cout << ans;

        return 0;
    }
}

题解

这个问题要求我们处理一个投票列表，其中每一票都是一个代表候选人姓名的字符串。我们需要找出得票最多的候选人。如果只有一位候选人得票最高，我们就打印他/她的名字。如果有两位或更多的候选人并列获得最高票数，我们必须宣布“Runoff! ”。投票列表以一个特殊的字符串 *** 结尾。

为了解决这个问题，我们需要一种高效的方式来存储和统计可能非常多的不同候选人的票数。哈希表（或字典）是完成此任务的理想数据结构。在 C++ 中，std::unordered_map 就是哈希表的实现。我们可以将每个候选人的名字（std::string）映射到他们的总票数（一个整数类型，如 unsigned long）。

整体算法主要分为三个阶段：

首先，我们读取输入并统计票数。我们逐行遍历输入。对于每一行，也就是一张选票，我们检查它是否是终止符 *** 。如果是，我们停止读取。否则，我们用候选人的名字作为 unordered_map 的键，并增加其对应的值。std::unordered_map 的 [] 操作符在这里非常方便：如果键（名字）在哈希表中不存在，它会自动插入并赋予一个默认构造的值（对于整数是0），然后自增操作 ++ 使其变为1。如果键已经存在，它的值就简单地加一。

其次，处理完所有选票后，我们需要确定所有候选人中获得的最高票数是多少。我们可以通过遍历哈希表中的所有键值对，并记录下到目前为止看到的最大值（票数）来实现这一点。我们将这个最大值称为 max_vote。

第三，我们必须确定获胜者或检测是否存在平局。在寻找最大值的同时可靠地完成这项任务仅用一次遍历是不够的。因此，最简单明了的方法是对哈希表进行第二次遍历。在第二次迭代中，我们将每个候选人的票数与上一步中找到的 max_vote 进行比较。我们使用一个字符串变量，比如 winner_name，并将其初始化为一个特殊的哨兵值（例如输入中的 *** ，因为它不可能是合法的候选人名字）。当我们找到第一个票数等于 max_vote 的候选人时，我们将其名字存储在 winner_name 中。如果随后我们又遇到了另一位票数也等于 max_vote 的候选人，我们就知道出现了平局。此时，我们可以立即打印 “Runoff!” 并终止程序。如果第二次循环完成而没有找到第二个票数等于 max_vote 的候选人，那就意味着有唯一的获胜者，其名字已存储在我们的 winner_name 变量中。然后我们打印这个名字。

复杂度分析

设 N 为总投票数，C 为独立候选人的人数。设 L 为候选人名字的最大长度。

时间复杂度

这个过程可以分解为三个部分。

1. 读取选票并填充哈希表：我们循环 N 次。在循环内部，std::getline 需要 O(L) 的时间。使用字符串键访问 unordered_map 需要对字符串进行哈希计算，平均情况下需要 O(L) 的时间。因此，这个阶段的平均时间复杂度为 O(N * L)。
2. 找到最高票数：我们遍历存储在哈希表中的 C 位独立候选人。这需要 O(C) 的时间。
3. 确定获胜者或平局：我们再次遍历 C 位独立候选人，这也需要 O(C) 的时间。

总时间复杂度是这些部分的总和：O(N * L + C + C) = O(N * L + C)。由于独立候选人的人数 C 不能超过总投票数 N（即 C ≤ N），复杂度主要由第一阶段决定，最终的平均时间复杂度为 O(N * L)。

空间复杂度

主要的内存使用来自 unordered_map。在最坏的情况下，每一票都投给了不同的候选人，这意味着我们将存储 N 个不同的名字。哈希表所需的空间与独立候选人的人数 (C) 以及他们名字长度的总和成正比。在最坏的情况下，这会是 O(N * L)，即我们存储了 N 个平均长度为 L 的名字。因此，空间复杂度为 O(N * L)。

Set

问题描述

Set是一款由Marsha Falco于1974年设计的纸牌游戏，由Set Enterprises, Inc.公司推广。它也以联合供稿的形式出现在《纽约时报》的网站上。玩家会看到12张牌，每张牌上包含1、2或3个符号。这些符号可以是菱形、波浪形或椭圆形。符号的绘制风格有实心、条纹或空心三种。每个符号的颜色可以是红色、绿色或紫色。在任意一张牌上，所有符号的类型、颜色和填充风格都是相同的。

要构成一个“Set”，你必须选择三张牌，这三张牌的全部4个特性必须满足“要么全部相同，要么两两不同”的规则。例如，有3张牌，第一张显示2个红色条纹椭圆，第二张显示3个绿色条纹波浪形，第三张显示1个紫色条纹菱形，这就构成了一个“Set”。它们的符号数量分别为2、3和1（每个数量都不同）；形状分别为椭圆、波浪形和菱形（每种形状都不同）；颜色为红色、绿色和紫色（3种不同颜色）；最后，它们都共享相同的填充风格：条纹。

请编写一个程序，找出给定的12张牌中所有的“Set”！

输入

你的程序的输入将包括4行，每行包含3个字符串，代表3张牌。每个字符串由四个字符ABCD组成，其中

A ∈ {1, 2, 3}，对应符号的数量。

B ∈ {D, S, O}，对应菱形(D)、波浪形(S)和椭圆(O)。

C ∈ {S, T, O}，对应实心(S)、条纹(T)和空心(O)的填充风格。

D ∈ {R, G, P}，对应红色(R)、绿色(G)和紫色(P)。

可以认为输入中的卡牌排列如下： +———-+ | 1 2 3 | | 4 5 6 | | 7 8 9 | | 10 11 12 | +———-+

输出

输出你找到的所有“Set”，每行一个。对于每个“Set”，按排序顺序输出其中卡牌的编号。所有找到的“Set”应根据其第一张牌的编号进行排序，如果第一张牌编号相同，则按第二张和第三张牌的编号来打破平局。 如果无法构成任何“Set”，则输出“no sets”。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <unordered_set>

namespace set {
    std::vector<std::vector<int>> ans = {};

    class card {
    public:
        int id;
        char f[4];
        card(int id, std::string s);
    };

    class cardset {
    public:
        unsigned short mask = -1;
        int cnt             = 0;
        std::unordered_set<card *> cards{};
        cardset() = default;
        cardset(card *c);
        void insert(card *c);
    };

    cardset::cardset(card *c) {
        this->cards.insert(c);
        this->cnt = 1;
    }

    unsigned short calc_mask(card *c1, card *c2) {
        unsigned short mask = 0;
        for(int i = 0; i < 4; i++) {
            mask <<= 1;
            mask |= c1->f[i] == c2->f[i];
        }
        return mask;
    }

    card::card(int id, std::string s) {
        this->id = id;
        std::istringstream iss(s);
        iss >> this->f[0] >> this->f[1] >> this->f[2] >> this->f[3];
    }

    void cardset::insert(card *c) {
        if(this->mask == (unsigned short) (-1)) {
            this->mask = calc_mask(c, *this->cards.begin());
        }
        this->cards.insert(c);
        this->cnt++;
        if(this->cnt == 3) {
            std::vector<int> vec = {};
            for(auto &card_ptr: this->cards) {
                vec.emplace_back(card_ptr->id);
            }
            std::sort(vec.begin(), vec.end());
            ans.emplace_back(vec);
        }
    }

    bool fit(card *c, const cardset *s) {
        if(s->mask == (unsigned short) (-1)) {
            return true;
        }
        for(auto &sc: s->cards) {
            if(calc_mask(sc, c) != s->mask) {
                return false;
            }
        }
        return true;
    }

    int main(std::istream &cin, std::ostream &cout) {
        cardset sets[1 << 10] = {};
        int sets_cnt          = 0;
        std::string input;
        for(int i = 1; i <= 12; i++) {
            cin >> input;
            card *newcard = new card(i, input);
            for(int j = 0; j < sets_cnt; j++) {
                if(fit(newcard, &sets[j])) {
                    cardset newset = sets[j];
                    newset.insert(newcard);
                    sets[sets_cnt++] = (newset);
                }
            }
            cardset newset   = cardset(newcard);
            sets[sets_cnt++] = (newset);
        }
        if(ans.size() == 0) {
            cout << "no sets";
            return 0;
        }
        std::sort(ans.begin(), ans.end(), [](const std::vector<int> &a, const std::vector<int> &b) {
            if(a[0] != b[0]) {
                return a[0] < b[0];
            } else if(a[1] != b[1]) {
                return a[1] < b[1];
            } else {
                return a[2] < b[2];
            }
        });
        for(const auto &s: ans) {
            cout << s[0] << ' ' << s[1] << ' ' << s[2] << std::endl;
        }
        return 0;
    }
}

题解

这个问题要求我们从给定的12张卡牌中找出所有有效的“Set”。一个“Set”由三张卡牌组成，对于它们的四个特征中的任何一个，特征值要么是三张牌都完全相同，要么是三张牌两两互不相同。

这里的C++代码实现了一种构造性或增量式算法来寻找这些“Set”。它不是通过检查所有可能的三张牌组合（暴力方法），而是通过一次添加一张牌来逐步构建潜在的“Set”。

其核心逻辑巧妙地利用了位掩码（bitmasking）来表示两张卡牌之间的关系。函数 calc_mask(card *c1, card *c2) 生成一个4位的整数。每一位对应四个特征中的一个。如果两张牌在该特征上相同，则该位设置为 1；如果不同，则为 0 。这个“相似性掩码”紧凑地描述了两张牌的相互关系。

使用这个掩码，三张牌（A, B, C）构成一个“Set”的规则可以被重新表述为：A和B之间的相似性掩码必须与A和C之间的相似性掩码相同，并且也必须与B和C之间的相似性掩码相同。这确保了每个特征都满足“全部相同或全部不同”的属性。

主算法的流程如下：

它从第1张到第12张，逐一处理卡牌。它维护一个数组 sets，用于存储 cardset 对象。一个 cardset 是一个潜在的“Set”，可以包含一张或两张卡牌。

对于每个新读入的卡牌 newcard：

1. 它会遍历所有已经创建的 cardset 对象 (sets[j])。一个 cardset 的大小可以是1（单张牌）或2（一对牌）。
2. 函数 fit(newcard, &sets[j]) 检查 newcard 是否可以有效地添加到现有的 cardset 中。
3. 如果 sets[j] 只包含一张牌，任何 newcard 都可以“fit”以形成一个对。一个大小为2的新 cardset 会由此创建。它的 mask 成员此时被计算并存储，代表这两张牌之间的相似性。
4. 如果 sets[j] 包含两张牌，fit 函数会检查 newcard 与 sets[j] 中两张牌的相似性掩码是否都与 sets[j] 中已存储的 mask 相匹配。如果匹配，那么一个有效的三张牌“Set”就找到了。一个大小为3的新 cardset 被创建，其卡牌ID被添加到全局的 ans 向量中。
5. 在尝试扩展所有现有的 cardset 之后，一个只包含 newcard 的新 cardset 会被创建并添加到列表中。这使得 newcard 能够与后续处理的卡牌开始新的潜在“Set”。

在所有12张卡牌都处理完毕后，ans 向量就包含了所有找到的“Set”。然后代码检查是否找到了任何“Set”。如果没有，则打印 “no sets” 。否则，它按照题目要求的字典序对“Set”列表进行排序，并每行打印一个“Set”。

复杂度分析

设 N 为卡牌数量（N=12）。

时间复杂度

外层循环运行 N 次。内层循环遍历 sets_cnt，即已存在的 cardset 的数量。处理完 i 张牌后，大小为1的 cardset 数量为 i ，大小为2的数量为 i*(i-1)/2。因此 sets_cnt 是二次增长的，即 O(i^2)。总工作量大约是从 i=1 到 N-1 对 i^2 求和，这导致时间复杂度为 O(N^3)。对于 N=12，这是非常高效的。

空间复杂度

sets 数组存储了所有的 cardset 对象。这些对象的数量是 O(N^2)。每个 cardset 存储指针，所以空间主要由数组本身主导，导致 O(N^2) 的空间复杂度。

Planting Trees

问题描述

农夫乔恩最近买了n棵树苗，他想把它们种在院子里。乔恩种植一棵树苗需要1天时间，并且对于每棵树，乔恩都确切地知道它在种植后需要多少天才能完全成熟。乔恩还想为他的农夫朋友们举办一个派对，但为了给他们留下深刻印象，他希望只在所有树都长成之后才组织派对。更准确地说，派对最早可以在最后一棵树长成后的第二天举办。

请帮助乔恩找出可以举办派对的最早日期。乔恩可以随心所欲地选择种植树木的顺序，因此他希望以一种能让派对尽早举行的方式来种植树木。

输入

输入包含两行。第一行包含一个整数 N (1 ≤ N ≤ 100,000)，表示树苗的数量。接下来的一行是 N 个整数 t_i (1 ≤ t_i ≤ 1,000,000)，其中 t_i 表示第 i 棵树生长所需的天数。

输出

你的程序应该输出一行，包含一个整数，表示可以组织派对的最早日期。天数从当前时刻开始编号为 1, 2, 3, …。

代码

#include <iostream>
#include <vector>
#include <algorithm>

namespace plantingtrees {
    int main(std::istream &cin, std::ostream &cout) {
        int n;
        cin >> n;
        std::vector<int> vec(n);
        for(int i = 0; i < n; i++) {
            cin >> vec[i];
        }

        // 将树的生长时间按降序排序。
        // rbegin() 和 rend() 迭代器用于反向排序。
        std::sort(vec.rbegin(), vec.rend());

        int ans = 0;
        // 按照选定的种植顺序遍历树木。
        // 位于索引 'i' 的树在第 'i + 1' 天被种植。
        for(int i = 0; i < n; i++) {
            // 种植日: i + 1
            // 生长时间: vec[i]
            // 成熟日: (i + 1) + vec[i]
            // 派对必须在所有树成熟后举行，所以我们寻找最晚的成熟日。
            // 派对在最后一棵树成熟后的第二天举行。
            // 值 `i + vec[i] + 2` 对应 `(i + 1) + vec[i] + 1`，
            // 如果这棵树是最后一棵成熟的，这就是最早可能的派对日期。
            ans = std::max(ans, i + vec[i] + 2);
        }
        cout << ans;

        return 0;
    }
}

题解

这个问题要求我们找出举办派对的最早可能日期。派对必须在所有种植的树木都成熟后的第二天举行。我们有N棵树苗，并且知道每棵树苗在种植后需要 t_i 天才能成熟。种植一棵树苗需要一天。我们可以决定种植的顺序。目标是找到一个种植顺序，使得最终的派对日期最小化。

让我们分析一下时间线。如果我们确定了种植顺序，第一棵树在第1天种植，第二棵在第2天，以此类推，序列中的第 i 棵树在第 i 天种植。如果这第 i 棵树的成熟时间是 t_i，它将在第 i + t_i 天完全成熟。派对只能在所有 树木都成熟后举行。这意味着我们需要在所有树中找到最晚的成熟日期。派对可以在这个最晚成熟日期的第二天举行。 因此，对于一个给定的种植序列 p_1, p_2, ..., p_N 及其对应的生长时间 t_{p_1}, t_{p_2}, ..., t_{p_N}，派对日期将是 1 + max(1 + t_{p_1}, 2 + t_{p_2}, ..., N + t_{p_N})。我们的任务是找到树木的一个排序（一个排列 p），以最小化这个值。

这个问题可以用贪心算法解决。直觉告诉我们，需要较长时间生长的树应该尽早种植。这给了它们漫长成熟期的“领先优势”。相反，生长快的树可以稍后种植，而不会显著推迟最终的完成日期。

让我们来证明这个贪心策略是最优的。该策略是：将树木按其生长时间 t_i 的降序排序，并按此顺序种植。 考虑任何一个最优的种植计划。如果这个计划不是按生长时间降序排列的，那么在种植序列中，必然至少存在一对相邻的树，比如在第 i 天和第 i+1 天种植的树，其中第 i 天种植的树（称之为树A，生长时间为 t_A）的生长时间比第 i+1 天种植的树（树B，生长时间为 t_B）要短。即 t_A < t_B。

在这个计划中，这两棵树的成熟日期是：

树A的成熟日期：i + t_A

树B的成熟日期：(i + 1) + t_B

序列中所有其他的树不受我们对A和B操作的影响。该计划的最晚成熟日期是 max(..., i + t_A, (i + 1) + t_B, ...)。

现在，让我们交换A和B的种植顺序。我们在第 i 天种植B，第 i+1 天种植A。新的成熟日期是：

树B的新成熟日期：i + t_B

树A的新成熟日期：(i + 1) + t_A

让我们比较交换前后这对树的最晚成熟日期。 交换前，最晚的是 max(i + t_A, i + 1 + t_B)。因为 t_A < t_B，所以 t_A <= t_B - 1。 因此，i + t_A < i + t_B - 1 < i + 1 + t_B。最大值是 i + 1 + t_B。 交换后，最晚的是 max(i + t_B, i + 1 + t_A)。 因为 t_A < t_B，所以 i + 1 + t_A < i + 1 + t_B。并且如果 t_B - t_A > 1，i + t_B 也大于 i + 1 + t_A。无论如何，最大值是 i + t_B。

比较最大值：(i + t_B) (交换后) vs. (i + 1 + t_B) (交换前)。 很明显，i + t_B < i + 1 + t_B。交换减少了这对树的最晚成熟日期。由于所有其他树的成熟日期保持不变，整个计划的总体最晚成熟日期只能减少或保持不变，不可能增加。 这个“交换论证”表明，我们总是可以通过将生长时间较长的树提前来改进或维持一个未排序的计划。通过反复应用这个逻辑，我们可以将任何最优计划转换为一个按生长时间降序排列的计划，而不会使结果变差。因此，优先种植生长时间长的树的贪心策略确实是最优的。

实现很简单：

1. 读取N和所有的生长时间 t_i 到一个向量中。
2. 将向量按降序排序。
3. 初始化一个变量 max_party_day 为0。
4. 从 i = 0 到 N-1 遍历排序后的向量。树 t_i 在第 i+1 天种植。它的成熟日期是 (i+1) + t_i。考虑到这棵树，最早的派对日期是 (i+1) + t_i + 1。我们用 max_party_day 的当前值和这个新计算出的日期的最大值来更新它。
5. 循环结束后，max_party_day 将持有最终答案。

复杂度分析

设N为树苗的数量。

时间复杂度

主要的操作是对生长时间进行排序。标准排序算法需要 O(N log N) 的时间。读取输入需要 O(N) 的时间，最后的循环计算最大派对日期也需要 O(N) 的时间。因此，总时间复杂度为 O(N log N)。

空间复杂度

我们需要将N个生长时间存储在一个向量中，这需要 O(N) 的空间。