二上進階程式設計實習學期總結
===
序言
---
這是在二上的時候，實習課的程式實際操作，而我將其中幾個程式統整起來，當作一個紀錄。

程式的主題
---

### 1.最接近的高人:
題意:

>對於一個人來說，只要比他高的人就是高人。有 N
個人排成一列，對於每一個人，要找出排在他前方離他最近的高人，排在之後的高人不算，假設任兩個相鄰的人的距離都是
1，本題要計算每個人和他前方最近高人的距離之總和。如果這個人前方沒有高人(前方沒人比他高)，距離以他的位置計算(等價於假設最前方有個無窮高的高人)。
日期:2022.11.22

程式碼:

#include <bits/stdc++.h>
using namespace std;
#define N 300010
#define oo 10000001
int a[N];
stack<int> S;
int main() {
  int i, n;
  long long total = 0; // total distance
  scanf("%d", &n);
  S.push(0);
  a[0] = oo;
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  cout << "每個位置，與前面高人的距離:\n";
  for (i = 1; i <= n; i++) {

    int cnt = i; //陣列的位置

    while (a[S.top()] <= a[i]) {

      S.pop();
    }
    cnt -= S.top(); //陣列的位置減去堆疊頂端即為距離
    total += i - S.top();
    S.push(i);
    cout << "(" << i << "): " << cnt << "\n";
  }
  printf("總距離 = %lld\n", total);
  return 0;
}

執行結果:

新增功能:
***除了列印出最高的高人，還有列出每個人的高人。***

---
### 2.定長度區間的最大區段差
題意:

>固定長度區間的最大區段差
對於序列的一個連續區段來說，區段差是指區段內的最大值減去區段內的最小值。有N
個非負整數組成的序列 seq，請計算在所有長度為 L 的連續區段中，最大的區段差為何。
date:2022.12.20

程式碼:

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200010
int seq[MAXN];
deque<int> max_q, min_q; // index of max and min queue
// put seq[i] from back of max_q
int max_n = 0, min_n = 0;
void put_max(int i) {
  // remove useless
  while (!max_q.empty() && seq[max_q.back()] <= seq[i])
    max_q.pop_back();
  max_q.push_back(i);
}
// put seq[i] from back of min_q
void put_min(int i) {
  // remove useless
  while (!min_q.empty() && seq[min_q.back()] >= seq[i])
    min_q.pop_back();
  min_q.push_back(i);
}
int main() {
  int n, L, i, j, max_diff = 0;
  scanf("%d%d\n", &n, &L);
  for (i = 0; i < n; i++) {
    scanf("%d", &seq[i]);
  }
  put_max(0);
  put_min(0);
  for (i = 1; i < n; i++) {
    // put the ith element into max_queue
    if (max_q.front() <= i - L) // out-of-range
      max_q.pop_front();        // its index

    put_max(i);
    max_n = max_q.front(); //取得最大值的首位index
    // put the ith element into min_queue
    if (min_q.front() <= i - L) // out of range
      min_q.pop_front();
    put_min(i);
    min_n = min_q.front(); // 取得最小值的index
    // the diff of this subarray
    int diff = seq[max_q.front()] - seq[min_q.front()];
    max_diff = max(max_diff, diff);
  }

  cout << "差值最大的區段為 [ ";
  for (int i = max_n; i < max_n + 4; i++) {
    cout << seq[i] << " "; //輸出取得的區間值
  }
  cout << "]";
  cout << "\n區段最大值 = " //最大值第一位
       << seq[max_n] << "\n";
  cout << "區段最小值 = " //最小值
       << seq[min_n] << "\n";
  printf("最大差值為 = %d\n", max_diff);
  return 0;
}

執行結果:

新增功能:
***除了找出最大的區段差，還有列出最大值最小值及最大區段。***

---
### 3.最多色彩帶
題意:

>有一條細長的彩帶，彩帶區分成 n
格，每一格的長度都是 1，每一格都有一個顏色，相鄰可能同色。給定長度限制
L，請找出此彩帶長度 L 的連續區段最多可能有多少種顏色。 data:2022.12.27

程式碼:

#include <bits/stdc++.h>
using namespace std;
#define N 200010
int seq[N], cnt[N] = {0}; // counter of color i
int t_cnt;
int main() {
  int n, L, i;
  scanf("%d%d", &n, &L);
  int n_color = 0;
  for (i = 0; i < n; i++)
    scanf("%d", &seq[i]);
  // initial window
  for (i = 0; i < L; i++) {
    int color = seq[i];
    cnt[color]++;
    if (cnt[color] == 1)
      n_color++;
  }
  int ans = n_color, left;

  // sliding window, seq[i] in, seq[left] out
  for (left = 0, i = L; i < n; i++, left++) {
    int color = seq[i];
    cnt[color]++;
    if (cnt[color] == 1) {
      n_color++;
    }
    color = seq[left];
    cnt[color]--;
    if (cnt[color] == 0) {
      n_color--;
    }
    if (n_color > ans) { //如果有新的最大值
      ans = n_color;
      t_cnt = left + 1; //就記錄下他的首位
    }
  }
  cout << "\n色彩種類最多序列: ";
  for (int i = 0; i < L; i++) {
    cout << seq[t_cnt + i] << " "; //將從首位的值依序輸出
  }
  cout << "\n";
  printf("最多色彩共 %d 種\n", ans); //輸出最多顏色區段
  return 0;
}

執行結果:

新增功能:
***找出顏色種類最多的序列***

---
### 4.樹狀圖分析
題意:

>有一個大家族有 N 個成員，編號
1~N，我們請每個成員寫下此家族中哪幾位是他的孩子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說，編號 i 的人如果高度記做
h(i)，那麼 h(i)就表示在所有 i 的子孫中，最遠的子孫與他隔了幾代。本題假設除了最高的一位祖先(稱為 root)之外，其他成員的 parent
都在此家族中(且只有一個 parent)。本題要計算所有成員高度的總和以及根的編號

程式碼:

#include <bits/stdc++.h>
using namespace std;
#define N 100
void showTree(vector<int> V[], int n);
int findRoot(int parent[], int n);
void bfs(vector<int> V[], int root);
int main() {
  vector<int> V[N];

  int parent[N] = {0};
  int h[N] = {0};    // 記錄每個節點的高度
  int n, childCount; // n:節點數量   childCount:子節點的數量
  int root;

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> childCount;
    for (int j = 0; j < childCount; j++) {
      int child; // child:子節點
      cin >> child;
      V[i].push_back(child);
      parent[child] = i;
    }
  }
  showTree(V, n);
  root = findRoot(parent, n);
  cout << "\n root=" << root << "\n";
  long long step = 0;
  for (int i = 1; i <= n; i++) { //每個節點
    int cnt = 0;                 // i走的步數
    // 直到走到root為止
    for (int j = i; j != 0; j = parent[j]) {
      h[j] = max(h[j], cnt);
      cnt++;
      step++;
    }
  }

  long long total = 0;
  for (int i = 1; i <= n; i++)
    total += h[i];
  printf(" high:%lld\n", total);

  bfs(V, root); //廣度搜尋

  return 0;
}
int findRoot(int parent[], int n) {
  int root;
  for (root = 1; root <= n; root++) { //找根
    if (parent[root] == 0)
      break;
  }

  return root;
}
void showTree(vector<int> V[], int n) { //列出樹狀結構
  // cout << "\n\nVector :\n" ;
  for (int i = 1; i <= n; i++) {
    printf(" node [ %d ]", i);
    // if( V[i].size()==0)printf("  ->  X");
    for (int j = 0; j < V[i].size(); j++) {
      printf("  -> %d ", V[i][j]);
    }
    printf("\n");
  }
}

void bfs(vector<int> V[], int root) {
  queue<int> q;
  vector<bool> vi;     //走訪標記
  vi.assign(N, false); //走訪標記
  q.push(root);        //設定出初始位置
  vi[root] = true;
  cout << " BFS check order:";

  while (!q.empty()) {

    int f = q.front();
    q.pop();

    cout << "->" << f; //輸出當前節點

    for (auto i = V[f].begin(); i != V[f].end(); i++) { //鄰近節點
      if (!vi[*i]) {
        q.push(*i);

        vi[*i] = true;
      }
    }
  }
  cout << "\n";
}

執行結果:

新增功能:
***顯示搜尋過程及全部節點的高度總和***

---