第一题 AC，比较简单的热身题：

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

typedef struct node {
  int val;
  node* next;
  node(int val) : val(val), next(NULL) {}
} node;

int main() {
  int n, k;
  cin >> n >> k;
  node* vhead = new node(0);
  node* last = vhead;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> v;
    if (i + 1 == k) continue;
    last->next = new node(v);
    last = last->next;
  }
  for (node* p = vhead->next; p; p = p->next) {
    printf("%d ", p->val);
  }
  return 0;
}

第二题 AC，这里的关键在于 cmp 函数。很明显不能把所有子串找到后再排序，会爆内存。因此只能保证生成子串的时候就是按照字典序生成的：

#include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

string s;
typedef pair<int, char> Item;
bool cmp(const Item &a, const Item &b) {
  if (a.second == b.second) {
    int i = a.first, j = b.first;
    while (s[i] == s[j] && i < s.length() && j < s.length()) {
      i++, j++;
    }
    if (i < s.length() && j < s.length()) {
      return s[i] < s[j];
    }
    return i < s.length();
  }
  return a.second < b.second;
}

// ac 关键在于 cmp 函数
// acab 2
int main() {
  int k;
  cin >> s >> k;
  set<string> ss;
  vector<Item> pairs(s.length());
  for (int i = 0; i < s.length(); i++) {
    pairs[i] = Item(i, s[i]);
  }
  sort(pairs.begin(), pairs.end(), cmp);
  for (int i = 0; i < pairs.size(); i++) {
    int start = pairs[i].first;
    for (int l = 1; l <= s.length() - start; l++) {
      ss.insert(s.substr(start, l));
    }
    if (ss.size() >= k) break;
    k -= ss.size();
    ss.erase(ss.begin(), ss.end());
  }
  int c = 1;
  for (std::set<string>::iterator it = ss.begin(); it != ss.end(); it++, c++) {
    if (c == k) {
      cout << *it << endl;
      return 0;
    }
  }
  return 0;
}

第三题只过了 50%。有个 bug，现在修了。不过这道题看其他同学的题解，有更优的解法。

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

#define IType long long
map<IType, int> ss;

int s(IType a) {
  if (ss.find(a) != ss.end()) return ss[a];
  int res = 0;
  IType n = a;
  while (n) {
    res += n % 10;
    n /= 10;
  }
  ss[a] = res;
  return res;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    IType n;
    int res = 0;
    cin >> n;
    for (IType a = 0; a <= n / 2; a++) {
      res = max(res, s(a) + s(n - a));
    }
    cout << res << endl;
  }
  return 0;
}

第四题 AC：

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

int heights[5010];

int minIndex(int l, int r) {
  int res = l;
  for (int i = l + 1; i <= r; i++) {
    if (heights[i] < heights[res]) res = i;
  }
  return res;
}

// 对于每个区间的柱子，有两种情况：
// 如果不横着刷，那就每个柱子分别竖着刷
// 如果横着刷，那就按最矮的柱子的高度，下方全部横着刷掉（否则如果不刷掉，那柱子数量没变，反而增加了刷的次数）
// 横着刷完后，最矮柱子左右分成两个区间，递归。这两个区间再计算横着刷的次数时，应当把下方已经刷过的高度减掉
// 但是如果计算竖着刷的次数，那么下方被刷过的地方并不影响


// 注意这几个测试用例
// 3 4 -> 2
// 55 55 1 -> 3
// 2 2 1 2 1 -> 3
int dfs(int l, int r, int base) {
  if (l > r) return 0;
  if (l == r)
    return min(1, heights[l] - base);  // 返回：竖着刷 or 横着刷的最小值
  int idx = minIndex(l, r);
  int minHeight = heights[idx];
  int res = (minHeight - base) +          // 需要横着刷的次数
            dfs(l, idx - 1, minHeight) +  // 左面区间的最少次数
            dfs(idx + 1, r, minHeight);   // 右面区间的最少次数
  return min(r - l + 1, res);  // 返回：全部竖着刷 or 下方横着刷的最小值
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> heights[i];
  cout << dfs(0, n - 1, 0) << endl;
  return 0;
}

第五题 AC，这道题和 leetcode 131、132 异曲同工。两个 dp 就可以了：

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

bool flag[410][410]; // flag[i][j] 表示 s[i~j] 是不是回文子串
int dp[410][410];  // dp[i][j] 表示 s[i~j] 被拆分为多少个子串

int main() {
  string s;
  cin >> s;
  for (int l = 1; l <= s.length(); l++) {
    for (int i = 0; i <= s.length() - l; i++) {
      int j = i + l - 1;
      flag[i][j] = s[i] == s[j] && (i + 1 > j - 1 || flag[i + 1][j - 1]);
    }
  }
  for (int l = 1; l <= s.length(); l++) {
    for (int i = s.length() - 1; i >= 0; i--) {
      int j = i + l - 1;
      if (flag[i][j])
        dp[i][j] = 1;
      else {
        dp[i][j] = 0x7fffffff; // 这里必须手动设置为最大值
        for (int k = i; k < j; k++) {
          if (flag[i][k]) dp[i][j] = min(dp[i][j], 1 + dp[k + 1][j]);
        }
      }
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << dp[l - 1][r - 1] << endl;
  }
  return 0;
}