美团笔试 3.19（AK代码）

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10;

int a[N], b[N], c[N], d[N], n, m;

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> c[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> d[i];
  }
  int sum = 0, cur = 0;
  for (int i = 1; i <= n; i++) {
    sum += a[i], cur += b[i];
    int p = 0;
    for (int j = 1; j <= m; j++) {
      if (sum >= c[j]) {
        p = j;
      }
    }
    int ans = sum - d[p];
    if (ans == cur) {
      putchar('B');
    } else if (ans < cur) {
      putchar('M');
    } else {
      putchar('Z');
    }
  }
  return 0;
}

B（规律）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

char str[N], ans[N];

int n, m;

void solve1() {
    int p = 0, l, r;
    if (n & 1) {
        ans[++p] = str[n / 2 + 1];
        l = n / 2, r = n / 2 + 2;
    } else {
        l = n / 2, r = n / 2 + 1;
    }
    while (l) {
        ans[++p] = str[l--];
        ans[++p] = str[r++];
    }
}

void solve2() {
    int p = 1, l, r;
    if (n & 1) {
        ans[n / 2 + 1] = str[p++];
        l = n / 2, r = n / 2 + 2;
    } else {
        l = n / 2, r = n / 2 + 1;
    }
    while (l) {
        ans[l--] = str[p++];
        ans[r++] = str[p++];
    }
}

int main() {
    cin >> n >> m >> str + 1;
    if (m == 1) {
        solve1();
    } else {
        solve2();
    }
    cout << ans + 1 << endl;
    return 0;
}

C（离散化、差分前缀和）

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int l1[N], r1[N], l2[N], r2[N], a[N], b[N], len[N], sum1[N], sum2[N], T, n, m, cnt, tot;

int main() {
    cin >> T >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> l1[i];
        a[++cnt] = l1[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r1[i];
        a[++cnt] = r1[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> l2[i];
        a[++cnt] = l2[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> r2[i];
        a[++cnt] = r2[i];
    }
    a[++cnt] = 1;
    a[++cnt] = T;
    sort(a + 1, a + 1 + cnt);
    cnt = unique(a + 1, a + 1 + cnt) - (a + 1);
    b[++tot] = a[1];
    len[tot] = 1;
    for (int i = 2; i <= cnt; i++) {
        if (a[i] != a[i - 1] + 1) {
            b[++tot] = a[i] - 1;
            len[tot] = a[i] - a[i - 1] - 1;
        }
        b[++tot] = a[i];
        len[tot] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int p1 = lower_bound(b + 1, b + 1 + tot, l1[i]) - b;
        int p2 = lower_bound(b + 1, b + 1 + tot, r1[i]) - b;
        sum1[p1]++, sum1[p2 + 1]--;
    }
    for (int i = 1; i <= m; i++) {
        int p1 = lower_bound(b + 1, b + 1 + tot, l2[i]) - b;
        int p2 = lower_bound(b + 1, b + 1 + tot, r2[i]) - b;
        sum2[p1]++, sum2[p2 + 1]--;
    }
    int ans = 0;
    for (int i = 1; i <= tot; i++) {
        sum1[i] += sum1[i - 1];
        sum2[i] += sum2[i - 1];
        if (sum1[i] && sum2[i]) {
            ans += len[i];
        }
    }
    cout << ans << endl;
    return 0;
}

D（DP计数）

// 可以考虑 另 p = lcm(k1, k2), f[i][j]，表示前i个数中模p余j的最大值，g[i][j]表示取到该值的方案。
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, mod = 998244353;

int f[N][110], g[N][110], a[N], n, k1, k2, p;

int main() {
    cin >> n >> k1 >> k2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    p = k1 * k2 / __gcd(k1, k2);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < p; j++) {
            f[i][j] = -0x3f3f3f3f;
        }
    }
    f[0][0] = 0, g[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < p; j++) {
            f[i][j] = max(f[i][j], f[i - 1][j]);
            // f[i - 1][j] -> (j + a[i]) % p + p % p
            int cur = ((j + a[i]) % p + p) % p;
            if (f[i - 1][j] != -0x3f3f3f3f) {
                f[i][cur] = max(f[i][cur], f[i - 1][j] + a[i]);
            }
        }
        for (int j = 0; j < p; j++) {
            // g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
            int cur = ((j + a[i]) % p + p) % p;
            if (f[i - 1][j] != -0x3f3f3f3f && f[i][cur] == f[i - 1][j] + a[i]) {
                g[i][cur] = (g[i][cur] + g[i - 1][j]) % mod;
            }
            if (f[i - 1][j] == f[i][j]) {
              g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
            }
        }
    }
    int ans = -0x3f3f3f3f, sum;
    for (int i = 0; i < p; i++) {
        if (i % k1 == 0 && i % k2 != 0) {
            if (f[n][i] > ans) {
                ans = f[n][i], sum = g[n][i];
            }
        }
    }
    cout << ans << " " << sum << endl;
    return 0;
}

E（递归、找规律）

#include <bits/stdc++.h>

using namespace std;

const int N = 50;

long long p[N], k, ans;

int main() {
  p[0] = 1;
  for (int i = 1; i < N; i++) {
    p[i] = p[i - 1] * 3;
  }
  int n;
  cin >> n >> k;
  while (n--) {
    if (k <= p[n]) {
      ans++;
    } else if (k <= 2 * p[n]) {
      k -= p[n];
    } else {
      ans += 2;
      k -= 2 * p[n];
    }
  }
  cout << ans << endl;
  return 0;
}