感觉很麻烦的一道题！

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

using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

int n;

TreeNode* construct1(vector<int>& preorder, vector<int>& inorder, int i, int j, int n)  {
  if (n <= 0) return (TreeNode*) nullptr;
  if (n == 1) return new TreeNode(preorder[i]);

  int k = j;
  while (k < j + n && inorder[k] != preorder[i]) ++k;
  if (k == j + n) return (TreeNode*) nullptr;
  const int l = k - j; // l == 左子树的长度 ...

  auto root = new TreeNode(inorder[k]);
  root->left  = construct1(preorder, inorder, i + 1, j, l);
  root->right = construct1(preorder, inorder, i + 1 + l, k + 1, n - l - 1);

  return root;
}

TreeNode* construct2(vector<int>& preorder, vector<int>& inorder, int i, int j, int n)  {
  if (n <= 0) return (TreeNode*) nullptr;
  if (n == 1) return new TreeNode(preorder[i]);

  int k = j + n - 1;
  while (k >= j && inorder[k] != preorder[i]) --k;
  if (k < j) return (TreeNode*) nullptr;
  const int l = k - j; // l == 左子树的长度 ...

  auto root = new TreeNode(inorder[k]);
  root->left  = construct2(preorder, inorder, i + 1, j, l);
  root->right = construct2(preorder, inorder, i + 1 + l, k + 1, n - l - 1);

  return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
  return construct1(preorder, inorder, 0, 0, preorder.size());
}

TreeNode* buildTree2(vector<int>& preorder, vector<int>& inorder) {
  return construct2(preorder, inorder, 0, 0, preorder.size());
}

void inOrder(TreeNode* root, vector<int>& vals) {
  if (!root) return;
  inOrder(root->left, vals);
  vals.emplace_back(root->val);
  inOrder(root->right, vals);
}

void postOrder(TreeNode* root, vector<int>& ans) {
  if (!root) return;
  postOrder(root->left, ans);
  postOrder(root->right, ans);
  ans.emplace_back(root->val);
}

void printAns(vector<int>& ans) {
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d", ans[i]);
    if (i < ans.size() - 1) printf(" ");
  }
  printf("\n");
}

int main(void) {
  cin >> n;
  vector<int> preorder(n);
  for (int i = 0; i < n; ++i) cin >> preorder[i];

  vector<int> inorder(preorder);
  sort(begin(inorder), end(inorder));

  auto root = buildTree(preorder, inorder);
  vector<int> v;
  inOrder(root, v);
  if (v == inorder) {
    puts("YES");
    vector<int> ans;
    postOrder(root, ans);
    printAns(ans);
  } else {
    sort(rbegin(inorder), rend(inorder));
    root = buildTree2(preorder, inorder);
    v.clear();
    inOrder(root, v);
    if (v == inorder) {
      puts("YES");
      vector<int> ans;
      postOrder(root, ans);
      printAns(ans);
    } else {
      puts("NO");
    }
  }
}

根据题目意思模拟

#include <iostream>
#include <unordered_map>
#include <unordered_set>

using namespace std;
int n, k, id;

unordered_map<int, int> ranking;
unordered_set<int> seen;

// 判断一个数是否是质数又称素数？ (只能被1和本身的整除的数)
bool isPrime(int x) {
  for (int i = 2; i * i <= x; ++i)
    if (!(x % i)) return false;

  return true;
}

int main(void) {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {
    scanf("%d", &id);
    ranking[id] = i;
  }

  scanf("%d", &k);
  while (k--) {
    scanf("%d", &id);
    if (!ranking.count(id)) { // 耍我呢？
      printf("%04d: Are you kidding?\n", id);
      continue;
    }
    if (seen.count(id)) { // 不能多吃多占！
      printf("%04d: Checked\n", id);
      continue;
    }

    const int x = ranking[id];
    if (x == 1) printf("%04d: Mystery Award\n", id); // NO 1 
    else if (isPrime(x)) printf("%04d: Minion\n", id);
    else printf("%04d: Chocolate\n", id);

    seen.emplace(id);
  }
}

Modern C++ 分享

现代化的 “C++”
在“C++”里面用管道？“CPP 20” Ranges简介

CODE

#include <iostream>

using namespace std;

// sol1
// Time Complexity: O(100)
int main(void) {
  for (int i = 1; i <= 100; ++i)
    if (!(i & 1)) printf("%d\n", i);
  return 0;
}

// sol2
// Time Complexity: O(50)
int main(void) {
  for (int i = 2; i <= 100; i += 2)
    printf("%d\n", i);
  return 0;
}

还是二叉树的各种基本功

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

using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

int n, l, r;

TreeNode* buildTree(vector<pair<int, int>>& node_infos, int index) {
  // recursion exit condition
  if (index == -1) return nullptr;

  auto root = new TreeNode(index);
  root->left  = buildTree(node_infos, node_infos[index].first);
  root->right = buildTree(node_infos, node_infos[index].second);
  return root;
}

void fill(TreeNode* root, vector<int>& vals, int& idx) {
  if (!root) return;
  fill(root->left, vals, idx);
  root->val = vals[idx++];
  fill(root->right, vals, idx);
}

void levelOrder(TreeNode* root) {
  queue<TreeNode*> q{{root}};
  while (not q.empty()) {
    auto cur = q.front(); q.pop();
    printf("%d ", cur->val);
    if (cur->left)  q.emplace(cur->left);
    if (cur->right) q.emplace(cur->right);
  }
}

int main(void) {
  scanf("%d", &n);
  vector<pair<int, int>> node_infos(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &l, &r);
    node_infos[i] = {l, r};
  }

  vector<int> vals(n);
  for (int i = 0; i < n; ++i) cin >> vals[i];
  sort(begin(vals), end(vals));

  auto root = buildTree(node_infos, 0);

  int idx = 0;
  fill(root, vals, idx);

  levelOrder(root);
}

CODE

#include <iostream>

using namespace std;
int a, b;

int main(void) {
  scanf("%d %d", &a, &b);
  printf("PROD = %d", a * b);
}

DFS + BFS Two Solutions

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

using namespace std;
int n, k, child;
double p, r;

unordered_map<int, int> amounts;

// depth first search
void dfs(vector<vector<int>>& g, int cur, double price, double& ans) {
  if (g[cur].empty()) { // leaf node
    ans += price * amounts[cur];
    return;
  }

  for (const auto& child : g[cur])
    // double new_price = price + price * r / 100; // 计算溢价
    dfs(g, child, price + price * r / 100, ans);
}

// breadth first search (level order)
double bfs(vector<vector<int>>& g) {

  queue<int> q{{0}};

  double ans = 0.0, price = p;
  while (not q.empty()) {
    size_t sz = q.size();
    while (sz--) {
      const int cur = q.front(); q.pop();
      if (g[cur].empty()) {
        ans += price * amounts[cur];
        continue;
      }
      for (int child : g[cur]) q.emplace(child);
    }
    price += price * r / 100; // 计算新的价格
  }

  return ans;
}

void print(vector<vector<int>>& g) {
  for (int i = 0; i < g.size(); ++i) {
    printf("%d: [", i);
    for (const auto& child : g[i]) printf("%d ", child);
    printf("]\n");
  }
}

int main(void) {
  cin >> n >> p >> r;

  vector<vector<int>> g(n); // adjacence list
  for (int i = 0; i < n; ++i) {
    scanf("%d", &k);
    if (!k) {
      int amount;
      scanf("%d", &amount);
      amounts[i] = amount;
      continue; 
    }
    while (k--) {
      scanf("%d", &child);
      g[i].emplace_back(child);
    }
  }

  // print(g);
  // double ans = 0.0;
  // dfs(g, 0, p, ans);
  // printf("%.1f", ans);

  printf("%.1f", bfs(g));
}

Greedy Algorithm!

#include <iostream>

using namespace std;
int n;

static constexpr int coins[] = {1, 4, 16, 64};

int main(void) {
  scanf("%d", &n);
  int change = 1024 - n, ans = 0;
  for (int i = 3; i >= 0; --i) {
    while (change >= coins[i]) {
      change -= coins[i];
      ++ans;
    }
  }
  printf("%d\n", ans);
}

BST 建树和求LCA！

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>

using namespace std;
int m, n, u, v;

struct TreeNode {
  int val;
  TreeNode *left, *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {};
  TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
  TreeNode(int _val, TreeNode* _left, TreeNode* _right) : val(_val), left(_left), right(_right) {};
  ~TreeNode() {};
};

TreeNode* bstFromPreorder(vector<int>& preorder) {
  stack<TreeNode*> s;
  TreeNode *root = nullptr, *pnode = nullptr;

  for (const auto& val : preorder) {
    auto node = new TreeNode(val);
    if (s.empty()) {
      root = node;
    } else if (node->val < s.top()->val)
      s.top()->left = node;
    else {
      while (not s.empty() && node->val > s.top()->val) {
        pnode = s.top();
        s.pop();
      }
      pnode->right = node;
    }
    s.emplace(node);
  }

  return root;
}

TreeNode* lowestCommonAncestor(TreeNode* root, const int p, const int q) {
  if (!root) return nullptr;
  if (p < root->val && q < root->val)
    return lowestCommonAncestor(root->left, p, q);
  if (p > root->val && q > root->val)
    return lowestCommonAncestor(root->right, p, q);
  return root;
}

int main(void) {
  scanf("%d %d", &m, &n);

  vector<int> preorder(n);
  for (int i = 0; i < n; ++i) cin >> preorder[i];

  unordered_set<int> s(begin(preorder), end(preorder));
  auto root = bstFromPreorder(preorder);

  while (m--) {
    scanf("%d %d", &u, &v);
    if (!s.count(u) or !s.count(v)) {
      if (!s.count(u) and !s.count(v)) printf("ERROR: %d and %d are not found.\n", u, v);
      else if (!s.count(u))            printf("ERROR: %d is not found.\n", u);
      else                             printf("ERROR: %d is not found.\n", v);                
      continue;
    }
    if (u == v) { 
      printf("%d is an ancestor of %d.\n", u, v); 
      continue; 
    }

    int lca = lowestCommonAncestor(root, u, v)->val;
    if (lca != u && lca != v) printf("LCA of %d and %d is %d.\n", u, v, lca);
    else if (lca == u)        printf("%d is an ancestor of %d.\n", u, v);
    else                      printf("%d is an ancestor of %d.\n", v, u);
  }
}

代码练习

#include <iostream>

using namespace std;
string s1, s2;

int main(void) {
  cin >> s1 >> s2;
  int n1 = 1, n2 = 1;
  for (const auto& c : s1) n1 *= c - 'A' + 1;
  for (const auto& c : s2) n2 *= c - 'A' + 1;
  n1 %= 47, n2 %= 47;

  puts(n1 == n2 ? "GO" : "STAY");
}