2、C++程序设计与数据结构

#include <iostream>
#include <string>
using namespace std;

class Person {
public:
    string name;   // 姓名
    int age;       // 年龄

    void sayHello() {   // 打招呼
        cout << "Hello, my name is " << name << ", I'm " << age << " years old." << endl;
    }
};

int main() {
    Person p1;    // 创建一个Person对象
    p1.name = "Tom";
    p1.age = 18;
    p1.sayHello();   // 调用对象的成员函数

    return 0;
}

#include <iostream>
using namespace std;

class Complex {
private:
    double real;   // 实部
    double imag;   // 虚部

public:
    Complex(double r, double i) : real(r), imag(i) {}   // 构造函数

    Complex operator+(const Complex& other) const {    // 重载"+"运算符
        return Complex(real + other.real, imag + other.imag);
    }

    void display() const {   // 成员函数
        cout << real << "+" << imag << "i" << endl;
    }
};

int main() {
    Complex c1(1, 2), c2(3, 4);
    Complex c3 = c1 + c2;    // 调用运算符重载函数
    c3.display();            // 调用成员函数

    return 0;
}

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> mySet;

    // 插入元素
    mySet.insert(3);
    mySet.insert(2);
    mySet.insert(1);

    // 查找元素
    if (mySet.find(2) != mySet.end()) {
        cout << "Found 2!" << endl;
    }

    // 遍历元素
    for (auto it = mySet.begin(); it != mySet.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    // 删除元素
    mySet.erase(2);

    // 遍历元素
    for (auto it = mySet.begin(); it != mySet.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> myList;

    // 插入元素
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);

    // 删除元素
    myList.pop_front();

    // 遍历元素
    for (auto it = myList.begin(); it != myList.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // 插入元素
    myDeque.push_back(1);
    myDeque.push_back(2);
    myDeque.push_back(3);
    myDeque.push_front(0);

    // 删除元素
    myDeque.pop_front();

    // 遍历元素
    for (auto it = myDeque.begin(); it != myDeque.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> myQueue;

    // 插入元素
    myQueue.push(3);
    myQueue.push(5);
    myQueue.push(1);

    // 输出队首元素
    cout << "队首元素：" << myQueue.top() << endl;

    // 弹出队首元素
    myQueue.pop();

    // 遍历元素
    while (!myQueue.empty()) {
        cout << myQueue.top() << " ";
        myQueue.pop();
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <set>

using namespace std;

int main() {
    multiset<int> myMultiset;

    // 插入元素
    myMultiset.insert(1);
    myMultiset.insert(3);
    myMultiset.insert(2);
    myMultiset.insert(2);

    // 输出元素
    for (auto it = myMultiset.begin(); it != myMultiset.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 查找元素
    auto it = myMultiset.find(2);
    if (it != myMultiset.end()) {
        cout << "找到了元素：" << *it << endl;
    } else {
        cout << "未找到元素" << endl;
    }

    // 删除元素
    myMultiset.erase(2);

    // 输出元素
    for (auto it = myMultiset.begin(); it != myMultiset.end(); ++it) {
        cout << *it << " ";
    }
    return 0;
}

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> myMap;

    // 插入键值对
    myMap.insert(pair<string, int>("Tom", 24));
    myMap.insert(make_pair("Lucy", 22));
    myMap["Lily"] = 18;

    // 输出元素
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    // 查找元素
    auto it = myMap.find("Lucy");
    if (it != myMap.end()) {
        cout << "Lucy的年龄是：" << it->second << endl;
    } else {
        cout << "未找到Lucy" << endl;
    }

    // 删除元素
    myMap.erase("Tom");

    // 输出元素
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    return 0;
}

#include <iostream>
#include <map>

using namespace std;

int main() {
    multimap<string, int> myMultimap;

    // 插入键值对
    myMultimap.insert(pair<string, int>("Tom", 24));
    myMultimap.insert(make_pair("Lucy", 22));
    myMultimap.insert(make_pair("Lucy", 25));
    myMultimap.insert(make_pair("Lily", 18));

    // 输出元素
    for (auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    // 查找元素
    auto it = myMultimap.find("Lucy");
    if (it != myMultimap.end()) {
        cout << "Lucy的年龄是：" << it->second << endl;
    } else {
        cout << "未找到Lucy" << endl;
    }

    // 删除元素
    myMultimap.erase("Lucy");

    // 输出元素
    for (auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    return 0;
}

#include <iostream>
#include <utility>

using namespace std;

int main() {
    pair<string, int> myPair;

    myPair.first = "Tom";
    myPair.second = 24;

    cout << myPair.first << ": " << myPair.second << endl;

    return 0;
}

#include <iostream>
#include <tuple>

using namespace std;

int main() {
    tuple<string, int, double> myTuple("Tom", 24, 1.75);

    cout << get<0>(myTuple) << endl;   // 输出第一个元素
    cout << get<1>(myTuple) << endl;   // 输出第二个元素
    cout << get<2>(myTuple) << endl;   // 输出第三个元素

    return 0;
}

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // push elements to back of deque
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // push elements to front of deque
    myDeque.push_front(5);
    myDeque.push_front(15);

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    // pop element from back of deque
    myDeque.pop_back();

    // pop element from front of deque
    myDeque.pop_front();

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // push elements to back of deque
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // push elements to front of deque
    myDeque.push_front(5);
    myDeque.push_front(15);

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    // pop element from back of deque
    myDeque.pop_back();

    // pop element from front of deque
    myDeque.pop_front();

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> mySet;

    // insert elements to set
    mySet.insert(30);
    mySet.insert(20);
    mySet.insert(10);

    // output set contents
    cout << "set contents: ";
    for (auto i : mySet) {
        cout << i << " ";
    }
    cout << endl;

    // find element in set
    auto it = mySet.find(20);
    if (it != mySet.end()) {
        cout << "element found in set: " << *it << endl;
    } else {
        cout << "element not found in set" << endl;
    }

    // erase element from set
    mySet.erase(20);

    // output set contents
    cout << "set contents: ";
    for (auto i : mySet) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  priority_queue<int, vector<int>, less<int>> pq;
  pq.push(5);
  pq.push(2);
  pq.push(7);
  pq.push(1);
  pq.push(8);

  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 100000;
const int MAXLOG = 20;

int n, q;
int a[MAXN + 1];
int st[MAXN + 1][MAXLOG + 1];

void build_st() {
  int k = log2(n);
  for (int i = 1; i <= n; i++) {
    st[i][0] = a[i];
  }
  for (int j = 1; j <= k; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
}

int query(int l, int r) {
  int k = log2(r - l + 1);
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  build_st();

  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    cout << query(l, r) << endl;
  }

  return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;

int fa[MAXN];

// 初始化并查集，每个元素的父节点初始化为它本身
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

// 查找元素x所在的集合的代表元素
int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);  // 路径压缩
}

// 合并元素x和y所在的集合
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    init(n);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        unite(a, b);
    }

    vector<int> e[MAXN];  // 存储每个等价类的元素
    for (int i = 1; i <= n; i++) {
        int f = find(i);  // 找到i所在的集合的代表元素
        e[f].push_back(i);  // 将i加入代表元素所在的等价类中
    }

    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) {  // 如果i是代表元素，则输出i所在的等价类
            cout << "等价类" << i << "中的元素为：";
            for (int j = 0; j < e[i].size(); j++) {
                cout << e[i][j] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
int p[N];  // p[x] 表示元素 x 的父节点，如果 p[x] = x，则 x 为该集合的代表元素

// 初始化
void init() {
    for (int i = 1; i <= n; i++) p[i] = i;
}

// 查找元素 x 所在集合的代表元素
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 合并两个集合
void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa != pb) p[pa] = pb;
}

int main() {
    cin >> n >> m;
    init();
    while (m--) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    // 输出各个元素所在集合的代表元素
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) ans.push_back(i);
    }
    cout << ans.size() << endl;
    return 0;
}

      A
     / \
    B   C
   / \   \
  D   E   F
         / \
        G   H

           A
          /
         B
        / \
       D   E
            \
             C
              \
               F
              / \
             G   H

#include <iostream>
using namespace std;

// 孩子兄弟表示法
struct CSNode {
    int data;            // 数据域
    CSNode* firstChild;  // 指向第一个孩子
    CSNode* nextSibling; // 指向下一个兄弟
};

// 创建树
CSNode* createTree() {
    CSNode* root = new CSNode;
    root->data = 1;

    CSNode* node2 = new CSNode;
    node2->data = 2;

    CSNode* node3 = new CSNode;
    node3->data = 3;

    CSNode* node4 = new CSNode;
    node4->data = 4;

    CSNode* node5 = new CSNode;
    node5->data = 5;

    CSNode* node6 = new CSNode;
    node6->data = 6;

    root->firstChild = node2;
    node2->nextSibling = node3;
    node3->nextSibling = NULL;
    node2->firstChild = node4;
    node4->nextSibling = node5;
    node5->nextSibling = NULL;
    node4->firstChild = node6;
    node6->nextSibling = NULL;
    node6->firstChild = NULL;

    return root;
}

// 先序遍历
void preOrder(CSNode* root) {
    if (root) {
        cout << root->data << " ";
        preOrder(root->firstChild);
        preOrder(root->nextSibling);
    }
}

int main() {
    CSNode* root = createTree();
    preOrder(root);
    return 0;
}

struct CSNode {
    char data;
    CSNode *firstChild; // 指向第一个孩子节点
    CSNode *nextSibling; // 指向下一个兄弟节点
};

// 将一棵树转换为二叉树
CSNode* treeToBinaryTree(TreeNode *root) {
    if (root == NULL) {
        return NULL;
    }
    CSNode *csroot = new CSNode();
    csroot->data = root->val;
    csroot->firstChild = treeToBinaryTree(root->left);
    csroot->nextSibling = treeToBinaryTree(root->right);
    return csroot;
}

#include <iostream>
using namespace std;
const int MAXN = 100005;

int n, m;
int a[MAXN];
struct SegTree {
    int l, r;
    int sum, lazy;
} tree[MAXN << 2]; // 线段树节点数量最多是原数组长度的 4 倍

void pushUp(int p) {
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

void pushDown(int p) {
    if (tree[p].lazy != 0) {
        tree[p << 1].lazy += tree[p].lazy;
        tree[p << 1 | 1].lazy += tree[p].lazy;
        tree[p << 1].sum += tree[p].lazy * (tree[p << 1].r - tree[p << 1].l + 1);
        tree[p << 1 | 1].sum += tree[p].lazy * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1);
        tree[p].lazy = 0;
    }
}

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    if (l == r) {
        tree[p].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushUp(p);
}

void update(int p, int l, int r, int k) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum += k * (tree[p].r - tree[p].l + 1);
        tree[p].lazy += k;
        return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) update(p << 1, l, r, k);
    if (r > mid) update(p << 1 | 1, l, r, k);
    pushUp(p);
}

int query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].sum;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    int res = 0;
    if (l <= mid) res += query(p << 1, l, r);
    if (r > mid) res += query(p << 1 | 1, l, r);
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op, l, r, k;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%d", &l, &r, &k);
            update(1, l, r, k);
        } else {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
    }
    return 0;
    }

// 线段树节点结构体
struct Node {
    int start;   // 区间左端点
    int end;     // 区间右端点
    int sum;     // 区间元素和
    Node* left;  // 左子节点指针
    Node* right; // 右子节点指针

    // 构造函数
    Node(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};

// 线段树类
class SegmentTree {
public:
    // 构造函数
    SegmentTree(const vector<int>& nums) {
        root = buildTree(nums, 0, nums.size() - 1);
    }

    // 区间查询
    int query(int start, int end) {
        return queryHelper(root, start, end);
    }

    // 区间更新
    void update(int index, int val) {
        updateHelper(root, index, val);
    }

private:
    // 根节点指针
    Node* root;

    // 建立线段树
    Node* buildTree(const vector<int>& nums, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        Node* node = new Node(start, end);
        if (start == end) {
            node->sum = nums[start];
        } else {
            int mid = start + (end - start) / 2;
            node->left = buildTree(nums, start, mid);
            node->right = buildTree(nums, mid + 1, end);
            node->sum = node->left->sum + node->right->sum;
        }
        return node;
    }

    // 区间查询
    int queryHelper(Node* node, int start, int end) {
        if (!node || node->start > end || node->end < start) {
            return 0;
        }
        if (start <= node->start && node->end <= end) {
            return node->sum;
        }
        int mid = node->start + (node->end - node->start) / 2;
        if (end <= mid) {
            return queryHelper(node->left, start, end);
        } else if (start > mid) {
            return queryHelper(node->right, start, end);
        } else {
            return queryHelper(node->left, start, mid) + queryHelper(node->right, mid + 1, end);
        }
    }

    // 区间更新
    void updateHelper(Node* node, int index, int val) {
        if (!node || index < node->start || index > node->end) {
            return;
        }
        if (node->start == node->end) {
            node->sum = val;
        } else {
            int mid = node->start + (node->end - node->start) / 2;
            if (index <= mid) {
                updateHelper(node->left, index, val);
            } else {
                updateHelper(node->right, index, val);
            }
            node->sum = node->left->sum + node->right->sum;
        }
    }
};

#include <iostream>
using namespace std;

const int MAXN = 100001;
int n, q, c[MAXN], tr[MAXN];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int k) {
    while (x <= n) {
        tr[x] += k;
        x += lowbit(x);
    }
}

int sum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        add(i, c[i]);
    }
    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y - c[x]);
            c[x] = y;
        } else {
            cout << sum(y) - sum(x - 1) << endl;
        }
    }
    return 0;
}

#include <iostream>
using namespace std;

const int MAXN = 100001;
int n, trie[MAXN][26], cnt[MAXN], tot = 1;

void insert(string s) {
    int p = 1;
    for (int i = 0; i < s.length(); i++) {
        int x = s[i] - 'a';
        if (trie[p][x] == 0) {
            trie[p][x] = ++tot;
        }
        p = trie[p][x];
        cnt[p]++;
    }
}

int query(string s) {
    int p = 1;
    for (int i = 0; i < s.length(); i++) {
        int x = s[i] - 'a';
        if (trie[p][x] == 0) {
            return 0;
        }
        p = trie[p][x];
    }
    return cnt[p];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string op, s;
        cin >> op >> s;
        if (op == "insert") {
            insert(s);
        } else {
            cout << query(s) << endl;
        }
    }
    return 0;
}