字节3.21笔试(满分）

前三个题的代码都是考完复盘的最后一个题是当时写的

A.给定n个猴子每个猴子有个食量，每个猴子轮流拿香蕉，要求拿的数量为min(remain/2,eat*2)且该数量>eat，其中remain是当前剩余食物数量，eat是食量。最后一个猴子可以全部拿走，求最小的食物数量使得每个人都能吃饱。

1<=n<=200

题解：考虑到这个食物数量肯定是单调的，那么二分答案即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
vector<int> v;
int a;
int check(int mid) {
  for (int i = 0; i + 1 < v.size(); i++) {
    int num = min(mid / 2, v[i] * 2);
    if (num < v[i]) return 0;
    mid -= num;
  }
  if (mid < v.back()) return 0;
  return 1;
}
int main() {
  while (cin >> a) {
    v.pb(a);
  }
  int l = 1, r = 1e9 + 7;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  printf("%d\n", l);
  return 0;
}

B.给定一个长度为n的序列，选出一段和最大且长度不超过M的子数组

1<=n<=1e5, -100<=a[i]<=100,1<=m<=n

题解：枚举子数组的右端点，可以用线段树查询出能取的左端点的前缀和最小值，更新答案即可

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n, m;
int a[100010];
int sum[100010];
int tree[100010 << 4];
void build(int rt, int l, int r) {
  if (l == r) {
    tree[rt] = sum[l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) return tree[rt];
  int res = 1e9 + 7;
  int mid = (l + r) >> 1;
  if (L <= mid) {
    res = min(res, query(rt << 1, l, mid, L, R));
  }
  if (R >= mid + 1) {
    res = min(res, query(rt << 1 | 1, mid + 1, r, L, R));
  }
  return res;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  sum[0] = 0;
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
  build(1, 1, n + 1);
  int Max = 0;
  for (int i = 1; i <= n; i++) {
    int qu = query(1, 1, n + 1, max(1, i - m + 1), i);
    Max = max(Max, sum[i] - qu);
  }
  printf("%d\n", Max);
  return 0;
}

C：现在给你一个空字符串s，给定三个操作：

1.倍增s，花费为a

2.末尾添加一个A,花费为b

3.末尾去掉一个A,花费为b

问要让序列为n个A的时候的最小花费

1<=n<=1e18,1<=a,b<=1e9

题解：从最终的状态往前dp，若当前为偶数，肯定是切成一半，若当前为奇数，要么是去掉一个，要么是补上一个然后再切成两半，用map记忆化就可以了

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
map<ll, ll> dp;
ll n, a, b;
ll dfs(ll n) {
  if (n == 0) return 0;
  if (n == 1) return b;
  if (n == 2) return min(a + b, b + b);
  if (dp.count(n)) return dp.find(n)->second;
  if (n % 2 == 0) {
    ll res = 1e18;
    if ((1.0 * a) / b > n / 2) {
      res = min(res, dfs(n / 2) + b * n / 2);
    } else {
      res = min(res, dfs(n / 2) + a);
    }
    return dp[n] = res;
  } else {
    ll res = 1e18;
    res = min(res, dfs(n - 1) + b);
    res = min(res, dfs((n + 1) / 2) + b + a);
    return dp[n] = res;
  }
}

int main() {
  scanf("%lld %lld %lld", &n, &a, &b);
  printf("%lld\n", dfs(n));
  return 0;
}

D:给你一个字符串S跟一个长度为2的字符串T,一次操作可以更改S里的一个字母，问在不超过k次操作的前提下，S中与T相同的子序列最多。

1<=strlen(S)<=200,1<=k<=strlen(S)

题解：dp(i,j,l）表示S的前i个字母改了j个，且有l个T[1]的最大子序列数状态转移即可

#include <cstdio>
#include <vector>
#include <iostream>
#include <cassert>
#include <map>
using namespace std;
int n,k;
char s[210];
char t[10];
//前i个,改了j次，有k个t[1]
int dp[220][220][220];
int vis[220][220][220];
int main(){
    scanf("%d %d",&n,&k);
    scanf("%s",s+1);
    scanf("%s",t+1);
    for (int i=0;i<=n;i++){
        for (int j=0;j<=k+1;j++){
            for (int l=0;l<=n;l++) dp[i][j][l]=0;
        }
    }
    vis[0][0][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=0;j<=k;j++){
            for (int l=0;l<=i;l++){
                if (!vis[i-1][j][l]) continue;
                //不改
                if (s[i]==t[1]&&s[i]!=t[2]){
                    dp[i][j][l+1]=max(dp[i][j][l+1],dp[i-1][j][l]);
                    vis[i][j][l+1]=1;
                }
                else if (s[i]==t[1]&&s[i]==t[2]){
                    dp[i][j][l+1]=max(dp[i][j][l+1],dp[i-1][j][l]+l);
                    vis[i][j][l+1]=1;
                }
                else if (s[i]!=t[1]&&s[i]==t[2]){
                    dp[i][j][l]=max(dp[i][j][l],dp[i-1][j][l]+l);
                    vis[i][j][l]=1;
                }
                else{
                    dp[i][j][l]=max(dp[i][j][l],dp[i-1][j][l]);
                    vis[i][j][l]=1;
                }
                //改
                if (t[1]==t[2]){
                    if (s[i]==t[1]) continue;
                    //改成t[1]
                    dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i-1][j][l]+l);
                    vis[i][j+1][l+1]=1;
                }
                else{
                    //改成t[1]
                    if (s[i]!=t[1]){
                        dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i-1][j][l]);
                        vis[i][j+1][l+1]=1;
                    }
                    //改成t[2]
                    if (s[i]!=t[2]){
                        dp[i][j+1][l]=max(dp[i][j+1][l],dp[i-1][j][l]+l);
                        vis[i][j+1][l]=1;
                    }
                }
            }
        }
    }
    int Max = 0;
    for (int j=0;j<=k;j++){
        for (int l=0;l<=n;l++) Max = max(Max,dp[n][j][l]);
    }
    printf("%d\n",Max);
    return 0;
}

#笔试题目##字节跳动#