虾皮9.2后端笔试编程题ak笔记

选择题完全看不懂，完全乱选，没什么好记的。

实际比赛中是写在一个class里面的，本质是一样的。

1

题意：给定一个序列，要把这个序列变成一个数，每次将相邻两个数合成一个数，贡献为新合成的数，求最小贡献。

区间dp 。

int solve(const int *gz, int gzLen) {
  const int n = gzLen;
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++) {
    a[i] = gz[i - 1];
    b[i] = b[i - 1] + a[i];
  }
  vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
  for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;
  }
  for (int len = 2; len <= n; len++) {
    for (int i = 1; i <= n - len + 1; i++) {
      const int j = i + len - 1;
      for (int k = i; k < j; k++) {
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + b[j] - b[i - 1]);
      }
    }
  }
  return dp[1][n];
}

实际上这个题是一个经典题，有的做法，用四边形不等式做到决策单调性。以前就听说过，但一直不会用，用途不广泛。看到这个题的时候就觉得很熟悉，感觉应该是哪里的原题抄过来而已。结束之后问队友才知道。

反正过了

2

题意：给定一个字符串，将这个字符串变成两个以上相同字符串的拼接，只能在字符串的末尾补，问最少要补多少个字符。

我的做法是z_function求某个前缀是否为循环节。实际上直接kmp求就可以了，但我不是很会kmp，对于字符串题通常也只会套模板，所以我就直接用我比较熟悉的z_function了。

vector<int> z_function(const string& s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}

int solve(const string& s) {
  vector<int> z = z_function(s);
  const int n = s.size();
  int ans = n;
  for (int i = 1; i < n; i++) {
    if (z[i] == n - i) {
      ans = min(ans, (n + i - 1) / i * i - n);
    }
  }
  return ans;
}

3

题意：有两种东西，每种东西都有n个，每一次随机选一种东西它的数量减一，当选择的东西的数量为0，问另一个东西的数量的期望是多少。（期望向下取整）

令表示第一种东西有个，第二种东西有个，那么有，其中且，但用下标-1有点危险，一开始把n += 1再处理即可。

int solve(int n) {
  n++;
  vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0.0));
  for (int i = 1; i <= n; i++) {
    dp[i][0] = i - 1;
    dp[0][i] = i - 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) * 0.5;
    }
  }
  return int(dp[n][n] + 1e-6);
}