Topic1

 Solo上了大学，对数学很感兴趣，有一天他面对数分三，一个Sequence(数列)摆在了他面前，这可难住他了……
 序列如下：S(a,k,n)=a+(k+a)+(2k+a)+…+(nk+a)，题目要他对序列求和，但是a、k、n的取值好多，他不知如何是好，于是他决定写个程序……
 Can you get it?

 题目数据范围：

 0<=a<=100.
 0<=k<=100.
 0<=n<=100.
 输入
 输入只有一行，包含三个整数a、k和n。

 输出
 根据输入的a、k和n，输出S(a,k,n)的值。

 样例
 输入样例 1 复制

 1 2 4
 输出样例 1
 25

#include <iostream>

int a, k, n;

int main() {

    std::cin >> a >> k >> n;
    std::cout << (n * (n + 1)) / 2 * k + (n + 1) * a;
    return 0;
}

Topic2

实现一个 Trie（前缀树），包含 insert, search, 和 startsWith 这三个方法。输入为全英文小写单词

#include <iostream>
#include <vector>

class Trie {
public:
    Trie() : Len(1e5), idx(0), c(Len), son(Len, std::vector<int>(26)), cnt(Len) {
    }

    void insert(std::string word) {
        int p = 0;
        for (int i = 0; i < word.size(); ++i) {
            int u = word[i] - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }

    bool search(std::string word) {
        int p = 0;
        for (int i = 0; i < word.size(); ++i) {
            int u = word[i] - 'a';
            if (!son[p][u]) return false;
            p = son[p][u];
        }
        return true;
    }

    bool startsWith(std::string prefix) {
        return search(prefix);
    }

private:
    const int Len;
    int idx;
    std::vector<char> c;
    std::vector<std::vector<int> > son;
    std::vector<int> cnt;
};

int main() {
    Trie t;
    t.insert("abc");
    t.insert("abd");
    t.insert("abc");
    t.insert("abd");
    t.insert("abc");
    t.insert("abd");

    std::cout << t.search("abc") << std::endl;
    std::cout << t.search("abd") << std::endl;
    std::cout << t.search("abcdf") << std::endl;
    std::cout << t.startsWith("ab") << std::endl;
    std::cout << t.startsWith("abz") << std::endl;
    std::cout << t.startsWith("abz") << std::endl;
}

Topic3

给定一个二叉排序树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
 样例
 样例 1:

 输入：root = {5,3,6,2,4,#,8,1,#,#,#,7,9}

 5
 / \
 3    6
 / \    \
 2   4    8
 /        / \
 1        7   9

 输出：{1,#,2,#,3,#,4,#,5,#,6,#,7,#,8,#,9}
 解释：
 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9
 样例 2:

 输入: root = {8,3,10,1,6,#,14,#,#,4,7,13,#}
 8
 /  \
 3     10
 / \      \
 1   6      14
 / \   /
 4   7  13
 输出: {1,#,3,#,4,#,6,#,7,#,8,#,10,#,13,#,14}
 解释：
 1
 \
 3
 \
 4
 \
 6
 \
 7
 \
 8
 \
 10
 \
 13
 \
 14

#include <iostream>
#include <queue>
#include <vector>


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
};

class CreateTree {
public:
    TreeNode *createTreeFromVector(const std::vector<int> &rootList) {
        if (rootList.empty() || rootList[0] == '#') {
            return nullptr;
        }

        TreeNode *root = new TreeNode(rootList[0]);
        std::queue<TreeNode *> q;
        q.push(root);

        int i = 1;
        while (i < rootList.size()) {
            TreeNode *current = q.front();
            q.pop();

            if (i < rootList.size() && rootList[i] != '#') {
                current->left = new TreeNode(rootList[i]);
                q.push(current->left);
            }
            i++;

            if (i < rootList.size() && rootList[i] != '#') {
                current->right = new TreeNode(rootList[i]);
                q.push(current->right);
            }
            i++;
        }

        return root;
    }

    void levelOrder(TreeNode *root) {
        if(!root) return;
        levelOrder(root->left);
        v.push_back(root->val);
        levelOrder(root->right);
    }
    TreeNode *specialTree(std::vector<int> rootList) {
        TreeNode *root = createTreeFromVector(rootList);
        levelOrder(root);
        TreeNode *NewTree = new TreeNode(v[0]);
        TreeNode *head = NewTree;
        for (int i = 1; i < v.size(); i++) {
            NewTree->right = new TreeNode(v[i]);
            NewTree = NewTree->right;
        }
        return head;
    }
    std::vector<int> v;

};

int main() {
    // std::vector<int> rootList = {5, 3, 6, 2, 4, '#', 8, 1, '#', '#', '#', 7, 9};
    std::vector<int> rootList = {8, 3, 10, 1, 6, '#', 14, '#', '#', 4, 7, 13, '#'};

    CreateTree p;
    auto node =  p.specialTree(rootList);

    for (int i = 0; i < p.v.size(); i++) {
        std::cout << p.v[i] << " ";
    }
    return 0;
}

Topic4

题目描述
奥运会即将到来，大家都非常关注奖牌榜的情况，现在我们假设奖牌榜的排名规则如下：

 1、首先gold medal数量多的排在前面；
 2、其次silver medal数量多的排在前面；
 3、然后bronze medal数量多的排在前面；
 4、若以上三个条件仍无法区分名次，则以国家名称的字典序排定。
 我们假设国家名称不超过20个字符、各种奖牌数不超过100，且大于等于0。

 解答要求
 时间限制：1000ms, 内存限制：100MB
 输入
 第一行输入一个整数N(0<N<21)，代表国家数量;
 然后接下来的N行，每行包含一个字符串Namei表示每个国家的名称，和三个整数Gi、Si、Bi表示每个获得的gold medal、silver medal、bronze medal的数量，以空格隔开，如(China 51 20 21)，具体见样例输入。

 输出
 输出奖牌榜的依次顺序，只输出国家名称，各占一行，具体见样例输出。

 样例
 输入样例 1 复制

 5
 China 32 28 34
 England 12 34 22
 France 23 33 2
 Japan 12 34 25
 Russia 23 43 0
 输出样例 1

 China
 Russia
 France
 Japan
 England
 提示样例 1

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
#include <string>

bool cmp(const std::tuple<int, int, int, std::string> &a, const std::tuple<int, int, int, std::string> &b)
{
    if (std::get<0>(a) > std::get<0>(b)) { return true; }
    else if (std::get<0>(a) < std::get<0>(b)) { return false;}
    else
    {
        if (std::get<1>(a) > std::get<1>(b)) { return true; }
        else if (std::get<1>(a) < std::get<1>(b)) { return false; }
        else
        {
            if (std::get<2>(a) > std::get<2>(b)) { return true; }
            else if (std::get<2>(a) < std::get<2>(b)) { return false; }
            else { return std::get<3>(a) < std::get<3>(b); }
        }
    }
}
int main()
{
    int n;
    std::cin >> n;
    std::vector<std::tuple<int, int, int, std::string>> v(n);
    for (int i = 0; i < n; i++ )
    {
        int gold, silver, bronze;
        std::string country;

        std::cin >> country >> gold >> silver >> bronze;

        v[i] = std::make_tuple(gold, silver, bronze, country);

    }
    sort(v.begin(), v.end(), cmp);
    for (const auto& t : v)
    {
        std::cout << std::get<3>(t) << std::endl;
    }
    return 0;
}

Topic5

 描述
 我们定义，两个论文的相似度为最长的相似单词子序列长度 * 2 除以两篇论文的总长度。
 给定两篇论文words1，words2（每个表示为字符串数组），和相似单词对列表pairs，求两篇论文的相似度。

 注意：相似关系是可传递的。例如，如果“great”和“good”类似，而“fine”和“good”类似，那么“great”和“fine”类似。
 相似性也是对称的。 例如，“great”和“good”相似，则“good”和“great”相似。
 另外，一个词总是与其本身相似。
 样例
 样例 1:

 输入：words1= ["great","acting","skills","life"]，words2= ["fine","drama","talent","health"]，pairs=  [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]]
 输出：：0.75
 解释：
 两篇单词相似的子单词序列为
 "great","acting","skills"
 "fine","drama","talent"
 总长度为8
 相似度为6/8=0.75`
 样例 2:

 输入：words1= ["I","love","you"]，words2= ["you","love","me"]，pairs=  [["I", "me"]]
 输出：0.33
 解释：
 两篇单词相似的子单词序列为
 "I"
 "me"
 或
 "love"
 "love"
 或
 "you"
 "you"
 总长度为6
 相似度为2/6=0.33

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

const int MOD = 1999, N = 2e3;

// 字符哈希
// test1
// std::vector<std::string> words1{"great", "acting", "skills", "life"};
// std::vector<std::string> words2{"fine", "drama", "talent", "health"};
// std::vector<std::pair<std::string, std::string> > pairs{
//     {"great", "good"}, {"fine", "good"}, {"acting", "drama"}, {"skills", "talent"}
// };
// test2
std::vector<std::string> words1{"I", "love", "you"};
std::vector<std::string> words2{"you", "love", "me"};
std::vector<std::pair<std::string, std::string> > pairs{
        {"I", "me"}
};

std::vector<int> hash1(1), hash2(1);
std::vector<std::pair<int, int> > hash_pairs;
std::vector<int> fa(N);

// 并查集
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

// 动态规划数组
int f[N][N];

int main() {
    std::hash<std::string> hash;
    for (auto word: words1) {
        hash1.push_back(hash(word) % MOD);
    }

    // 字符串哈希并生成散列值
    for (auto word: words2) {
        hash2.push_back(hash(word) % MOD);
    }
    for (auto pair: pairs) {
        hash_pairs.push_back({hash(pair.first) % MOD, hash(pair.second) % MOD});
    }
    for (int i = 0; i < N; i++) fa[i] = i;

    // 合并相似单词
    for (auto [a, b]: hash_pairs) {
        int x = find(a), y = find(b);
        fa[x] = y;
    }

    // hash1, hash2  查找并查集
    for (auto &hashVal: hash1) {
        hashVal = fa[hashVal];
    }
    for (auto &hashVal: hash2) {
        hashVal = fa[hashVal];
    }

    // 最长公共子序列
    int n = hash1.size(), m = hash2.size();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
            if (hash1[i] == hash2[j]) f[i][j] = f[i - 1][j - 1] + 1;
        }
    }
    std::cout << ((f[n][m] * 2.0) / (n + m - 2)) << '\n';
}