字节跳动9.6后端笔试ak笔记

没有选择题，爷青回！

不过居然不给用ide，我又一次没带草稿纸，只能用编辑器的注释来记一下了。。

下面的代码仅供参考，因为不是现场写的代码，不一定能ac，因为不给用ide代码存不下来。

1

题意

一个人跳楼梯，可以跳一格，可以跳两格，但不能连续跳两格，问跳到层有多少种方式。（）

Solution

表示跳到第层表示上一次跳跃是不是两格，显然有。

那么答案即。

首先需要令，然后从递推上去即可。

然后要特判，我也不知道为什么的时候答案是，题目也没说，很迷。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  vector<vector<int64_t>> dp(105, vector<int64_t>(2, 0));
  dp[0][0] = 1;
  for (int i = 1; i < 105; i++) {
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
    if (i >= 2) {
      dp[i][1] = dp[i - 2][0];
    }
  }
  int n; cin >> n;
  if (n == 0) {
    cout << 0 << '\n';
    return 0;
  }
  cout << (dp[n][0] + dp[n][1]) << '\n';
}

这题的数据范围以及不取模差点让我投奔Python去了。

2

题意

给定一个长为的序列。表示第个位置左边第一个大于的数的下标（从开始），没有的话为。表示第个位置右边第一个大于的数的下标（从开始），没有的话为。求。

Solution

非常裸的单调栈。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n; cin >> n;
  int64_t ans = 0;
  vector<int> a(n), l(n, 0);
  stack<int> stk;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    while (!stk.empty() && a[stk.top()] <= a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      l[i] = stk.top() + 1;
    }
    stk.push(i);
  }
  while (!stk.empty()) {
    stk.pop();
  }
  for (int i = n - 1; i >= 0; i--) {
    while (!stk.empty() && a[stk.top()] <= a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      ans = max(ans, (int64_t)(1ll * l[i] * (stk.top() + 1)));
    }
    stk.push(i);
  }
  cout << ans << '\n';
}

3

题意

给定一个长为的序列，这个序列是由一个长为的序列重复次得来的。问这个序列的最大连续子段和是多少。（）

Solution

重复了次的序列称为一段序列。如果为，那就是一个普通的最大连续子段和的题了。如果，那么结果一定是某一段序列的最大连续子段和，或者是这一段的后缀加这一段的前缀，或者如果一段序列总和大于0，那就是这一段的后缀加这一段的前缀再加上段序列。总体思路和为时是差不多的，求后缀拼前缀时把这一段序列接起来变成两段序列再求一下最大连续子段和即可。

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m; cin >> n >> m;
  vector<int> a(n * 2);
  int64_t ans = LLONG_MIN, dp = 0, sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (dp <= 0) {
      dp = a[i];
    } else {
      dp += a[i];
    }
    ans = max(ans, dp);
    sum += a[i];
  }
  if (m == 1) {
    cout << ans << '\n';
    return 0;
  }
  int64_t link = LLONG_MIN;
  for (int i = n; i < 2 * n; i++) {
    a[i] = a[i - n];
    if (dp <= 0) {
      dp = a[i];
    } else {
      dp += a[i];
    }
    link = max(link, dp);
  }
  if (sum > 0) {
    link += 1ll * sum * (m - 2);
  }
  cout << max(link, ans) << '\n';
}

4

题意

给定一个序列和，要求把整个序列变成w，每一次操作选择一个和，使得序列区间到的值增加1。每一次操作的都不相同且每一次操作的都不相同，问有多少种方式可以把整个序列变成，求结果对取模的结果。（）

Solution

转换成差分数组求解。先求这个序列最终需要增加的大小的序列的差分数组，如果差分数组有大于或者小于则无解输出，因为端点不能重复，而代表这是区间增加的开始，代表这是区间增加的结束位置。还有一种无解的情况是有数比大也是无解的。对于差分数组中的，可以是和的叠加。然后枚举差分数组中所有的位置假设当前位置是（处也要枚举，因为可能是叠加的状态），去选一个前面出现过的假设这个的位置是，则区间被选择了，选的情况很显然就是前面的个数，前面的个数实际上就是转换后的数组，因为差分数组再前缀和就是原来的数组，然后将所有枚举的情况累乘即可。好像本题是一个套路题，但原题暂时没有办法找到。

Code

#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005];
const int64_t MOD = 1e9 + 7;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, w; cin >> n >> w;
  bool ok = true;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = w - a[i];
    b[i] = a[i] - a[i - 1];
    if (a[i] < 0 || b[i] < -1 || b[i] > 1) {
      ok = false;
    }
  }
  b[n + 1] = -a[n];
  if (b[n + 1] < -1 || b[n + 1] > 1) {
    ok = false;
  }
  if (!ok) {
    cout << "0\n";
    return 0;
  }
  int64_t ans = 1;
  for (int i = 1; i <= n + 1; i++) {
    if (b[i] == 0 || b[i] == -1) {
      ans = (ans * (a[i] + 1)) % MOD;
    }
  }
  cout << ans << '\n';
}